The relationship of sea level changes to climatic change in northeast Asia and northern North America during the last 75 ka B.P.

1.   Introduction

All graphs considered in this paper are finite, undirected and simple. Let $G$ be a graph with vertex-set $V(G)$ and edge-set $E(G)$. A subset $D$ of $V(G)$ is called a dominating set of $G$ if every vertex of $G$ is either in $D$ or adjacent to a vertex of $D$. The domination number $\gamma(G)$ is the cardinality of a minimum dominating set of $G$.

The domination in graphs is so classic that it has been widely studied in networks theory, while the decision problem for the domination number of a general graph was proved to be NP-complete ^[8]. On the study of domination, there are three early textbooks compiled by Haynes et al. ^[13,14] and Henning et al. ^[17]. Recently, Haynes, Hedetniemi and Henning ^[11,12] edited two new books on this field once again.

Definition 1.1. ^[24] (1) A vertex $v\in V(G)$ is called $\gamma$-fixed if $v$ belongs to every minimum dominating set of $G$. (2) A vertex $v\in V(G)$ is called $\gamma$-bad if $v$ does not belong to any minimum dominating set of $G$. (For simplicity, we abbreviate "$\gamma$-fixed" and "$\gamma$-bad" to "fixed" and "bad" respectively in this paper.)

Definition 1.2. A vertex $v\in V(G)$ is called critical if $\gamma(G-v) < \gamma(G)$. In particular, we agree that the single vertex of a trivial graph is critical.

Remark for Definition 1.2: It is easy to see that $\gamma(G-v) < \gamma(G)\Leftrightarrow\gamma(G-v)\leq\gamma(G)-1\Leftrightarrow\gamma(G-v) = \gamma(G)-1$, where $\gamma(G-v)\leq\gamma(G)-1\Rightarrow \gamma(G-v) = \gamma(G)-1$ holds because if not so, then $\gamma(G-v)\leq\gamma(G)-2$, and thus $G$ would have a dominating set with cardinality $\big((\gamma(G)-2)+|v|\big) < \gamma(G)$, contradicting the minimality of $\gamma(G)$.

The terms of fixed and bad vertices of graphs were introduced by Samodivkin ^[24], which can help us to research the constructions of minimum dominating sets of a graph better and shorten the processes of our proofs ^[7,22,24,25]. (In ^[28], fixed and bad vertices of a graph are also called universal and idle vertices, respectively.) The notions of domination critical, which include vertex-critical ^[4] and edge-critical ^[3,27], are very important to domination of graphs. But in this paper, we are not going to discuss the topic of edge-critical.

Definition 1.3. A graph $G$ is called vertex-critical if every vertex of $G$ is critical.

There are lots of nice properties on domination vertex-critical graphs ^{[1,2,19,29,30]}. Many of them possess symmetry, and even vertex-transitivity. For example, the graph $C_4\cdot C_4$ obtained by identifying two vertices of two cycles of orders four, the Harary graph $H_{3, 8}$ and the circulant graph $C_{12}\langle1, 5\rangle$ (See Figure 1.).

Figure 1.  Three examples of vertex-critical graph.

DownLoad: Full-Size Img PowerPoint

Trees is a kind of basic graph class often applied to algorithm design. There are a good few results on the study of the constructions for special trees, such as trees with equal domination and total domination numbers ^[7], trees with equal domination and restrained domination numbers ^[6], trees with equal total domination and disjunctive domination numbers ^[18], trees with equal independent domination and weak domination numbers ^[10], trees with a minimum vertex cover also being a minimum total dominating set ^[5], trees with two disjoint minimum independent dominating sets ^[15], trees with the paired domination number being twice the matching number ^[26], trees without fixed vertices ^[31], trees without fixed vertices and critical vertices ^[23,16], trees with unique minimum dominating sets ^[9,34], trees with equal Roman $\{2\}$-domination and Roman domination numbers ^[21], and trees with total Roman domination number being equal to the sum of domination number and semitotal domination number ^[20].

Naturally, there are two such questions: Can we exhaustively characterize vertex-critical graphs, as well as graphs without critical vertices? It seems not easy to solve these two questions. Therefore, in this paper, we study on the latter one and focus on the graph class-trees. Via defining 3 operations of graphs, we get a constructive characterization of trees without critical vertices.

2.   Preliminary

2.1.   Notations and terminologies

For any $u, v\in V(G)$, denote by $d_G(u, v)$ the distance from $u$ to $v$ in $G$ as well as $d_G(v)$, $N_{G}(v)$, $N_{G}[v]$ and $N^{2}_{G}(v)$ the degree, open neighborhood, closed neighborhood and $2$-open neighborhood of vertex $v$ in $G$ respectively, where the $2$-open neighborhood of vertex $v$ in $G$ is defined as $N^{2}_{G}(v) = \{x\in V(G)\mid d(x, v) = 2\}$. For any $\emptyset\neq X\subseteq V(G)$, let $G[X]$ denote the subgraph of $G$ induced by $X$.

Denote by $\underline{MDS}(G)$ the set composed of all the minimum dominating sets of $G$. That is, $\underline{MDS}(G) = \{D \mid D$ is a minimum dominating set of $G\}$. A vertex of degree one (resp. degree zero) in $G$ is called an end-vertex (resp. isolated vertex) of $G$. Let $g$ be a cut-vertex of $G$. If a component $P$ of $G-g$ is a path and $g$ is adjacent to an end-vertex of $P$ in $G$, then we call $P$ as a pendant path of $G$ and say that $g$ and $P$ are linked with each other. A pendant path of $G$ with order $l$ ($l\geq1$) is called an $l$-pendant path of $G$. Let $P_{2k+1} = v_{1}v_{2}\cdots v_{2k+1}$ be a path of order $2k+1$. Then $v_{k+1}$ is the center of $P_{2k+1}$.

Let $r$ be a vertex, $l$ and $m$ be two non-negative integers with $l+m\geq1$. Let $P_{3}^{1}\cong P_{3}^{2} \cong\cdots \cong P_{3}^{l} \cong P_3$ with $P_{3}^{i} = v_iu_iw_i$, $i = 1, 2, \ldots, l$, and $P_{2}^{1}\cong P_{2}^{2} \cong\cdots \cong P_{2}^{m} \cong P_2$ with $P_{2}^{j} = x_jy_j$, $j = 1, 2, \ldots, m$. For every $1\leq i\leq l$, link $r$ and $u_i$ by an edge. For every $1\leq j\leq m$, link $r$ and $x_j$ by an edge. Denote the resulting graph as $R_{l, m}$ and call $r$ as the root of $R_{l, m}$ (See Figure 2).

Figure 2.  The graph $R_{l, m}$.

DownLoad: Full-Size Img PowerPoint

2.2.   Some useful results

Now, we give three observations and some known lemmas, which will support our proofs in the next section.

Observation 2.1. Let $G$ be a graph. If $G_1$ and $G_2$ are vertex-induced subgraphs of $G$ such that $V(G) = V(G_1)\cup V(G_2)$, then $\gamma(G)\leq \gamma(G_1)+\gamma(G_2)$ with the equality holding when $G_1$ and $G_2$ are two components of $G$.

Observation 2.2. Let $u\in V(G)$. If $u$ is adjacent to two end-vertices $v$ and $w$ in $G$, then $v$ and $w$ are bad in $G$, and $u$ is fixed in $G$.

Observation 2.3. Let $u$ be an end-vertex of $G$ with $N_G(u) = \{v\}$. Then $u$ is non-fixed and $v$ is non-bad in $G$, and $|\{u, v\}\cap D| = 1$ for any $D\in\underline{MDS}(G)$.

Lemma 2.4. ^[3] For any nontrivial tree $T$ and any $v\in V(T)$, $v$ is a fixed vertex of $T$ if and only if $\gamma(T-v) > \gamma(T)$.

Lemma 2.5. ^[32] Let $G$ be a graph with minimum degree at least one. If $x$ is a bad or fixed vertex of $G$, then all the elements of $N_G[x]$ are non-critical vertices of $G$.

Lemma 2.6. ^[33] Let $G$ be a graph.

(a) If $x$ is a non-fixed vertex of $G$, then $\gamma(G-x)\leq\gamma(G)$.

(b) If $x$ is a bad vertex of $G$, then $\gamma(G-x) = \gamma(G)$.

(c) If $x$ is a non-fixed and non-critical vertex of $G$, then $\gamma(G-x) = \gamma(G)$.

Lemma 2.7. ^[34] Let $T$ be a tree containing only one vertex $u$ of degree at least $3$. Then $u$ is linked with $|N_T(u)|$ pendant paths in $T$.

Lemma 2.8. ^[34] Let $T$ be a tree with at least two vertices of degree at least $3$ and let $d_T(u, v) = \rm{max}\{d_T(x, y)\; |$ both $x$ and $y$ are vertices of degree at least $3$ in $T$$\}$. Then $u$ is linked with $|N_T(u)|-1$ pendant paths in $T$.

Lemma 2.9. ^[34] Let $G_0$ be a graph without any isolated vertices and possessing a fixed vertex. If $G$ is a graph obtained via linking a fixed vertex of $G_0$ and the single vertex of $P_1$ by an edge, then $\gamma(G) = \gamma(G_0)$.

Lemma 2.10. ^[34] Let $G_0$ be a graph without any isolated vertices and possessing a fixed vertex. If $G$ is a graph obtained via linking a fixed vertex of $G_0$ and the center of $P_3$ by an edge, then $\gamma(G) = \gamma(G_0)+1$.

3.   Trees without critical vertices

3.1.   Nontrivial vertex-critical trees do not exist

We now ask a question: Is there a nontrivial tree only containing critical vertices? Unluckily, the answer to this question is no (See Lemma 3.1).

Lemma 3.1. If $d_G(u) = 1$ and $v\in N_G(u)\cup N^{2}_G(u)$, then $v$ is a non-critical vertex of $G$.

Proof. Suppose to the contrary that $v$ is a critical vertex of $G$. If $v\in N_G(u)$, let $D_1\in \underline{MDS}(G-v)$. Then by Definition 1.2, we have $|D_1| = \gamma(G)-1$. Since $u$ is an isolated vertex of $G-v$, it follows that $u$ is fixed in $G-v$. Now, if we let $D_2 = (D_1-\{u\})\cup \{v\}$, then $D_2$ is a dominating set of $G$ with $|D_2| = |D_1| = \gamma(G)-1$, a contradiction.

If $v\in N^{2}_G(u)$, then $|D^{\prime}| = \gamma(G)-1$ for any $D^{\prime}\in \underline{MDS}(G-v)$. Let $N_G(u) = \{w\}$. Since $u$ is still an end-vertex of $G-v$, it follows from Observation 2.3 that $w$ is a non-bad vertex of $G-v$. Let $D^{\prime}_1\in \underline{MDS}(G-v)$ with $w\in D^{\prime}_1$. On one hand, we have $|D^{\prime}_1| = \gamma(G)-1$. But on the other hand, $D^{\prime}_1$ is also a dominating set of $G$, which implies that $|D^{\prime}_1|\geq\gamma(G)$, a contradiction.

Lemma 3.1 tells us that if $G$ is nontrivial and has an end-vertex, then $G$ must have a non-critical vertex. Therefore, a tree is vertex-critical if and only if it is trivial.

3.2.   To get larger graphs without critical vertices via operations of graphs

In this subsection, via several operations of graphs, we can get large graphs without critical vertices from small graphs without critical vertices step by step. In particular, these processes of operations are reversible for trees. (Here, large graph represents graph with large order while small graph represents graph with small order.) For a graph $G_0$, we define the following three operations.

Operation i. Link a fixed vertex of $G_0$ and the single vertex of $P_{1}$ by an edge. Denote the resulting graph by $G_0\negthinspace\backsim\negthinspace P_{1}$. (Refer to Figure 3 (i)).

Figure 3.  Examples of $G_0\negthinspace\backsim \negthinspace P_{1}$, $G_0\negthinspace\backsim\negthinspace P_{3}$ and $G_0\negthinspace\backsim \negthinspace R_{l, m}$.

DownLoad: Full-Size Img PowerPoint

Operation ii. Link a fixed vertex of $G_0$ and the center of $P_{3}$ by and edge. Denote the resulting graph by $G_0\negthinspace\backsim\negmedspace P_{3}$. (Refer to Figure 3 (ii)).

Operation iii. Link an arbitrary vertex of $G_0$ and the root of $R_{l, m}$ by and edge. Denote the resulting graph by $G_0\negthinspace\backsim\negthinspace R_{l, m}$. (Refer to Figure 3 (iii)).

Remark. In fact, the resulting graph may be not unique. So, "$G = G_0 \negthinspace\backsim \negthinspace P_{1}$" means that "$G$ is obtained from $G_0$ by Operation i".

Lemma 3.2. Let $G_0$ be a graph without any isolated vertices and possessing a fixed vertex, and let $G = G_0 \negthinspace\backsim\negthinspace P_{1}$. Then all the vertices of $G_0$ are non-critical if and only if all the vertices of $G$ are non-critical.

Proof. $(\Rightarrow)$ Suppose that $V(P_1) = \{v_1\}$ and $gv_1\in E(G)$. From Lemma 2.9, we have $\gamma(G) = \gamma(G_0) = \gamma(G-v_1)$. So by Definition 1.2, $v_1$ is a non-critical vertex of $G$. Also, we have $g$ is a non-critical vertex of $G$ by Lemma 3.1. It remains to prove that $x$ is a non-critical vertex of $G$ for every $x\in V(G-v_1-g)\subseteq V(G_0)$. Since all the vertices of $G_0$ are non-critical, we have $\gamma(G_0-x)\geq\gamma(G_0)$. Since $d_{G-x}(v_1) = 1$, we have $v_1$ is a non-fixed vertex of $G-x$ by Observation 2.3. So there exists $D_x^{-}\in \underline{MDS}(G-x)$ such that $v_1\notin D_x^{-}$, and then $g\in D_x^{-}$. Thus $D_x^{-}\cap V(G_0-x)$ is a dominating set of $G_0-x$. Hence $\gamma(G-x) = |D_x^{-}| = |D_x^{-}\cap V(G_0-x)|\geq \gamma(G_0-x)\geq\gamma(G_0) = \gamma(G)$, which implies that $x$ is a non-critical vertex of $G$. The necessity follows.

$(\Leftarrow)$ Assume to the contrary that $G_0$ has a critical vertex $y_0$. Since all the vertices of $G$ are non-critical, we have $\gamma(G-y_0)\geq\gamma(G)$. Let $D_0^{-}\in \underline{MDS}(G_0-y_0)$. Then $|D_0^{-}\cup\{y_0\}| = \gamma(G_0-y_0)+1 = \gamma(G_0)$, which implies that $D_0^{-}\cup\{y_0\}\in \underline{MDS}(G_0)$. By the definition of Operation i, $g$ is a fixed vertex of $G_0$. So we have $g\in D_0^{-}\cup\{y_0\}$, and $g$ is a non-critical vertex of $G_0$ by Lemma 2.5. Thus $g\neq y_0$, and therefore $g\in D_0^{-}$, which implies that $D_0^{-}$ is a dominating set of $G-y_0$. Hence $\gamma(G_0-y_0) = |D_0^{-}|\geq\gamma(G-y_0)\geq\gamma(G) = \gamma(G_0)$, which contradicts the assumption that $y_0$ is a critical vertex of $G_0$. The sufficiency follows.

Lemma 3.3. Let $G_0$ and $W$ be two graphs. Let $G$ be a graph obtained via linking an arbitrary vertex of $G_0$ and an arbitrary vertex of $W$ by an edge. If $\gamma(G) = \gamma(G_0)+\gamma(W)$ and all the vertices of $G$ are non-critical, then all the vertices of $G_0$ are non-critical.

Proof. For any $y\in V(G_0)$, since all the vertices of $G$ are non-critical, it follows that $\gamma(G-y)\geq \gamma(G)$. By Observation 2.1, we have $\gamma(G_0-y)+\gamma(W)\geq\gamma(G-y)\geq \gamma(G) = \gamma(G_0)+\gamma(W)$. Thus $\gamma(G_0-y)\geq\gamma(G_0)$, and so $y$ is a non-critical vertex of $G_0$. The lemma follows.

Lemma 3.4. Let $G_0$ be a graph without isolated vertices and possessing a fixed vertex, and $G = G_0\negthinspace\backsim\negmedspace P_{3}$.

$\rm{(a)}$ If all the vertices of $G$ are non-critical, then all the vertices of $G_0$ are non-critical.

$\rm{(b)}$ When $G_0$ is a tree, $\rm{(}$in order to avoid confusion, $\rm{)}$ we rewrite $T_0 = G_0$ and $T = G$. If all the vertices of $T_0$ are non-critical, then all the vertices of $T$ are non-critical.

Proof. (a) Suppose that $P_3 = v_1v_2v_3$ and $E(G)-E(G_0)-E(P_3) = \{gv_2\}$. Then $g$ is fixed in $G_0$. From Lemma 2.10, we get $\gamma(G) = \gamma(G_0)+1$. Item (a) follows by Lemma 3.3.

(b) Firstly, by Observation 2.2, $v_2$ is a fixed vertex of $T$. So by Lemma 2.5, $v_1, v_2$, $v_3$ and $g$ are non-critical vertices of $T$.

Secondly, we need to show that $x$ is a non-critical vertex of $T$ for every $x\in V(T-g)-V(P_3)$. That is, to prove $\gamma(T-x)\geq\gamma(T)$. Since $T_0$ has no critical vertices, we have $\gamma(T_0-x)\geq\gamma(T_0)$. Let $D_{x}^{-}\in \underline{MDS}(T-x)$. If $g\in D_{x}^{-}$, then $D_{x}^{-}\cap V(T_0-x)$ is a dominating set of $T_0-x$, and so $\gamma(T-x) = |D_{x}^{-}| = |D_{x}^{-}\cap V(T_0-x)|+|\{v_2\}|\geq \gamma(T_0-x)+1\geq\gamma(T_0)+1 = \gamma(T)$. If $g\notin D_{x}^{-}$, then $\big(D_{x}^{-}\cap V(T_0-x)\big)\cup\{x\}$ is a dominating set of $T_0-g$. By Lemma 2.4, we have $|\big(D_{x}^{-}\cap V(T_0-x)\big)\cup\{x\}|\geq\gamma(T_0-g)\geq\gamma(T_0)+1$, which implies that $|D_{x}^{-}\cap V(T_0-x)|\geq\gamma(T_0)$. So $\gamma(T-x) = |D_{x}^{-}| = |D_{x}^{-}\cap V(T_0-x)|+|\{v_2\}|\geq \gamma(T_0)+1 = \gamma(T)$. Item (b) follows.

Note. In Lemma 3.4 (b), we restrict $G_0$ to be a tree because if $G_0$ is a general graph, then the result maybe not true. (See the following Example 3.5).

Example 3.5. Define $G_0$ and $G$ as shown in Figure 4. Then $G = G_0\negthinspace\backsim\negmedspace P_{3}$. It is not hard to check that $\gamma(G_0) = 2$, $h_1$ and $g$ are fixed vertices of $G_0$, as well as $w_1, u_1, u_2, u_3, u_4$ and $h_2$ are bad vertices of $G_0$. By Lemma 2.5, $G_0$ has no critical vertices. However, since $\gamma(G) = \gamma(G_0)+1 = 3$, we can see that $\{h_2, v_2\}\in \underline{MDS}(G-w_1)$, which implies that $w_1$ is a critical vertex of $G$.

Figure 4.  Sketch of Example 3.5.

DownLoad: Full-Size Img PowerPoint

Lemma 3.6. Let $G_0$ be a graph and $G = G_0\negthinspace\backsim\negthinspace R_{l, m}$. Then

$\rm{(a)}\; \gamma(G) = \gamma(G_0)+(l+m)$;

$\rm{(b)}$ all the vertices of $G_0$ are non-critical if and only if all the vertices of $G$ are non-critical.

Proof. Suppose that $E(G)-E(G_0)-E(R_{l, m}) = \{gr\}$. Set $U = \{u_1, u_2, \ldots, u_l\}$, $X = \{x_1, x_2, \ldots, \; x_m\}$, $Y = \{y_1, y_2, \ldots, y_m\}$ and $Z = X\cup Y$.

(a) We can easily see that $\gamma(R_{l, m}) = l+m$. So $\gamma(G)\leq\gamma(G_0)+(l+m)$. It remains to prove $\gamma(G)\geq\gamma(G_0)+(l+m)$. Let $D\in \underline{MDS}(G)$. If $D\cap V(G_0)$ can dominate $g$ in $G$, then $D\cap V(G_0)$ is a dominating set of $G_0$, and so $|D|\geq|D\cap V(G_0)|+|U|+|D\cap Z|\geq\gamma(G_0)+(l+m)$; if not, then $r\in D$ and $\big(D\cap V(G_0)\big)\cup\{g\}$ is a dominating set of $G_0$, and so $|D| = |D\cap V(G_0)|+|\{r\}|+|U|+|D\cap Z| = |\big(D\cap V(G_0)\big)\cup\{g\}|+(l+m)\geq\gamma(G_0)+(l+m)$.

(b) $(\Leftarrow)$ The sufficiency follows immediately by Item (a) and Lemma 3.3.

$(\Rightarrow)$ We claim that $r$ is a bad vertex of $G$. Otherwise, let $D_{r}\in \underline{MDS}(G)$ with $r\in D_r$. If $g\in D_r$, then $D_r-\{r\}$ is a dominating set of $G$, contradicting the minimality of $|D_r|$. So we have $g\notin D_r$, and then $D_r\cap V(G_0)$ is a dominating set of $G_0-g$. Thus $\gamma(G_0-g)\leq|D_r\cap V(G_0)| = |D_r|-|U|-|D_r\cap Z|-|\{r\}| = \gamma(G)-(l+m)-1 = \gamma(G_0)-1$, which implies that $g$ is a critical vertex of $G_0$, contradicting the known condition that $G_0$ has no critical vertices.

Now firstly, for every $1\leq i\leq l$ and every $1\leq j\leq m$, we have $u_i, v_i, w_i, r, g$ and $x_j$ are non-critical vertices of $G$ by Lemma 2.5.

Secondly, if there exists some $1\leq j^{\prime}\leq m$ such that $\gamma(G-y_{j^{\prime}}) = \gamma(G)-1$, we can let $D^{-}\in\underline{MDS}(G-y_{j^{\prime}})$ with $r\in D^{-}$ by Observation 2.3. But then $D^{-}\cup\{y_{j^{\prime}}\}\in \underline{MDS}(G)$ with $r\in D^{-}\cup\{y_{j^{\prime}}\}$, contradicting the claim that $r$ is bad in $G$. So for every $1\leq j\leq m$, we have $\gamma(G-y_{j})\geq\gamma(G)$, which implies that $y_j$ is non-critical in $G$.

Finally, it remains to show that $\gamma(G-x)\geq\gamma(G)$ for every $x\in V(G-g)-V(R_{l, m})\subseteq V(G_0)$. Since all the vertices of $G_0$ are non-critical, we have $\gamma(G_0-x)\geq \gamma(G_0)$. Let $D^{-}_x\in \underline{MDS}(G-x)$. If $D^{-}_x\cap V(G_0-x)$ can dominate $g$, then $D^{-}_x\cap V(G_0-x)$ is a dominating set of $G_0-x$, and so $\gamma(G-x) = |D^{-}_x|\geq|D^{-}_x\cap V(G_0-x)|+|U|+|D^{-}_x\cap Z|\geq\gamma(G_0-x)+(l+m)\geq\gamma(G_0)+(l+m) = \gamma(G)$; if not, then we have $r\in D^{-}_x$ and $\big(D^{-}_x\cap V(G_0-x)\big)\cup\{g\}$ is a dominating set of $G_0-x$, and so $\gamma(G-x) = |D^{-}_x| = |D^{-}_x\cap V(G_0-x)|+|\{r\}|+|U|+|D^{-}_x\cap Z| = |\big(D^{-}_x\cap V(G_0-x)\big)\cup\{g\}|+(l+m)\geq\gamma(G_0-x)+(l+m)\geq\gamma(G_0)+(l+m) = \gamma(G)$. The necessity follows.

3.3.   To construct trees only containing non-critical vertices

Since it is hard to obtain a constructive characterization of graphs without critical vertices, we only solve this problem partly by restricting the graph class to be trees in this subsection.

Theorem 3.7. A nontrivial tree $T$ has no critical vertices if and only if $T$ can be obtained from $P_{2}$ or $P_{3}$ by a finite sequence of Operations $\rm{i}$–$\rm{iii}$.

Proof. Let $\mathcal{T}$ be the set of graphs obtained from $P_{2}$ or $P_{3}$ by a finite sequence of Operations i–iii. It suffices to prove that $T$ has no critical vertices if and only if $T\in \mathcal{T}$.

($\Leftarrow$) Assume that $T$ is obtained by doing $n$ times Operations i, ii and iii. We will prove that all the vertices of $T$ are non-critical by induction on $n$. When $n = 0$, we have $T = P_{2}$ or $T = P_{3}$, and the result is true clearly. Suppose that the result is true when $n = k \; (k\geq0)$. Then from Lemmas 3.2, 3.4 (b), and 3.6 (b), we know that the result is also true when $n = k+1$. By the induction principle, the sufficiency follows.

($\Rightarrow$) We are going to prove the necessity by induction on $|V(T)|$. When $|V(T)| = 2$ or $3$, the result is true clearly. Suppose that the result is true when $|V(T)| < k \; (k\geq4)$. We consider the case when $|V(T)| = k$ below.

Case 1. $T$ has a pendant path of order at least $3$.

Let $P_3$ be a $3$-pendant path of $T$ and $T_0 = T-V(P_3)$. Note that $P_3\cong R_{0, 1}$. So $T = T_0\negthinspace\backsim\negthinspace R_{0, 1}$. By Lemma 3.6 (b), all the vertices of $T_0$ are non-critical. Since $|V(T_0)| < |V(T)| = k$, we have $T_0\in\mathcal{T}$ by the induction hypothesis. Hence $T = T_0\negthinspace\backsim\negthinspace R_{0, 1}\in \mathcal{T}$.

Case 2. $T$ has a vertex $u$ adjacent to an end-vertex $w$ in $T$ and $u$ is fixed in $T-w$.

Let $T_0 = T-w$. Then $T = T_0\negthinspace\backsim\negthinspace P_{1}$. By Lemma 3.2, $T_0$ has no critical vertices. Since $|V(T_0)| = k-1 < k$, we have $T_0\in\mathcal{T}$. Hence $T = T_0\negthinspace\backsim\negthinspace P_{1}\in\mathcal{T}$.

Case 3. $T$ has a vertex $u$ of degree $3$ which is adjacent to two end-vertices $v, w$ of $T$ and a fixed vertex $g$ of $T-\{v, u, w\}$ in $T$.

Let $T_0 = T-\{v, u, w\}$. Then $T = T_0\negthinspace\backsim\negthinspace P_{3}$. By Lemma 3.4 (a), $T_0$ has no critical vertices. So $T_0\in\mathcal{T}$, and hence $T\in \mathcal{T}$.

Case 4. $T$ has a vertex $u$ of degree at least $3$ linked with $|N_T(u)|-1$ 2-pendant paths.

Let $P_{2}^{1}, P_{2}^{2}, \ldots, P_{2}^{m}$ be the 2-pendant paths linked with $u$ in $T$, where $m = |N_T(u)|-1$. Then $T\big[\{u\}\cup\bigcup\nolimits_{j = 1}^{m}V(P_{2}^{j})\big]\cong R_{0, m}$. Let $T_0 = T-\big(\{u\}\cup\bigcup\nolimits_{j = 1}^{m}V(P_{2}^{j})\big)$. Then $T = T_0\backsim\negthinspace R_{0, m}$. As a consenquence, we have $T\in \mathcal{T}$.

Case 5. All of Cases 1–4 do not occur.

Since $|V(T)|\geq4$ and Case 1 does not occur, $T$ is not a path. So $T$ has at least one vertex of degree at least $3$.

Claim 5.1. There does not exist a vertex $u$ adjacent to three end-vertices in $T$.

Suppose not. Let $v_1$ be an end-vertex which is adjacent to $u$ in $T$ and let $T_0 = T-v_1$. By Observation 2.2, $u$ is a fixed vertex of $T_0$, which is contrary to the supposition that Case 2 does not occur.

Claim 5.2. There does not exist a vertex $u$ linked with one 1-pendant path $P_1$ and one 2-pendant path $P_2$ in $T$.

Suppose not. Let $V(P_2) = \{x, y\}$ with $ux\in E(T)$. By Observation 2.3, there exists $D_u\in \underline{MDS}(T)$ such that $u\in D_u$. Let $D^{\ast}_u = (D_u-\{x, y\})\cup \{y\}$. Then $D^{\ast}_u-\{y\}$ is a dominating set of $T-y$, which implies that $y$ is a critical vertex of $T$, contradicting the known condition that $T$ has no critical vertices.

Claim 5.3. $T$ has at least two vertices of degree at least $3$.

Suppose, to the contrary, that $T$ has only one vertex $c$ with $d_T(c)\geq3$. By Lemma 2.7, $c$ is linked with $|N_T(c)|$ pendant paths in $T$. Since Case 1 does not occur, it follows from Claims 5.2 and 5.1 that all of these $|N_T(c)|$ pendant paths are $2$-pendant paths. But this contradicts the supposition that Case 4 does not occur.

Claim 5.4. If $u$ and $v$ are two vertices of degree at least $3$ in $T$ such that $d_T(u, v) =$ max $\{d_T(x, y)\; |\;$both $x$ and $y$ are vertices of degrees at least $3$ in $T\}$, then $|N_T(u)| = 3$ and $u$ is adjacent to $2$ end-vertices in $T$.

By Lemma 2.8, $u$ is linked with $|N_T(u)|-1$ pendant paths in $T$. Since Cases 1 and 4 does not occur, it follows from Claims 5.2 and 5.1 that $|N_T(u)| = 3$ and $u$ is adjacent to $2$ end-vertices in $T$.

Now, let $u$ and $v$ be two vertices of $T$ satisfying the supposition of Claim 5.4. Suppose that $v_1$ and $w_1$ are two end-vertices which are adjacent to $u$ in $T$ and $N_T(u)-\{v_1, w_1\} = \{r\}$. By Claim 5.4, the equivalent status of $v$ and $u$, and Observation 2.2, we get that $v$ is a fixed vertex of $T-\{u, v_1, w_1\}$. Since Case 3 does not occur, we have $r\neq v$.

Let $T_v$ be the component of $T-r$ such that $v\in V(T_v)$, $\{z\} = N_T(r)\cap V(T_v)$, $N_T(r)-\{z\} = \{u_1, u_2, \ldots, u_q\}$ (where $u_1 = u$) and $T_{u_1}, T_{u_2}, \ldots, T_{u_q}$ be the components of $T-r$ such that $u_i\in V(T_{u_i})$ for every $1\leq i\leq q$. Furthermore, we may suppose without loss of generality that $T_{u_1}, T_{u_2}, \ldots, T_{u_l}$ are not pendant paths of $T$ as well as $T_{u_{l+1}}, T_{u_{l+2}}, \ldots, T_{u_{l+m}}$ are pendant paths of $T$, where $1\leq l\leq q$ and $l+m = q$.

Claim 5.5. $T_{u_i}$ is a 2-pendant path of $T$ for every $l+1\leq i\leq l+m$.

Suppose, to the contrary, that $T_{u_{i^\prime}}$ is a pendant path of $T$ with $|V(T_{u_{i^\prime}})|\neq2$ for some $l+1\leq i^\prime\leq l+m$. By Lemma 3.1, $r$ is a non-critical vertex of $T-V(T_{u_{i^\prime}})$. Since Case 1 does not occur, we have $|V(T_{u_{i^\prime}})| = 1$. Let $V(T_{u_{i^\prime}}) = \{w\}$ and $T_0 = T-\{u, v_1, w_1\}$. By Observations 2.2 and 2.3, one may let $D_r\in \underline{MDS}(T)$ with $u, r\in D_{r}$. We claim that $D_r\cap V(T_0)\in \underline{MDS}(T_0)$. Otherwise there exists $D_0\in\underline{MDS}(T_0)$ such that $|D_0| < |D_r\cap V(T_0)|$. But then $\{u\}\cup D_0$ would be a dominating set of $T$ with $|\{u\}\cup D_0| < |\{u\}\cup \big(D_u\cap V(T_0)\big)| = |D_r|$, contradicting the minimality of $|D_r|$. Thus $\gamma(T) = |D_r| = |\{u\}|+| D_r\cap V(T_0)| = 1+\gamma(T_0)$. Since Case 3 does not occur, $r$ is not a fixed vertex of $T_0$. Let $\hat{D}_0^{r}\in \underline{MDS}(T_0)$ with $r\notin \hat{D}_0^{r}$. Then $w\in \hat{D}_0^{r}$ and $\{u\}\cup \hat{D}_0^{r} \in \underline{MDS}(T)$. Since $(\{u\}\cup \hat{D}_0^{r})-\{w\}$ is a dominating set of $T-w$, it follows that $w$ is a critical vertex of $T$, a contradiction.

Claim 5.6. For every $2\leq i\leq l$, $u_i$ is the unique vertex of $V(T_{u_i})$ satisfying $d_T(u_i)\geq3$.

Firstly, since $T_{u_i}$ is not a pendant path of $T$, $T_{u_i}$ has a vertex with degree at least $3$ in $T$. Secondly, we claim that for every $h\in V(T_{u_i})-\{u_i\}$, $h$ is not a vertex of $V(T_{u_i})$ with degree at least $3$ in $T$. Otherwise, we have $d_T(h, v) = d_T(h, u_i)+d_T(u_i, v) > d_T(u_i, v) = 1+d_T(r, v) = d_T(u, v)$, contradicting the selection of $u$ and $v$. From these two observations, Claim 5.6 follows.

Since $d_T(u_i, v) = d_T(u_1, v)$, we have $|N_T(u_i)| = 3$ and $u_i$ is adjacent to $2$ end-vertices in $T$ for every $2\leq i\leq l$ by Claim 5.4, which implies that

(See Figure 5.) Let $T_0 = T-\big(\{r\}\cup\bigcup\nolimits_{i = 1}^{l}V(T_{u_i})\cup\bigcup\nolimits_{j = 1}^{m}V(T_{u_{l+j}})\big)$. Then $T = T_0\negthinspace\backsim\negthinspace R_{l, m}$. By Lemma 3.6 (b), $T_0$ has no critical vertices. Thus we have $T_0\in \mathcal{T}$ by the induction hypothesis, and so $T\in \mathcal{T}$.

Figure 5.  The sketch of Case 5.

DownLoad: Full-Size Img PowerPoint

In conclusion, the result is true when $|V(T)| = k$. The necessity follows.

4.   Conclusions

We think that it is quite difficult to give a construction for graphs without critical vertices. For further studies, ones may consider to characterize unicyclic graphs without critical vertices, or graphs with domination number 3 and without critical vertices.

Acknowledgments

1. National Natural Science Foundation of China (no. 12061047);

2. Natural Science Foundation of Jiangxi Province (no. 20192BAB211002);

3. Undergraduate Innovation Training Project of Hubei Province (no. 202111072011);

4. Foundation of Cultivation of Scientific Institutions of Jianghan University (no. 06210033).

Conflict of interest

The authors declared that they have no conflicts of interest to this work.