✦ LIBER ✦

Domination in planar graphs with small diameter

✍ Scribed by Wayne Goddard; Michael A. Henning

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 199 KB
Volume: 40
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10027

No coin nor oath required. For personal study only.

✦ Synopsis

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 arbitrarily large domination numbers. In this paper we improve on their results. We prove that there is in fact a unique planar graph of diameter two with domination number three, and all other planar graphs of diameter two have domination number at most two. We also prove that every planar graph of diameter three and of radius two has domination number at most six. We then show that every sufficiently large planar graph of diameter three has domination number at most seven. Analogous results for other surfaces are discussed. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 1–25, 2002

📜 SIMILAR VOLUMES

Dominating Sets in Planar Graphs

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

Superconnected digraphs and graphs with

Superconnected digraphs and graphs with small conditional diameters

✍ C. Balbuena; J. Fàbrega; X. Marcote; I. Pelayo 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 179 KB

Connected subgraphs with small degree su

Connected subgraphs with small degree sums in 3-connected planar graphs

✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Total domination in graphs with minimum

Total domination in graphs with minimum degree three

✍ Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 3 views

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at leas

Total domination in 2-connected graphs a

Total domination in 2-connected graphs and in graphs with no induced 6-cycles

✍ Michael A. Henning; Anders Yeo 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

## Abstract A set __S__ of vertices in a graph __G__ is a total dominating set of __G__ if every vertex of __G__ is adjacent to some vertex in __S__. The minimum cardinality of a total dominating set of __G__ is the total domination number γ~t~(__G__) of __G__. It is known [J Graph Theory 35 (2000)

Infinite paths in planar graphs I: Graph

Infinite paths in planar graphs I: Graphs with radial nets

✍ Xingxing Yu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB 👁 1 views

## Abstract Let __G__ be an infinite 4‐connected planar graph such that the deletion of any finite set of vertices from __G__ results in exactly one infinite component. Dean __et al__. proved that either __G__ admits a radial net or a special subgraph of __G__ admits a ladder net, and they used the