Discussiones
Mathematicae Graph Theory 21(1) (2001) 43-62
DOI: https://doi.org/10.7151/dmgt.1132
FULL DOMINATION IN GRAPHS
Robert C. Brigham Department of Mathematics |
Gary Chartrand Department of Mathematics and Statistics |
Ronald D. Dutton Program of Computer Science |
Ping Zhang Department of Mathematics and Statistics |
Abstract
For each vertex v in a graph G, let there be associated a subgraph Hv of G. The vertex v is said to dominate Hv as well as dominate each vertex and edge of Hv. A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number γFH(G). A full dominating set of G of cardinality γFH(G) is called a γFH-set of G. We study three types of full domination in graphs: full star domination, where Hv is the maximum star centered at v, full closed domination, where Hv is the subgraph induced by the closed neighborhood of v, and full open domination, where Hv is the subgraph induced by the open neighborhood of v.
Keywords: full domination, full star domination, full closed domination, full open domination.
2000 Mathematics Subject Classification: 05C12.
References
[1] | T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 2 (1959) 133-138. |
[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, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). |
[4] | S.R. Jayaram, Y.H.H. Kwong and H.J. Straight, Neighborhood sets in graphs, Indian J. Pure Appl. Math. 22 (1991) 259-268. |
[5] | E. Sampathkumar and P.S. Neeralagi, The neighborhood number of a graph, Indian J. Pure Appl. Math. 16 (1985) 126-136. |
[6] | O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc. Providence, RI, 1962). |
Received 5 July 2000
Revised 17 October 2000
Close