Pebbling in Kneser Graphs

被引：0

作者：

Adauto, Matheus ^{[1
,3
]}

Bardenova, Viktoriya ^{[3
]}

da Cruz, Mariana ^{[1
]}

de Figueiredo, Celina ^{[1
]}

Hurlbert, Glenn ^{[3
]}

Sasaki, Diana ^{[2
]}

机构：

[1] Univ Fed Rio De Janeiro, Programa Engn Sistemas Comp, Rio De Janeiro, Brazil

[2] Univ Estado Rio De Janeiro, Inst Matemat Estat, Rio De Janeiro, Brazil

[3] Virginia Commonwealth Univ, Dept Math & Appl Math, Richmond, VA 23284 USA

来源：

LATIN 2024: THEORETICAL INFORMATICS, PT II | 2024年 / 14579卷

关键词：

graph pebbling; Kneser graphs; odd graphs; weight function method; DIAMETER;

D O I：

10.1007/978-3-031-55601-2_4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex. The pebbling number pi(G) is the smallest t so that from any initial configuration of t pebbles it is possible, after a sequence of pebbling moves, to place a pebble on any given target vertex. We consider the pebbling number of Kneser graphs, and give positive evidence for the conjecture that every Kneser graph has pebbling number equal to its number of vertices.

引用

页码：46 / 60

页数：15

共 16 条

[1] Adauto M, 2024, Arxiv, DOI arXiv:2303.13292
[2] Pebbling in powers of paths
Alcon, Liliana
Hurlbert, Glenn
[J]. DISCRETE MATHEMATICS, 2023, 346 (05)
[3] Pebbling in semi-2-trees
Alcon, Liliana
Gutierrez, Marisa
Hurlbert, Glenn
[J]. DISCRETE MATHEMATICS, 2017, 340 (07) : 1467 - 1480
[4] PEBBLING IN SPLIT GRAPHS
Alcon, Liliana
Gutierrez, Marisa
Hurlbert, Glenn
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (03) : 1449 - 1466
[5] Improved pebbling bounds
Chan, Melody
Godbole, Anant P.
[J]. DISCRETE MATHEMATICS, 2008, 308 (11) : 2301 - 2306
[6] Chung F.R.K., 1989, SIAM J DISCRETE MATH, V2, P467, DOI [10.1137/0402041, DOI 10.1137/0402041]
[7] Clarke TA, 1997, J GRAPH THEOR, V25, P119, DOI 10.1002/(SICI)1097-0118(199706)25:2<119::AID-JGT3>3.3.CO
[8] 2-#
[9] Modified linear programming and class 0 bounds for graph pebbling
Cranston, Daniel W.
Postle, Luke
Xue, Chenxiao
Yerger, Carl
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (01) : 114 - 132
[10] A note on graph pebbling
Czygrinow, A
Hurlbert, G
Kierstead, HAI
Trotter, WT
[J]. GRAPHS AND COMBINATORICS, 2002, 18 (02) : 219 - 225

← 1 2 →