๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Independent domination in regular graphs

โœ Scribed by Julie Haviland

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
387 KB
Volume
143
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let G be a simple graph of order n. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. Motivated by work of Cockayne et al. (1991) and Cockayne and Mynhardt (1989), we investigate the maximum value of the product of the independent domination numbers of a graph and its complement, as a function of n. In particular we prove that if G is regular then i(G). i(G) < (n + 14)2/12.68.

๐Ÿ“œ SIMILAR VOLUMES

Independent Dominating Sets and a Second
Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs
โœ Carsten Thomassen ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Signed domination in regular graphs
Signed domination in regular graphs
โœ Odile Favaron ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 456 KB

In answer to the open questions proposed by Henning and Slater, we give sharp upper bounds on the upper signed domination number of a regular graph and on the signed domination number of a connected cubic graph. Let G = (V, E) be a simple graph. For v E V, we denote by d(u) the degree of v in V, by

Minus domination in regular graphs
Minus domination in regular graphs
โœ Jean Dunbar; Stephen Hedetniemi; Michael A. Henning; Alice A. McRae ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 77 KB
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.