✦ LIBER ✦

On the independent domination number of graphs with given minimum degree

✍ Scribed by N.I. Glebov; A.V. Kostochka

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 175 KB
Volume: 188
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00267-7

No coin nor oath required. For personal study only.

✦ Synopsis

We prove a new upper bound on the independent domination number of graphs in terms of the number of vertices and the minimum degree. This bound is slightly better than that of Haviland (1991) and settles the case 6 = 2 of the corresponding conjecture by Favaron (1988). @ 1998 Elsevier Science B.V. All rights reserved This last bound (if true), for every fixed positive integer 3, is attained on infinitely many graphs. Haviland [3] improved the bound of Favaron as follows: if 0 ~< 3 ~< (n-2)/7, then i(n,f)<..n + 33 -min{1 + 2x/3(n + 23 -2),2X/f(n + 93/4)}, and if (n -2 )/7 <~ 6 <~ n/4, then i(n, 3) <..2(n -3)/3.

📜 SIMILAR VOLUMES

On the domination number of Hamiltonian

On the domination number of Hamiltonian graphs with minimum degree six

✍ Hua-Ming Xing; Johannes H. Hattingh; Andrew R. Plummer 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 177 KB

The domination number of G, denoted by γ (G), is the minimum cardinality of a dominating set of G. We prove that if G is a Hamiltonian graph of order n with minimum degree at least six, then γ (G) ≤ 6n 17 .

The number of cutvertices in graphs with

The number of cutvertices in graphs with given minimum degree

✍ L.H. Clark; R.C. Entringer 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 453 KB

The maximum number of cutvertices in a connected graph of order n having minimum degree at least 6 is determined for 6 > 5.

The minimum spectral radius of graphs wi

The minimum spectral radius of graphs with a given independence number

✍ Mimi Xu; Yuan Hong; Jinlong Shu; Mingqing Zhai 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 221 KB

The minimum signless Laplacian spectral

The minimum signless Laplacian spectral radius of graphs with given independence number

✍ Ruilin Li; Jinsong Shi 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 307 KB

The independence number α(G) of G is defined as the maximum cardinality of a set of pairwise non-adjacent vertices which is called an independent set. In this paper, we characterize the graphs which have the minimum spectral radius among all the connected graphs of order n with independence number α

On the spectral radius of graphs with a

On the spectral radius of graphs with a given domination number

✍ Dragan Stevanović; Mustapha Aouchiche; Pierre Hansen 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 202 KB

On graphs with equal domination and inde

On graphs with equal domination and independent domination numbers

✍ Jerzy Topp; Lutz Volkmann 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 284 KB

Topp, J. and L. Volkmann, On graphs wi',h equal domination and independent domination number, Discrete Mathematics 96 (1991) 75-80. Allan and Laskar have shown that Kt.s-free graphs are graphs with equal domination and independent domination numbers. In this paper new classes of graphs with equal d