Pebbling in Split Graphs
Graph pebbling is a network optimization model for transporting discrete re- sources that are consumed in transit: the movement of two pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles t so that, from any initial configuration of t peb...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Articulo Preprint |
| Lenguaje: | Inglés |
| Publicado: |
2014
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/162725 |
| Aporte de: |
| id |
I19-R120-10915-162725 |
|---|---|
| record_format |
dspace |
| spelling |
I19-R120-10915-1627252024-02-15T20:08:23Z http://sedici.unlp.edu.ar/handle/10915/162725 Pebbling in Split Graphs Alcón, Liliana Graciela Gutiérrez, Marisa Hurlber, Glenn 2014-01 2024-02-15T17:06:16Z en Ciencias Exactas Matemática pebbling number split graphs Class 0 graph algorithms complexity Graph pebbling is a network optimization model for transporting discrete re- sources that are consumed in transit: the movement of two pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles t so that, from any initial configuration of t pebbles on its vertices, one can place a pebble on any given target vertex via such pebbling steps. It is known that deciding if a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter two graphs, and that deciding if the pebbling number has a prescribed upper bound is Πᴾ₂ -complete. On the other hand, for many families of graphs there are formulas or polynomial algorithms for computing pebbling numbers; for example, complete graphs, products of paths (including cubes), trees, cycles, diameter two graphs, and more. Moreover, graphs having minimum pebbling number are called Class 0, and many authors have studied which graphs are Class 0 and what graph properties guaran- tee it, with no characterization in sight. In this paper we investigate an important family of diameter three chordal graphs called split graphs; graphs whose vertex set can be partitioned into a clique and an independent set. We provide a formula for the pebbling number of a split graph, along with an algorithm for calculating it that runs in O(nᵝ) time, where β = 2ω/(ω + 1) ≅ 1.41 and ω ≅ 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0. Facultad de Ciencias Exactas Departamento de Matemática Articulo Preprint http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Exactas Matemática pebbling number split graphs Class 0 graph algorithms complexity |
| spellingShingle |
Ciencias Exactas Matemática pebbling number split graphs Class 0 graph algorithms complexity Alcón, Liliana Graciela Gutiérrez, Marisa Hurlber, Glenn Pebbling in Split Graphs |
| topic_facet |
Ciencias Exactas Matemática pebbling number split graphs Class 0 graph algorithms complexity |
| description |
Graph pebbling is a network optimization model for transporting discrete re- sources that are consumed in transit: the movement of two pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles t so that, from any initial configuration of t pebbles on its vertices, one can place a pebble on any given target vertex via such pebbling steps. It is known that deciding if a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter two graphs, and that deciding if the pebbling number has a prescribed upper bound is Πᴾ₂ -complete.
On the other hand, for many families of graphs there are formulas or polynomial algorithms for computing pebbling numbers; for example, complete graphs, products of paths (including cubes), trees, cycles, diameter two graphs, and more. Moreover, graphs having minimum pebbling number are called Class 0, and many authors have studied which graphs are Class 0 and what graph properties guaran- tee it, with no characterization in sight.
In this paper we investigate an important family of diameter three chordal graphs called split graphs; graphs whose vertex set can be partitioned into a clique and an independent set. We provide a formula for the pebbling number of a split graph, along with an algorithm for calculating it that runs in O(nᵝ) time, where β = 2ω/(ω + 1) ≅ 1.41 and ω ≅ 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0. |
| format |
Articulo Preprint |
| author |
Alcón, Liliana Graciela Gutiérrez, Marisa Hurlber, Glenn |
| author_facet |
Alcón, Liliana Graciela Gutiérrez, Marisa Hurlber, Glenn |
| author_sort |
Alcón, Liliana Graciela |
| title |
Pebbling in Split Graphs |
| title_short |
Pebbling in Split Graphs |
| title_full |
Pebbling in Split Graphs |
| title_fullStr |
Pebbling in Split Graphs |
| title_full_unstemmed |
Pebbling in Split Graphs |
| title_sort |
pebbling in split graphs |
| publishDate |
2014 |
| url |
http://sedici.unlp.edu.ar/handle/10915/162725 |
| work_keys_str_mv |
AT alconlilianagraciela pebblinginsplitgraphs AT gutierrezmarisa pebblinginsplitgraphs AT hurlberglenn pebblinginsplitgraphs |
| _version_ |
1807222442028957696 |