Domination in graphs of minimum degree four
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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. Reed [11] considered the domination problem for graphs with minimum degree at least three. He showed that any graph G of minimum degree at least three contains a dominating set D of size at most 3/8|V(G)| by introducing a covering by vertex disjoint paths. In this paper, by using this technique, we show that every graph on n vertices of minimum degree at least four contains a dominating set D of size at most 4/11|V(G)|.
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. Reed [11] considered the domination problem for graphs with minimum degree at least three. He showed that any graph G of minimum degree at least three contains a dominating set D of size at most 3/8|V(G)| by introducing a covering by vertex disjoint paths. In this paper, by using this technique, we show that every graph on n vertices of minimum degree at least four contains a dominating set D of size at most 4/11|V(G)|.
참고문헌 (13)
- N. Alon, "The Probabilistic Method" (1992), Wiley-Interscience
- Y. Caro, "On the vertex-independence number and star decomposition of graphs", Ars Combin., 20, pp.167~180 (1985)
- Y. Caro, "A note on the k-domination number of a graph", Internat. J. Math. Math. Sci., 13(1), pp.205~206 (1990)
- G. Chartrand, "Graphs and Digraphs, 3rd Edition" (1996), Chapman and Hall
- M. R. Garey, "Computers and intractability, A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences" (1979), W. H. Freeman and Co.
- T. W. Haynes, "Fundamentals of Domination in Graphs", Marcel Dekker, Inc. (1998)
- T. W. Haynes, "Domination in Graphs" (1998), Marcel Dekker, Inc.
- W. McCuaig, "Domination in graphs with minimum degree two", J. Graph Theory, 13(6), pp.749~762 (1989)
- O. Ore, "Theory of Graphs, American Mathematical Society Colloquium Publications", American Mathematical Society, Providence, R.I., ~ (1962)
- C. Payan, "Domination-balanced graphs", J. Graph Theory, 6(1), pp.23~32 (1982)
- B. A. Reed, "Paths, stars and the number three", Combin. Probab. Comput., 5(3), pp.277~295 (1996)
- Paths, stars and the number three: the grunge, "B. A. Reed", University of Waterloo, Technical Report, ~ (1993)
- L. A. Sanchis, "Bounds related to domination in graphs with minimum degree two", J. Graph Theory, 25(2), pp.139~152 (1997)