DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

N. Ananchuen, P. Kaemawichanurat

Title:

Connected domination critical graphs with cut vertices

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-12-12, Revised: 2018-06-26, Accepted: 2018-06-26, https://doi.org/10.7151/dmgt.2163

Abstract:

A graph $G$ is said to be $k$-$\gamma_{c}$-critical if the connected domination number of $G$, $\gamma_{c}(G)$, is $k$ and $\gamma_{c}(G + uv)<k$ for any pair of non-adjacent vertices $u$ and $v$ of $G$. Let $G$ be a $k$-$\gamma_{c}$-critical graph and $\zeta(G)$ the number of cut vertices of $G$. It was proved, in \cite{A, PKNA}, that, for $3 \leq k \leq 4$, every $k$-$\gamma_{c}$-critical graph satisfies $\zeta(G) \leq k - 2$. In this paper, we generalize that every $k$-$\gamma_{c}$-critical graph satisfies $\zeta(G) \leq k - 2$ for all $k \geq 5$. We also characterize all $k$-$\gamma_{c}$-critical graphs when $\zeta(G)$ is achieving the upper bound.

Keywords:

connected domination, critical

PDF
Close