Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

04.05.2019

A new lower bound on the domination number of a graph

Zeitschrift:
Journal of Combinatorial Optimization
Autoren:
Majid Hajian, Michael A. Henning, Nader Jafari Rad
Wichtige Hinweise
Michael A. Henning: Research supported in part by the South African National Research Foundation and the University of Johannesburg.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The domination number, \(\gamma (G)\), of G is the minimum cardinality of a dominating set of G. Lemańska (Discuss Math Graph Theory 24:165–170, 2004) showed that if T is a tree of order \(n \ge 2\) with \(\ell \) leaves, then \(\gamma (T) \ge (n-\ell +2)/3\), and characterized all trees achieving equality in this bound. In this paper, we first characterize all trees T of order n with \(\ell \) leaves satisfying \(\gamma (T) = \lceil (n - \ell + 2)/3 \rceil \). We then generalize this result to connected graphs and show that if G is a connected graph of order \(n \ge 2\) with \(k \ge 0\) cycles and \(\ell \) leaves, then \(\gamma (G) \ge \lceil (n-\ell +2 - 2k)/3 \rceil \). We also characterize the graphs G achieving equality for this new bound.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​​​​​​​​

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

    Bildnachweise