Geodesic
The diameter of paired-domination vertex critical graphs
Czechoslovak Mathematical Journal, Tome 58 (2008) no. 4, pp. 887-897 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks {\it 32} (1998), 199--206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$, denoted by $\gamma _{{\rm pr}}(G)$, is the minimum cardinality of a paired-dominating set of $G$. The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of degree one, $\gamma _{{\rm pr}}(G - v) \gamma _{{\rm pr}}(G)$. We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least $\frac 32(\gamma _{{\rm pr}}(G) - 2)$. For $\gamma _{{\rm pr}}(G) \le 8$, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.
In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks {\it 32} (1998), 199--206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$, denoted by $\gamma _{{\rm pr}}(G)$, is the minimum cardinality of a paired-dominating set of $G$. The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of degree one, $\gamma _{{\rm pr}}(G - v) \gamma _{{\rm pr}}(G)$. We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least $\frac 32(\gamma _{{\rm pr}}(G) - 2)$. For $\gamma _{{\rm pr}}(G) \le 8$, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.
Classification : 05C12, 05C35, 05C69
Keywords: paired-domination; vertex critical; bounds; diameter 
@article{CMJ_2008_58_4_a1,
     author = {Henning, Michael A. and Mynhardt, Christina M.},
     title = {The diameter of paired-domination vertex critical graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {887--897},
     year = {2008},
     volume = {58},
     number = {4},
     mrnumber = {2471154},
     zbl = {1174.05093},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Mynhardt, Christina M.
TI  - The diameter of paired-domination vertex critical graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2008
SP  - 887
EP  - 897
VL  - 58
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/
LA  - en
ID  - CMJ_2008_58_4_a1
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Mynhardt, Christina M.
%T The diameter of paired-domination vertex critical graphs
%J Czechoslovak Mathematical Journal
%D 2008
%P 887-897
%V 58
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/
%G en
%F CMJ_2008_58_4_a1
Henning, Michael A.; Mynhardt, Christina M. The diameter of paired-domination vertex critical graphs. Czechoslovak Mathematical Journal, Tome 58 (2008) no. 4, pp. 887-897. http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/