Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree

1.   Introduction

We consider only simple and undirected labeled graphs and follow the terminology and notation of ^[5]. Let $G = (V, E)$ be a graph and $v$ be a vertex of $G$, we write $N_G(v)$ to denote the (open) neighborhood of $v$. The closed neighborhood of $v$ is defined as $N_G[v] = N_G(v)\cup\{v\}$. The degree of $v$ is defined as $d_G(v) = |N_{G}(v)|$. For $U\subseteq V$, we write $G[U]$ to denote the subgraph induced by $U$. The subgraph $G[V\setminus U]$ is denoted by $G-U$. Furthermore, $G-U$ can be written by $G- u$ if $U = \{u\}$.

In a graph $G$, an independent set is a subset of vertices spanning no edges. Finding an independent set of maximum cardinality in a graph is a widely studied well-known problem of graph theory and is called the maximum independent set problem. In 1982, Hammer et al. ^[11] studied the maximum independent problem from different perspectives and investigated the vertices contained in all or in no maximum independent sets of a graph. Since then, researchers have extensively studied this kind of problem for some other vertex subsets with given properties. For example, Mynhardt ^[15], Cockayne et al. ^[10], and Blidia et al. ^[3] considered this kind of problem for minimum dominating sets, total dominating sets, and minimum double dominating sets of trees, respectively. Recently, Bouquet et al. ^[6] studied this kind of problem of minimum dominating sets on claw-free graphs, chordal graphs, and triangle-free graphs.

In a graph $G$, a dissociation set is a subset of vertices $F$ such that the induced subgraph $G[F]$ has maximum degree at most 1. A maximum dissociation set of $G$ is a dissociation set of maximum cardinality. The dissociation number $\psi(G)$ of a graph $G$ is the cardinality of a maximum dissociation set of $G$. The concept of dissociation set was introduced by Yannakakis ^[21] in 1981 and is a natural generalization of independent set. The maximum dissociation set problem, to find a maximum dissociation set in a graph is NP-hard for many subclasses of graphs such as $K_{1, 4}$-free bipartite graphs, $C_4$-free bipartite graphs with vertex degree at most 3, planar graphs with vertex degree at most 4, triangle-free graphs, line graphs, etc. (see ^[2,4,16,17]). On the other hand, the problem is polynomially solvable for chordal and weakly chordal graphs, circular-arc graphs, AT-free graphs, (chair, $K_3$)-free graphs, etc. (see ^[8,16]). In terms of exact algorithms, Kardoš, Katrenič and Schiermeyer ^[13] gave an $O^*(1.5171^n)$-time exact algorithm for the problem in an $n$-vertex graph. Chang et al. ^[9] improved the result to $O^*(1.4658^n)$. Xiao and Kou ^[20] proposed an exact algorithm which can solve the problem in $O^*(1.4656^n)$ time and polynomial space or $O^*(1.3659^n)$ time and exponential space. Computing the dissociation number can be helpful in finding a lower bound for the 1-improper chromatic number of a graph ^[12]. And the maximum dissociation set problem has applications in telecommunications, scheduling, wireless sensor networks and networking security ^[1,7].

A $k$-path vertex cover in a graph $G$ is a subset of vertices intersecting every $k$-path of $G$, where a $k$-path is a path of order $k$. It is easy to see that a set $S$ of vertices of a graph $G$ is a 3-path vertex cover of $G$ if and only if its complement $V(G)\setminus S$ is a dissociation set of $G$. In this decade, the problem of finding a minimum $k$-path vertex cover in a graph has received great attention ^{[7,13,14,19,20]}.

The main purpose of this paper is to characterize the vertices contained in all maximum dissociation sets and in no maximum dissociation set of a tree. Define the vertex subsets $\mathcal{A}(G)$, $\mathcal{F}(G)$ and $\mathcal{N}(G)$ by

On the other hand, the study is also inspired by the relationship between the characteristic of vertex subsets $\mathcal{A}(G)$ and $\mathcal{N}(G)$ and the number of maximum dissociation sets in a graph $G$. In ^[18], Tu, Zhang and Shi found four structure theorems concerning the vertex subsets $\mathcal{A}(T)$ and $\mathcal{N}(T)$ for a tree $T$ and determined the maximum number of maximum dissociation sets in a tree of order $n$.

The paper is organized as follows. In Section 2, we introduce some necessary notation and lemmas. In Section 3, we characterize the vertex subsets $\mathcal{A}(T)$ and $\mathcal{N}(T)$ of a tree $T$. In Section 4, a linear recognition algorithm which can determine whether a given vertex in a tree is contained in all (or no) maximum dissociation sets of the tree will be presented. Thus, using the recognition algorithm, all vertices contained in all (or no) maximum dissociation sets of a tree of order $n$ can be found in $O(n^2)$ time.

2.   Preliminary results

A rooted tree $T$ is a connected acyclic graph with a specified vertex $r$, called the root of $T$. Let $T$ be a tree rooted at $r$ and $v$ be a vertex of $T$, each vertex on the path from the root $r$ to the vertex $v$, including the vertex $v$ itself, is called an ancestor of $v$, and a descendant of $v$ is a vertex $u$ such that $v$ is an ancestor of $u$. An ancestor or descendant of a vertex is proper if it is not the vertex itself. The parent $p(v)$ of $v$ is the immediate proper ancestor of $v$, a child of $v$ is a vertex $u$ such that $p(u) = v$. Define the vertex subsets $C_T(v)$, $D_T(v)$, and $D_T[v]$ by

If no confusion occurs, these also be written by $C(v)$, $D(v)$, and $D[v]$, respectively. We write $T_v$ to denote the subtree induced by $D_T[v]$.

A leaf in a tree is a vertex with degree 1, a branch vertex is a vertex with degree at least 3. We write $B(T)$ to denote the set of branch vertices of $T$. A path $P$ in $T$ is called a $v-L$ path, if $P$ joins $v$ to a leaf that is a descendant of $v$. Denote the order of $P$ by $n(P)$, and for $i = 0, 1, 2$, define

Now, some basic observations about maximum dissociation sets of the path are given.

Observation 2.1. Let $P_n = u_1u_2\cdots u_n$ be a path of order $n\ge3$.

(a) $\psi(P_n) = \tfrac{2n+i}{3}$, where $n\equiv i(\bmod3)$, $i = 0, 1, 2$.

(b) If $n\equiv 0(\bmod3)$, then there exists a maximum dissociation set of $P_n$ that contains exactly one leaf.

(c) If $n\equiv 1(\bmod3)$, then both leaves of $P_n$ belong to all maximum dissociation sets of $P_n$, furthermore, $P_n$ has a maximum dissociation set $F$ such that $d_{P_n[F]}(u_1) = 0$.

(d) If $n\equiv 2(\bmod3)$, then there is only one maximum dissociation set $F$ in $P_n$, furthermore, $\{u_1, u_n\}\subset F$ and $d_{P_n[F]}(u_1) = d_{P_n[F]}(u_n) = 1$.

Proof. (a) Since a maximum dissociation set of $P_n$ contains at most two vertices of three consecutive vertices of $P_n$, one can easily check the truth of the statement by case analysis.

(b) If $n\equiv 0(\bmod3)$, then $F = V(P_n)\setminus\{u_{3i}, 1\leq i\leq \frac{n}{3}\}$ is a maximum dissociation set of $P_n$ that contains exactly one leaf.

(c) If $n\equiv 1(\bmod3)$, then $\psi(P_n) = \frac{2n+1}{3}$. Suppose for a contradiction that there exists a maximum dissociation set in $P_n$ that contains at most one leaf. Then $\psi(P_n) = \psi(P_{n-1}) = \frac{2(n-1)}{3} < \frac{2n+1}{3}$, a contradiction. Thus both leaves of $P_n$ belong to all maximum dissociation sets of $P_n$.

Furthermore, $F = V(P_n)\setminus\{u_{3i+2}, 0\leq i\leq \frac{n-4}{3}\}$ is a maximum dissociation set of $P_n$ such that $d_{P_n[F]}(u_1) = 0$.

(d) If $n\equiv 2(\bmod3)$, then $\psi(P_n) = \frac{2n+2}{3}$. Let $F$ be any maximum dissociation set of $P_n$. If $u_1\notin F$, then $\psi(P_n) = \psi(P_{n-1}) = \frac{2(n-1)+1}{3} < \frac{2n+2}{3}$, a contradiction. If $d_{P_n[F]}(u_1) = 0$, then $\psi(P_n) = \psi(P_{n-2})+1 = \frac{2(n-2)}{3}+1 = \frac{2n-1}{3} < \frac{2n+2}{3}$, a contradiction. Thus, $d_{P_n[F]}(u_1) = 1$. Similarly, $d_{P_n[F]}(u_n) = 1$. Since a maximum dissociation set of $P_n$ contains at most two vertices of three consecutive vertices of $P_n$, one can easily check that there is only one maximum dissociation set in $P_n$.

Firstly, we characterize $\mathcal{A}(T)$ and $\mathcal{N}(T)$ in the case where $B(T)\le1$.

Lemma 2.2. Let $T$ be a rooted tree with the root $v$. If for each $u\in V(T)\setminus\{v\}$, $d_T(u)\le2$, then

Proof. Because $T_w$ is a path for each $w\in C(v)$, it is easy to determine $\psi(T_w)$ and $C^i(v)\cap C^j(v) = \emptyset$ for $i\neq j$. Note that $\sum_{w\in C(v)}\psi(T_w)\le\psi(T)\le\sum_{w\in C(v)}\psi(T_w)+1$. We consider the two cases.

Case 1. $|C^2(v)| = 0$ and $|C^1(v)|\le 1$.

If $w\in C^0(v)$, then $T_w\cong P_n$ with $n\equiv 0(\bmod3)$. Let $F_w$ be a maximum dissociation set of $T_w$ such that $w\notin F_w$ ($F_w$ exists by Observation 2.1(b)). If $w\in C^1(v)$, then $T_w\cong P_n$ with $n\equiv 1(\bmod3)$ and let $F_w$ be a maximum dissociation set of $T_w$ such that $d_{T_w[F_w]}(w) = 0$ ($F_w$ exists by Observation 2.1(c)). Now, let

then $F$ is a dissociation set of $T$ and $|F| = \sum_{w\in C(v)}\psi(T_w)+1$. Thus, $F$ is a maximum dissociation set of $T$ and $\psi(T) = \sum_{w\in C(v)}\psi(T_w)+1$.

Case 2. $|C^2(v)|\ge1$ or $|C^1(v)|\ge 2$.

Suppose for a contradiction that $\psi(T) = \sum_{w\in C(v)}\psi(T_w)+1$. Let $F$ be a maximum dissociation set of $T$. Then, $v\in F$ and $F\cap T_w$ is a maximum dissociation set of $T_w$ for each $w\in C(v)$. Let $F_w: = F\cap T_w$ for each $w\in C(v)$. If $w\in C^2(v)$, then $T_w\cong P_n$ with $n\equiv 2(\bmod3)$. By Observation 2.1(d), $w\in F_w$ and $d_{T_w[F_w]}(w) = 1$. Thus, if $|C^2(v)|\ge1$, there is a 3-path in $T[F]$ that contains the vertex $v$, a contradiction.

If $w\in C^1(v)$, then $T_w\cong P_n$ with $n\equiv 1(\bmod3)$. By Observation 2.1(c), we have $w\in F_w$. Thus, if $|C^1(v)|\ge 2$, then there is a 3-path in $T[F]$ that contains the vertex $v$, a contradiction.

The proof is complete.

Theorem 2.3. Let $T$ be a rooted tree with the root $v$. If for each $u\in V(T)\setminus\{v\}$, $d_T(u)\le2$, then

(a) $v\in \mathcal{A}(T)$ if and only if $|C^2(v)| = 0$ and $|C^1(v)|\le 1$;

(b) $v\in \mathcal{N}(T)$ if and only if $|C^2(v)| = 2$ or $|C^1(v)|+|C^2(v)|\ge 3$.

Proof. (a) Necessity. Suppose for a contradiction that $|C^2(v)|\ge1$ or $|C^1(v)|\ge2$ and $v\in \mathcal{A}(T)$. Let $F = \bigcup_{w\in C(v)}F_w$, where $F_w$ is a maximum dissociation set of $T_w$ for each $w\in C(v)$. By Lemma 2.2, we have $\psi(T) = \sum_{w\in C(v)}\psi(T_w)$. Thus, $F$ is a maximum dissociation set of $T$ and $v\notin F$, which contradicts with $v \in \mathcal{A}(T)$.

Sufficiency. Suppose that $|C^2(v)| = 0$ and $|C^1(v)|\le 1$. Then $\psi(T) = \sum_{w\in C(v)}\psi(T_w)+1$ by Lemma 2.2 and the vertex $v$ is in all maximum dissociation sets of $T$. Thus, $v\in \mathcal{A}(T)$.

The proof of (a) is complete.

(b) Necessity. Suppose for a contradiction that $|C^2(v)|\neq 2$ and $|C^1(v)|+|C^2(v)|\le 2$ and $v\in \mathcal{N}(T)$.

If $|C^2(v)| = 0$ and $|C^1(v)|\le1$, then $v\in \mathcal{A}(T)$ by (a), a contradiction.

If $|C^2(v)| = 0$ and $|C^1(v)| = 2$, then we assume $w_1, w_2\in C^1(v)$. For each $w\in C^0(v)$, there exists a maximum dissociation set $F_w$ of $T_w$ such that $w\notin F_w$ by Observation 2.1(b). For $w_1\in C^1(v)$, we have $T_{w_1}-w_1 \cong P_n$ with $n\equiv 0(\bmod3)$. Let $F_{w_1}$ be a maximum dissociation set of $T_{w_1}-w_1$. Then $|F_{w_1}| = \psi(T_{w_1})-1$ by Observation 2.1(a). For $w_2\in C^1(v)$, there exists a maximum dissociation set $F_{w_2}$ of $T_{w_2}$ such that $d_{T_{w_2}[F_{w_2}]}(w_2) = 0$ by Observation 2.1(c). Let $F = \bigcup_{w\in C^0(v)}F_w \cup F_{w_1} \cup F_{w_2}\cup \{v\}$, then $F$ is a dissociation set of $T$ and $|F| = \sum_{w\in C(v)}\psi(T_w)$. By Lemma 2.2, $F$ is a maximum dissociation set of $T$ and $v\in F$, a contradiction.

If $|C^2(v)| = 1$ and $|C^1(v)|\le1$, then we assume $w_3\in C^2(v)$. For $w_3\in C^2(v)$, we have $T_{w_3}-w_3 \cong P_n$ with $n\equiv 1(\bmod3)$. Let $F_{w_3}$ be a maximum dissociation set of $T_{w_3}-w_3$, then $|F_{w_3}| = \psi(T_{w_3})-1$ by Observation 2.1(a). For each $w\in C^0(v)$, let $F_w$ be a maximum dissociation set of $T_w$ such that $w\notin F_w$. For $w\in C^1(v)$, let $F_w$ be a maximum dissociation set of $T_{w}$ such that $d_{T_{w}[F_{w}]}(w) = 0$. Now let $F = \bigcup_{w\in C(v)-\{w_3\}}F_w \cup F_{w_3}\cup\{v\},$ then $F$ is a dissociation set of $T$ and $|F| = \sum_{w\in C(v)}\psi(T_w)$. By Lemma 2.2, $F$ is a maximum dissociation set of $T$ and $v\in F$, a contradiction.

Sufficiency. Suppose for a contradiction that $|C^2(v)| = 2$ or $|C^1(v)|+|C^2(v)|\ge 3$, and $v\notin \mathcal{N}(T)$. Let $F$ be a maximum dissociation set of $T$ such that $v\in F$. For each $w\in C^0(v)$, $|F\cap T_w|\le \psi(T_w)$. If $w\in C^2(v)$, then $T_w\cong P_n$ with $n\equiv 2(\bmod3)$. Since $v\in F$, we have $|F\cap T_w|\le \psi(T_w)-1$. If $w\in C^1(v)$, then every maximum dissociation set $F_w$ of $T_w$ contains the vertex $w$. Since $v\in F$, there are at least $|C^1(v)|-1$ vertices $w$ in $C^1(v)$ such that $|F\cap T_w|\le \psi(T_w)-1$. Hence, it is easy to check $|F| < \sum_{w\in C(v)}\psi(T_w)\leq\psi(T)$, a contradiction.

The proof of (b) is complete.

3.   Characterizations of $\mathcal{A}(T)$ and $\mathcal{N}(T)$

A technique called pruning process was introduced in ^[15]. Using the technique and Theorem 2.3, we can characterize $\mathcal{A}(T)$ and $\mathcal{N}(T)$ for an arbitrary tree $T$.

Let $T$ be a rooted tree with the root $v$ and $u$ be a branch vertex of $T$ at maximum distance from $v$. It is easy to see that $|C(u)|\ge2$ and $d_T(x)\le2$ for each $x\in D(u)$. If $u\neq v$, we execute the following pruning process:

● if $|C^2(u)|\ge1$ or $|C^1(u)|\ge2$, then delete $D[u]$,

● if $|C^2(u)| = 0$ and $|C^1(u)|\le1$, then for all $w\in C(u)\setminus\{z\}$, delete $D[w]$, where $z$ is the vertex in $C^1(u)$ if $|C^1(u)| = 1$, otherwise $z$ is any one vertex in $C(u)$.

This step of pruning process is called a pruning of $T$ at $u$. Repeat the above pruning process, finally, we obtain a unique tree $\bar{T}$ called the pruning of $T$ such that $d_{\bar{T}}(u)\le2$ for each $u\in V(\bar{T})\setminus\{v\}$. We will show that the root $v$ is in all maximum dissociation sets (or in no maximum dissociation set) of $T$ if and only if it is in all maximum dissociation sets (or in no maximum dissociation set) of the pruning $\bar{T}$ of $T$.

Lemma 3.1. Let $T$ be a rooted tree with the root $v$ and $\bar{T}$ be the pruning of $T$. For every maximum dissociation set $\bar{F}$ of $\bar{T}$, there exists a maximum dissociation set $F$ of $T$ such that $v\in F$ if and only if $v\in\bar{F}$. Conversely, for every maximum dissociation set $F$ of $T$, there exists a maximum dissociation set $\bar{F}$ of $\bar{T}$ such that $v\in\bar{F}$ if and only if $v\in F$.

Proof. We prove the lemma by induction on $|B'(T)|$, where $B'(T) = \{u\in V(T)\setminus\{v\}:d(u)\ge3\}$. If $|B'(T)| = 0$, then $T = \bar{T}$ and the result holds clearly. Suppose that when $|B'(T)| < k$, the lemma holds. Let $T$ be a tree with $|B'(T)| = k$ and $u$ be a vertex of $B'(T)$ at maximum distance from $v$. Let $T'$ be the tree obtained from $T$ by applying a pruning of $T$ at $u$. Thus, $\bar{T}$ is also the pruning of $T'$.

First, we show that for every maximum dissociation set $\bar{F}$ of $\bar{T}$, there exists a maximum dissociation set $F$ of $T$ such that $v\in F$ if and only if $v\in\bar{F}$. By the induction hypothesis, for every maximum dissociation set $\bar{F}$ of $\bar{T}$, there exists a maximum dissociation set $F'$ of $T'$ such that $v\in F'$ if and only if $v\in\bar{F}$.

We consider the following two cases.

Case 1. $|C^2(u)| = 0$ and $|C^1(u)|\le 1$.

For each $w\in C(u)\setminus\{z\}$, $T_w\cong P_n$ with $n\equiv 0\ (\bmod3)$. Let $F_w$ be a maximum dissociation set of $T_w$ such that $w\notin F_w$ ($F_w$ exists by Observation 2.1(b)). Let $F = \bigcup_{w\in C(u)\setminus\{z\}}F_w \cup F'$. Clearly, $F$ is a maximum dissociation set of $T$. Since $v\in F'$ if and only if $v\in F$, we have $v\in F$ if and only if $v\in\bar{F}$.

Case 2. $|C^2(u)|\ge1$ or $|C^1(u)|\ge2$.

In this case, $T' = T-D[u]$. For each $w\in C(u)$, let $F_w$ be a maximum dissociation set of $T_w$. Let $F = \bigcup_{w\in C(u)}F_w \cup F'$. Since $|C^2(u)|\ge1$ or $|C^1(u)|\ge2$, by Lemma 2.2, $\psi(T_u) = \sum_{w\in C(u)}\psi(T_w) = \sum_{w\in C(u)}|F_w|$, which implies that $\bigcup_{w\in C(u)}F_w$ is a maximum dissociation set of $T_u$. Thus, $F$ is a maximum dissociation set of $T$. Since $v\in F'$ if and only if $v\in F$, we have $v\in F$ if and only if $v\in\bar{F}$.

Now, we show that for every maximum dissociation set $F$ of $T$, there exists a maximum dissociation set $\bar{F}$ of $\bar{T}$ such that $v\in\bar{F}$ if and only if $v\in F$. Likewise, we consider the following two cases.

Case 1. $|C^2(u)| = 0$ and $|C^1(u)|\le 1$.

For each $w\in C(u)\setminus\{z\}$, we have $T_w\cong P_n$ with $n\equiv 0(\bmod3)$. Let $F_w$ be a maximum dissociation set of $T_w$ such that $w\notin F_w$ ($F_w$ exists by Observation 2.1(b)).

For every maximum dissociation set $F$ of $T$, let $F' = F-\bigcup_{w\in C(u)\setminus\{z\}}D[w]$. Then $F'$ is a dissociation set of $T'$ and $v\in F$ if and only if $v\in F'$. We will prove that $F'$ is a maximum dissociation set of $T'$. Suppose for a contradiction that $F_1$ is a maximum dissociation set of $T'$ with $|F_1| > |F'|$. Let $F_2 = \bigcup_{w\in C(u)\setminus\{z\}}F_w \cup F_1$. Then $F_2$ is a dissociation set of $T$ and

which contradicts the fact that $F$ is a maximum dissociation set of $T$. Thus $F'$ is a maximum dissociation set of $T'$. By the induction hypothesis, there exists a maximum dissociation set $\bar{F}$ of $\bar{T}$ such that $v\in F'$ if and only if $v\in\bar{F}$. Hence, there exists a maximum dissociation set $\bar{F}$ of $\bar{T}$ such that $v\in F$ if and only if $v\in\bar{F}$.

Case 2. $|C^2(u)|\ge1$ or $|C^1(u)|\ge2$.

For each $w\in C(u)$, let $F_w$ be a maximum dissociation set of $T_w$. By Lemma 2.2, $\psi(T_u) = \sum_{w\in C(u)}\psi(T_w) = \sum_{w\in C(u)}|F_w|$.

For every maximum dissociation set $F$ of $T$, let $F' = F-D[u]$. We will prove that $F'$ is a maximum dissociation set of $T'$. Suppose for a contradiction that $F_1$ is a maximum dissociation set of $T'$ with $|F_1| > |F'|$. Let $F_2 = \bigcup_{w\in C(u)}F_w \cup F_1$. Then $F_2$ is a dissociation set of $T$ and

which contradicts the fact that $F$ is a maximum dissociation set of $T$. Thus $F'$ is a maximum dissociation set of $T'$. By the induction hypothesis, there exists a maximum dissociation set $\bar{F}$ of $\bar{T}$ such that $v\in F'$ if and only if $v\in\bar{F}$. Thus, there exists a maximum dissociation set $\bar{F}$ of $\bar{T}$ such that $v\in F$ if and only if $v\in\bar{F}$.

We complete the proof.

By Lemma 3.1, we can obtain the following corollary.

Corollary 3.2. Let $T$ be a rooted tree with the root $v$ and $\bar{T}$ be the pruning of $T$, then $v\in\mathcal{A}(T)$ (or $\mathcal{N}(T)$) if and only if $v\in \mathcal{A}(\bar{T})$ (or $\mathcal{N}(\bar{T}))$.

By Theorem 2.3 and Corollary 3.2, the characterizations of $\mathcal{A}(T)$ and $\mathcal{N}(T)$ can be obtained immediately.

Theorem 3.3. Let $T$ be a tree and $v$ be a vertex of $T$. Let $T_v$ be the rooted tree obtained from $T$ with the root $v$ and $\bar{T_v}$ be the pruning of $T_v$. Then

(a) $v\in\mathcal{A}(T)$ if and only if $|C^2_{\bar{T_v}}(v)| = 0$ and $|C^1_{\bar{T_v}}(v)|\le1$;

(b) $v\in\mathcal{N}(T)$ if and only if $|C^2_{\bar{T_v}}(v)| = 2$ or $|C^1_{\bar{T_v}}(v)|+|C^2_{\bar{T_v}}(v)|\ge3$.

4.   A recognition algorithm

In ^[7], the authors presented an algorithm which can find a minimum $k$-path vertex cover in a tree in linear time, it follows that the problem of finding a maximum dissociation set of a tree can be solved in linear time. Let $T$ be a tree and $v$ a vertex of $T$. The equality $\psi(T-v) = \psi(T)-1$ holds if and only if $v$ belongs to all maximum dissociation sets of $T$. Thus the algorithm presented in ^[7] can be used to determine whether a given vertex in a tree belongs to all maximum dissociation sets of the tree. But, if $\psi(T-v) = \psi(T)$, then it may be that $v$ belongs to no maximum dissociation set of $T$, it may be that $v$ belongs to some maximum dissociation sets but not all. Hence, the algorithm presented in ^[7] cannot be used to determine whether a given vertex in a tree belongs to no maximum dissociation set of the tree.

In this section, we present a linear time recognition algorithm which can determine whether a given vertex in a tree is in all maximum dissociation sets, or in some maximum dissociation sets but not all, or in no maximum dissociation set. See Table 1.

For a rooted tree, we can use the breadth-first search algorithm to find the distance from the root to each other vertex in linear time. Step 4 is the pruning process of the rooted tree $T$. The cardinality of the set $B$ is at most $|V(T)|$ and will decrease by 1 after each loop execution. More precisely, let $u$ be a vertex in $B$ such that $d(u, v)$ is maximum and $w$ be a child of $u$, there exists only one $w-L$ path that joins $w$ to a leaf that is a descendant of $v$ and the order of the $w-L$ path can be obtained from the distances from the root to the vertex $w$ and the leaf. Thus, we can compute the sets $C^2(u)$ and $C^1(u)$ in $O(d(u))$ time. The total runtime of Step 4 is $O(\sum_{u\in B}d(u))$, which implies that Step 4 can be executed in linear time. Thus, the runtime of the recognition algorithm is linear. Using the recognition algorithm we can find all vertices contained in all (or no) maximum dissociation sets of a tree of order $n$ in $O(n^2)$ time.

5.   Conclusions

In this paper, we study the maximum dissociation set problem from different perspectives and characterize the vertices belonging to all maximum dissociation sets, and no maximum dissociation set of a tree. Based on the characterization, we present a linear time recognition algorithm which can determine whether a given vertex in a tree is in all maximum dissociation sets, or in some maximum dissociation sets but not all, or in no maximum dissociation set. Thus for a tree with $n$ vertices, we can find all vertices belonging to all (or no) maximum dissociation sets of the tree in $O(n^2)$ time.

Acknowledgments

The work is supported by Research Foundation for Advanced Talents of Beijing Technology and Business University (No. 19008021187). We would like to thank two anonymous referees for their many helpful suggestions and comments.

Conflict of interest

The authors declare that they have no competing interests.