مدل و عدد سنگ‌ریزه گراف

نوع مقاله : مقاله پژوهشی

نویسندگان

دانشکده علوم ریاضی، دانشگاه یزد، یزد

چکیده

موضوعات بسیاری در نظریه گراف وجود دارند که می‌توانند تحت عنوان «حرکت اشیاء حول یک گراف» قرار گیرند. برای مثال، در بهینه‌سازی شبکه، محموله‌ها با توجه به هزینه‌های تعلق گرفته به یال‌ها، از برخی رئوس (منابع) به برخی دیگر از رئوس (تقاضا) به نحوی منتقل می‌شوند که این‌ کار به ارزان‌ترین حالت انجام شود. یک حرکت سنگ‌ریزه در گراف، شامل برداشتن دو سنگ‌ریزه از یک رأس گراف و سپس قرار دادن یک سنگ‌ریزه در رأس مجاور آن است. اگر یک توزیع (یا پیکربندی) از سنگ‌ریزه‌ها به ما اجازه دهد که با اعمال مکررِ حرکات سنگ‌ریزه، حداقل یک سنگ‌ریزه را به هر رأس حرکت دهیم، آنگاه آن توزیع، یک سنگ‌ریزه از گراف نامیده می‌شود. از اساسی‌ترین سوالات این است که چه تعداد سنگ‌ریزه مورد نیاز است تا ضمانت کند که هر پیکربندی با این تعداد، می‌تواند یک سنگ‌ریزه را روی هر رأس هدف مشخص قرار دهد. به کمترین تعداد سنگ که این شرط را برآورده کند، عدد سنگ‌ریزه گراف می‌گویند. در این مقاله، پس از بررسی ریشه‌های نظریه اعدادِ مدل گراف سنگ‌ریزه که به نوبه خود موضوع پرباری است، عدد سنگ‌ریزه را برای گراف‌های خاص مطالعه کرده و همچنین یک رویکرد بهینه‌سازی در این موضوع، به نام توابع وزن را مورد بررسی قرار خواهیم داد.

کلیدواژه‌ها

موضوعات


[1] J. Asplund, G. Hurlbert and F. Kenter, Pebbling on graph products and other binary graph construc-tions, Australas. J. Combin., 71 (2018) 246–260.
[2] D. P. Bunde, E. W. Chambers, D. Cranston, K. Milans and D. B. West, Pebbling and optimal pebbling in graphs, J. Graph Theory, 57 (2008) 215– 238.
[3] Fan R. K. Chung, Pebbling in hypercubes, SIAM J. Discrete Math., 2 (1989) 467–472.
[4] D. W. Cranston, L. Postle, Ch. Xue and C. Yerger, Modified linear programming and class 0 bounds for graph pebbling, J. Comb. Optim., 34 (2017) 114–132.
[5] B. Crull, T. Cundiff, P. Feltman, G. H. Hurlbert, L. Pudwell, Z. Szaniszlo and Z. Tuza, The cover pebbling number of graphs, Discrete Math., 296 (2005) 15–23.
[6] Ch. A. Cusack, M. Powers and A. Bekmetjev, Doppelgangers and Lemke graphs, Discrete Math., 341 (2018) 2686–2693.
[7] A. Czygrinow, G. Hurlbert, H. A. Kierstead and W. T. Trotter, A note on graph pebbling, Graphs Combin., 18 (2002) 219–225.
[8] G. Hurlbert, General graph pebbling, Discrete Appl. Math., 161 (2013) 1221–1231.
[9] G. Hurlbert, Graph pebbling, Handbook of Graph Theory, 2nd ed., Chapman and Hall/CRC, Kalamazoo, MI, 2014 1428–1449.
[10] G. Hurlbert, The weight function lemma for graph pebbling, J. Comb. Optim., 34 (2017) 343–361.
[11] F. Kenter, D. Skipper and D. Wilson, Computing bounds on product graph pebbling numbers, Theoret. Comput. Sci., 803 (2020) 160–177.
[12] G. Hurlbert and F. Kenter, Graph Pebbling: A Blend of Graph Theory, Number Theory and Optimiza-tion, Notices AMS, 68 (2021) 1900–1913.
[13] D. Moews, Pebbling graphs, J. Combin. Theory Ser. B, 55 (1992) 244–252.
[14] L. Postle, N. Streib and C. Yerger, Pebbling graphs of diameter three and four, J. Graph Theory, 72 (2013) 398–417.