DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

DOI 10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2017: 0.601

SCImago Journal Rank (SJR) 2017: 0.633

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 43-62
DOI: 10.7151/dmgt.1132

FULL DOMINATION IN GRAPHS

Robert C. Brigham

Department of Mathematics
University of Central Florida, Orlando, FL 32816

Gary Chartrand

Department of Mathematics and Statistics
Western Michigan University, Kalamazoo, MI 49008

Ronald D. Dutton

Program of Computer Science
University of Central Florida, Orlando, FL 32816

Ping Zhang

Department of Mathematics and Statistics
Western Michigan University, Kalamazoo, MI 49008

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