ArticleOriginal scientific text

Title

Full domination in graphs

Authors 1, 2, 3, 2

Affiliations

  1. Department of Mathematics, University of Central Florida, Orlando, FL 32816
  2. Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008
  3. Program of Computer Science, University of Central Florida, Orlando, FL 32816

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

Bibliography

  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).
Pages:
43-62
Main language of publication
English
Received
2000-07-05
Accepted
2000-10-17
Published
2001
Exact and natural sciences