𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Domination number of cubic graphs with large girth

✍ Scribed by Daniel Král'; Petr Škoda; Jan Volec

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
219 KB
Volume
69
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n / g) < 3n / 10+O(n / g) This research was done when the Petr Škoda was a student of

📜 SIMILAR VOLUMES

The circular chromatic number of series-
The circular chromatic number of series-parallel graphs with large girth
✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

UniquelyH-colorable graphs with large gi
UniquelyH-colorable graphs with large girth
✍ Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 2 views

Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition o o c of c with an automorph

Numbers of cubic graphs
Numbers of cubic graphs
✍ R. W. Robinson; N. C. Wormald 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

## Abstract The numbers of unlabeled cubic graphs on __p = 2n__ points have been found by two different counting methods, the best of which has given values for __p ≦__ 40.

Total Colourings of Planar Graphs with L
Total Colourings of Planar Graphs with Large Girth
✍ O.V. Borodin; A.V. Kostochka; D.R. Woodall 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 96 KB

It is proved that if G is a planar graph with total (vertex-edge) chromatic number χ , maximum degree and girth g, then χ = + 1 if ≥ 5 and g ≥ 5, or ≥ 4 and g ≥ 6, or ≥ 3 and g ≥ 10. These results hold also for graphs in the projective plane, torus and Klein bottle.