Pebbling in Split Graphs

DOI10.1137/130914607zbMATH Open1305.05215arXiv1211.4049OpenAlexW2015837397MaRDI QIDQ2935280FDOQ2935280

Authors: L. Alcón, M. Gutierrez, Glenn H. Hurlbert 

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Graph pebbling is a network optimization model for transporting discrete resources 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 Pi_2^P-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 guarantee 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^�eta) time, where �eta=2omega/(omega+1)cong 1.41 and omegacong 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0.

Full work available at URL: https://arxiv.org/abs/1211.4049

Recommendations

• Pebbling and optimal pebbling in graphs
• A note on graph pebbling
• scientific article; zbMATH DE number 1040545
• General graph pebbling
• Pebbling number of some bipartite graphs
• On Pebbling Graphs by Their Blocks
• Optimal pebbling of graphs
• Pebbling numbers of some graphs
• Pebbling Algorithms in Diameter Two Graphs

zbMATH Keywords

complexitygraph algorithmssplit graphsclass 0pebbling number

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12)

Cited In (9)

• Pebbling on Graph Products and other Binary Graph Constructions
• The weight function lemma for graph pebbling
• On the target pebbling conjecture
• Pebbling in 2-paths
• On the number of maximal independent sets in minimum colorings of split graphs
• On the pebbling numbers of flower, Blanuša and Watkins snarks
• Pebbling in powers of paths
• Pebbling in Kneser graphs
• Pebbling in semi-2-trees

This page was built for publication: Pebbling in Split Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935280)