✦ LIBER ✦

Maximum pebbling number of graphs of diameter three

✍ Scribed by Boris Bukh

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 93 KB
Volume: 52
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20187

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a configuration of pebbles on the vertices of a graph G, a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v. The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G. We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2)n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Pebbling in diameter two graphs and prod

Pebbling in diameter two graphs and products of paths

✍ Clarke, T. A.; Hochberg, R. A.; Hurlbert, G. H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing t

Maximum degree in graphs of diameter 2

✍ Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

Maximum number of colorings of (2k, k2)-

Maximum number of colorings of (2k, k2)-graphs

✍ Felix Lazebnik; Oleg Pikhurko; Andrew Woldar 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract Let ${\cal F}\_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2__k__ vertices and ${k}^{2}$ edges. For a simple graph __G__ and a positive integer $\lambda$, let ${P}\_{G}(\lambda)$ denote the number of proper vertex colorings of __G__ in at most $\lambda$ colors, and let $f(2k, k^{2

The maximum interval number of graphs wi

The maximum interval number of graphs with given genus

✍ Edward R. Scheinerman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investiga

On graphs with the maximum number of spa

On graphs with the maximum number of spanning trees

✍ Alexander K. Kelmans 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta

Total chromatic number of planar graphs

Total chromatic number of planar graphs with maximum degree ten

✍ Weifan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views