Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T10:38:18.786Z Has data issue: false hasContentIssue false
  • English
  • Français

Paths, Stars and the Number Three

Published online by Cambridge University Press:  12 September 2008

Bruce Reed
Bruce Reed
Affiliation:
Equipe Combinatoire, Institute Blaise Pascal, Université Paris VI, 4 Place Jussieu, Paris 75252, Cedex 05, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A dominating set for a graph G is a set D of vertices of G such that every vertex of G not in D is adjacent to a vertex of D. We prove that any graph G of minimum degree at least three contains a dominating set D of size at most 3|V(G)|/8. A star S is a graph consisting of a centre x and a set of edges from x to S — x. Clearly, a dominating set D for a graph G corresponds to a set of |D| stars which cover V(G). Thus, we show that the vertices of any graph G of minimum degree 3 can be covered by at most 3|V(G)|/8 vertex disjoint stars. We also show that any connected cubic graph G can be covered by [|V(G)|/9] vertex disjoint paths. Both these results are sharp.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 3 , September 1996 , pp. 277 - 295
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Arnautov, V. I. (1974) Estimation of the external stability number of a graph by means of the minimal degree of the vertices. Prikl. Mat. i Programmirovanie Vyp. 11 3–8.Google Scholar
[2]Blank, M. (1973) An estimate of the external stability number of a graph without suspended vertices. Prikl. Math, i Programmirovanie Vyp. 10 3–11.Google Scholar
[3]Cockayne, E. J. and Hedetnemie, S. T. (1977) Towards a theory of domination in graphs. Networks 7 241–261.CrossRefGoogle Scholar
[4]Edmonds, J. (1964) Paths, trees and flowers. Can. J. Math. 17 449–467.CrossRefGoogle Scholar
[5]Lovász, L. (1975) On the ratio of optimal integral and fractional covers. Discrete Mathematics 13 383–390.CrossRefGoogle Scholar
[6]McCuaig, B. and Shepherd, B. (1989) Domination in graphs of minimum degree two. Journal of Graph Theory 13 749–762.CrossRefGoogle Scholar
[7]Payan, C. (1975) Sur la Nombre d'Absorption d'un Graphe Simple. Cahiers C.E.R.O. 17 307–317.Google Scholar
[8]Reed, B. (1993) Paths, stars and the number three: the grunge. University of Waterloo, Technical Report.Google Scholar