An upper bound on the domination number of a graph with minimum degree 2 |
| |
Authors: | Allan Frendrup Bert Randerath |
| |
Institution: | a Department of Mathematical Sciences, Aalborg University, DK-9220 Aalborg East, Denmark b School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa c Institut für Informatik, Universität zu Köln, D-50969 Köln, Germany |
| |
Abstract: | A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let Pn and Cn denote a path and a cycle, respectively, on n vertices. Let k1(F) and k2(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P3,P4,P5,C5} and {P1,P2}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then . |
| |
Keywords: | Bounds Path-component Domination number |
本文献已被 ScienceDirect 等数据库收录! |
|