پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 42 |
| تعداد شماره‌ها | 1,514 |
| تعداد مقالات | 12,479 |
| تعداد مشاهده مقاله | 24,743,567 |
| تعداد دریافت فایل اصل مقاله | 10,433,938 |
Bounds for the pebbling number of product graphs | ||
| Transactions on Combinatorics | ||
| مقاله 3، دوره 11، شماره 4، اسفند 2022، صفحه 317-326 اصل مقاله (438.93 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2021.128705.1855 | ||
| نویسندگان | ||
| Nopparat Pleanmani* ؛ Nuttawoot Nupo؛ Somnuek Worawiset | ||
| Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand | ||
| چکیده | ||
| Let $G$ be a connected graph. Given a configuration of a fixed number of pebbles on the vertex set of $G$, a pebbling move on $G$ is the process of removing two pebbles from a vertex and adding one pebble on an adjacent vertex. The pebbling number of $G$, denoted by $\pi(G)$, is defined to be the least number of pebbles to guarantee that there is a sequence of pebbling movement that places at least one pebble on each vertex $v$, for any configuration of pebbles on $G$. In this paper, we improve the upper bound of $\pi(G\square H)$ from $2\pi(G)\pi(H)$ to $\left(2-\frac{1}{\min\{\pi(G),\pi(H)\}}\right)\pi(G)\pi(H)$ where $\pi(G)$, $\pi(H)$ and $\pi(G\square H)$ are the pebbling number of graphs $G$, $H$ and the Cartesian product graph $G\square H$, respectively. Moreover, we also discuss such bound for strong product graphs, cross product graphs and coronas. | ||
| کلیدواژه‌ها | ||
| Graph pebbling؛ Graham's conjecture؛ product graph؛ corona | ||
| مراجع | ||
|
[1] J. Asplund, G. Hurlbert and F. Kenter, Pebbling on graph products and other binary graph constructions, Australas. J. Combin., 71 no. 2 (2018) 246–260. [2] F. Chung, Pebbling in hypercubes, SIAM J. Discrete Math., 2 (1989) 467–472.
[3] R. Feng and J. Y. Kim, Graham’s pebbling conjecture on product of complete bipartite graphs, Sci. China Ser. A, 44 (2001) 817–822. [4] D. S. Herscovici and A. W. Higgins, The pebbling number of C5 × C5 , Discrete Math., 187 (1998) 123–135.
[5] G. Hurlbert, Graph pebbling, Handbook of graph theory, CRC Press, 2nd edition, Boca Raton, 2014, 1428–1454.
[6] G. Hurlbert, The graph pebbling page, http://www.people.vcu.edu/ ghurlbert/pebbling/pebb.html.
[7] W. Imrich and S. Klavzar, Product graphs: structure and recognition, Wiley-Interscience, New York, 2000.
[8] U. Knauer, Algebraic graph theory: morphisms, monoids and matrices, De Gruyter, Berlin-Boston, 2011.
[9] M. Mohorn, An introduction to graph pebbling, B. Sc. Thesis, Davidson College, May 2014.
[10] N. Pleanmani, Graham’s pebbling conjecture holds for the product of a graph and a sufficiently large complete bipartite graph, Discrete Math. Algorithms Appl., 11 no. 6 (2019) 1–7.
[11] N. Pleanmani, Graham’s pebbling conjecture holds for the product of a graph and a sufficiently large complete graph, Theory Appl. Graphs, 1 (2020) 1–7. [12] S. S. Wang, Pebbling and Graham’s conjecture, Discrete Math., 226 (2001) 431–438.
[13] D. B. West Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. | ||
|
آمار تعداد مشاهده مقاله: 505 تعداد دریافت فایل اصل مقاله: 498 |
||