Previous |  Up |  Next

Article

Keywords:
dominating set; induced-paired dominating set; induced-paired domatic number
Summary:
A subset $D$ of the vertex set $V(G)$ of a graph $G$ is called dominating in $G$, if each vertex of $G$ either is in $D$, or is adjacent to a vertex of $D$. If moreover the subgraph $<D>$ of $G$ induced by $D$ is regular of degree 1, then $D$ is called an induced-paired dominating set in $G$. A partition of $V(G)$, each of whose classes is an induced-paired dominating set in $G$, is called an induced-paired domatic partition of $G$. The maximum number of classes of an induced-paired domatic partition of $G$ is the induced-paired domatic number $d_{\text{ip}}(G)$ of $G$. This paper studies its properties.
References:
[1] E. J. Cockayne, S. T. Hedetniemi: Towards a theory of domination in graphs. Networks 7 (1977), 247–261. MR 0483788
[2] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. MR 1605684
[3] D. S. Studer, T. W. Haynes, L. M. Lawson: Induced-paired domination in graphs. Ars Combinatoria 57 (2000), 111–128. MR 1796633
[4] B. Zelinka: Adomatic and idomatic numbers of graphs. Math. Slovaca 33 (1983), 99–103. MR 0689285 | Zbl 0507.05059
Partner of
EuDML logo