
























A graph $G$ is said to be $k$-$γ_{c}$-critical if the connected domination number $γ_{c}(G)$ is equal to $k$ and $γ_{c}(G + uv) < k$ for any pair of non-adjacent vertices $u$ and $v$ of $G$. Let $ζ$ be the number of cut vertices of $G$ and let $ζ_{0}$ be the maximum number of cut vertices that can be contained in one block. For an integer $\ell \geq 0$, a graph $G$ is $\ell$-factor critical if $G - S$ has a perfect matching for any subset $S$ of vertices of size $\ell$. It was proved that, for $k \geq 3$, every $k$-$γ_{c}$-critical graph has at most $k - 2$ cut vertices and the graphs with maximum number of cut vertices were characterized. It was proved further that, for $k \geq 4$, every $k$-$γ_{c}$-critical graphs satisfies the inequality $ζ_{0}(G) \le \min \left\{ \left\lfloor \frac{k + 2}{3} \right\rfloor, ζ\right\}$. In this paper, we characterize all $k$-$γ_{c}$-critical graphs having $k - 3$ cut vertices. Further, we establish realizability that, for given $k \geq 4$, $2 \leq ζ\leq k - 2$ and $2 \leq ζ_{0} \le \min \left\{ \left\lfloor \frac{k + 2}{3} \right\rfloor, ζ\right\}$, there exists a $k$-$γ_{c}$-critical graph with $ζ$ cut vertices having a block which contains $ζ_{0}$ cut vertices. Finally, we proved that every $k$-$γ_{c}$-critical graph of odd order with minimum degree two is $1$-factor critical if and only if $1 \leq k \leq 2$. Further, we proved that every $k$-$γ_{c}$-critical $K_{1, 3}$-free graph of even order with minimum degree three is $2$-factor critical if and only if $1 \leq k \leq 2$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。