Full domination in graphs

Robert C. Brigham; Gary Chartrand; Ronald D. Dutton; Ping Zhang

Discussiones Mathematicae Graph Theory (2001)

  • Volume: 21, Issue: 1, page 43-62
  • ISSN: 2083-5892

Abstract

top
For each vertex v in a graph G, let there be associated a subgraph H v of G. The vertex v is said to dominate H v as well as dominate each vertex and edge of H v . 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 γ F H ( G ) . A full dominating set of G of cardinality γ F H ( G ) is called a γ F H -set of G. We study three types of full domination in graphs: full star domination, where H v is the maximum star centered at v, full closed domination, where H v is the subgraph induced by the closed neighborhood of v, and full open domination, where H v is the subgraph induced by the open neighborhood of v.

How to cite

top

Robert C. Brigham, et al. "Full domination in graphs." Discussiones Mathematicae Graph Theory 21.1 (2001): 43-62. <http://eudml.org/doc/270252>.

@article{RobertC2001,
abstract = {For each vertex v in a graph G, let there be associated a subgraph $H_v$ of G. The vertex v is said to dominate $H_v$ as well as dominate each vertex and edge of $H_v$. 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 $H_v$ is the maximum star centered at v, full closed domination, where $H_v$ is the subgraph induced by the closed neighborhood of v, and full open domination, where $H_v$ is the subgraph induced by the open neighborhood of v.},
author = {Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {full domination; full star domination; full closed domination; full open domination; full domination number; full star domination number; full closed domination number; full open domination number},
language = {eng},
number = {1},
pages = {43-62},
title = {Full domination in graphs},
url = {http://eudml.org/doc/270252},
volume = {21},
year = {2001},
}

TY - JOUR
AU - Robert C. Brigham
AU - Gary Chartrand
AU - Ronald D. Dutton
AU - Ping Zhang
TI - Full domination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 1
SP - 43
EP - 62
AB - For each vertex v in a graph G, let there be associated a subgraph $H_v$ of G. The vertex v is said to dominate $H_v$ as well as dominate each vertex and edge of $H_v$. 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 $H_v$ is the maximum star centered at v, full closed domination, where $H_v$ is the subgraph induced by the closed neighborhood of v, and full open domination, where $H_v$ is the subgraph induced by the open neighborhood of v.
LA - eng
KW - full domination; full star domination; full closed domination; full open domination; full domination number; full star domination number; full closed domination number; full open domination number
UR - http://eudml.org/doc/270252
ER -

References

top
  1. [1] T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 2 (1959) 133-138. 
  2. [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
  4. [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. Zbl0733.05074
  5. [5] E. Sampathkumar and P.S. Neeralagi, The neighborhood number of a graph, Indian J. Pure Appl. Math. 16 (1985) 126-136. Zbl0564.05052
  6. [6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc. Providence, RI, 1962). 

NotesEmbed ?

top

You must be logged in to post comments.