Domination in Graphs
of Minimum Degree Four
Sohn Moo Young and Xudong
Yuan
Department of Mathematics, Guangxi
Normal University,
Guilin 541004
P.R.China
Abstract
Let 
(G) denote the
minimum degree of graph G. An early result of Ore (see [5])
states that 
(G)
n/2 if G is a graph of order
$n$ with the minimum degree at least one. This result was improved
as (G) 2n/5 by McCraig and Shepherd in
[4] for the connected graph G which has minimum degree at
least two and is not one of seven exceptional graphs. Reed in
[7] considered the case for the graphs with minimum degree at
least three, and obtained that (G) 3n/8. In
this direction, an obvious conjecture (see [5]) seems to be
that for any graph G with (G)
k, (G)
kn/(3k-1). However, for (G)7, Caro and Roditty
(see [9, 10]) gave the following better bound.
Theorem 0.3. For any graph G,
Thus, the question remains open only for graphs G with 4
(G) 6. In this paper, by using the so-called vertex
disjoint paths cover introduced by Reed, we prove that every graph
on $n$ vertices of minimum degree at least four has a dominating
set of at most 4n/11 vertices.
References
1. G. Chartrand and L. lesniak,
Graphs and Digraphs, 3rd Edition, Chapman and Hall,
London, 1996.
2. T.W. Haynes, S.T. Hedetniemi, and P.J. Slater,
Fundamentals of Domination in Graphs, Marcel Dekker, New York,
1998.
3. T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (Eds),
Domination in Graphs: Advanced Topics, Marcel Dekker, New York,
1998.
4. W. McCuaig and B. Shepherd,
Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762.
5. O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ.,
Vol. 38, Amer. Math. Soc., Providence, RI, 1962.
6. C. Payan and N.H. Xuong, Domination-balanced graphs,
J. Graph Theory 6 (1982) 23--32.
7. B.A. Reed, Paths, stars and the number three,
Combin. Probab. Comput. 5 (1996) 277--295.
8. B.A. Reed, Paths, stars and the number three: the grunge. University of
Waterloo, Technical Report.
9. Y.Caro, Roditty, On the vertex-independence number and star decomposition of graphs,
Ars Combin. 20 (1985) 167--180.
10. Y.Caro, Roditty, A note On the k-domination number of a graph,
Internat. J. Math. Sci. 13 (1990) 205--206.
11. L.A. Sanchis, Bounds related to domination in graphs with minimum degree two,
J. Graph theory 25 (1997) 139--152.
12. M.R. Garey and D.S. Johnson,
Computers and Intractability: A Guide to the Theory of
NP-Completeness, W.H.Freeman, San Franciso, 1979.
