✦ LIBER ✦

Domination numbers of planar graphs

✍ Scribed by MacGillivray, G.; Seyffarth, K.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 967 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199607)22:3<213::aid-jgt2>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of determining the domination number of a graph is a well known NPhard problem, even when restricted to planar graphs. By adding a further restriction on the diameter of the graph, we prove that planar graphs with diameter two and three have bounded domination numbers. This implies that the domination number of such a graph can be determined in polynomial time. We also give examples of planar graphs of diameter four, and nonplanar graphs of diameter two, having arbitrarily large domination numbers.

📜 SIMILAR VOLUMES

Domination critical graphs with higher i

Domination critical graphs with higher independent domination numbers

✍ Ao, S.; Cockayne, E.J.; MacGillivray, G.; Mynhardt, C.M. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB 👁 2 views

We show that for each k L 4 there exists a connected k-domination critical graph with independent domination number exceeding k, thus disproving a conjecture of Sumner and Blitch ( J Cornbinatorial Theory B 34 (19831, 65-76) in all cases except k = 3.

Domination in planar graphs with small d

Domination in planar graphs with small diameter

✍ Wayne Goddard; Michael A. Henning 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract MacGillivray and Seyffarth (J Graph Theory 22 (1996), 213–229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar graphs of diameter four having arbitrar

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

Star chromatic numbers of some planar gr

Star chromatic numbers of some planar graphs

✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 2 views

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of pla

Graphs with large total domination numbe

Graphs with large total domination number

✍ Michael A. Henning 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

The star-chromatic number of planar grap

The star-chromatic number of planar graphs

✍ Moser, David 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The star-chromatic number of a graph, a parameter introduced by Vince, is a natural generalization of the chromatic number of a graph. Here we construct planar graphs with star-chromatic number r, where r is any rational number between 2 and 3, partially answering a question of Vince.