The diameter of paired-domination vertex critical graphs

Title:

The diameter of paired-domination vertex critical graphs

Creator:

Henning, Michael A. and Mynhardt, Christina M.

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:880d1f39-8f4e-4ee0-b3b5-dfb2d86fc3a9
uuid:880d1f39-8f4e-4ee0-b3b5-dfb2d86fc3a9

Subject:

paired-domination, vertex critical, bounds, and diameter

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

887-897

Source:

Czechoslovak Mathematical Journal | 2008 Volume:58 | Number:4

Harvested from:

CDK

Metadata only:

false