Some sufficient conditions for path-factor uniform graphs

Abstract

For a set $\mathcal {H}$ of connected graphs, a spanning subgraph H of G is called an $\mathcal {H}$-factor of G if each component of H is isomorphic to an element of $\mathcal {H}$. A graph G is called an $\mathcal {H}$-factor uniform graph if for any two edges $e_1$ and $e_2$ of G, G has an $\mathcal {H}$-factor covering $e_1$ and excluding $e_2$. Let each component in $\mathcal {H}$ be a path with at least d vertices, where $d\ge 2$ is an integer. Then an $\mathcal {H}$-factor and an $\mathcal {H}$-factor uniform graph are called a $P_{\ge d}$-factor and a $P_{\ge d}$-factor uniform graph, respectively. In this article, we verify that (i) a 2-edge-connected graph G is a $P_{\ge 3}$-factor uniform graph if $\delta (G)>\frac{\alpha (G)+4}{2}$; (ii) a $(k+2)$-connected graph G of order n with $n\ge 5k+3-\frac{3}{5\gamma -1}$ is a $P_{\ge 3}$-factor uniform graph if $|N_G(A)|>\gamma (n-3k-2)+k+2$ for any independent set A of G with $|A|=\lfloor \gamma (2k+1)\rfloor$, where k is a positive integer and $\gamma$ is a real number with $\frac{1}{3}\le \gamma \le 1$.

1 Introduction

The graphs considered here are finite, undirected and simple. Let G be a graph with edge set E(G) and vertex set V(G). We use i(G), $\omega (G)$, $\alpha (G)$ and $\delta (G)$ to denote the number of isolated vertices, the number of connected components, the independence number and the minimum degree of G, respectively. Let $N_G(x)$ denote the set of neighbours of a vertex x in G. By $d_G(x)$ we mean $|N_G(x)|$ and we call it the degree of a vertex x in G. For any $X\subseteq V(G)$ or $X\subseteq E(G)$ the symbol G[X] denotes the subgraph of G induced by X. We write $N_G(X)=\bigcup \nolimits _{x\in X}{N_{G}(x)}$ and $G-X=G[V(G){\setminus } X]$ for $X\subseteq V(G)$, and denote by $G-X$ the subgraph derived from G by deleting edges of X for $X\subseteq E(G)$. The edge joining vertices x and y is denoted by xy. A vertex subset X of G is called an independent set if $X\cap N_G(X)=\emptyset$. Let $P_n$ and $K_n$ denote the path and the complete graph with n vertices, respectively. We denote by $K_{m,n}$ the complete bipartite graph with the bipartition (X, Y), where $|X|=m$ and $|Y|=n$. Let $G_1$ and $G_2$ be two graphs. By $G_1\cup G_2$ we mean a graph with vertex set $V(G_1)\cup V(G_2)$ and edge set $E(G_1)\cup E(G_2)$. By $G_1\vee G_2$ we mean a graph with vertex set $V(G_1)\cup V(G_2)$ and edge set $E(G_1)\cup E(G_2)\cup \{e=xy: x\in V(G_1), y\in V(G_2)\}$. Recall that $\lfloor r\rfloor$ is the greatest integer with $\lfloor r\rfloor \le r$, where r is a real number.

A subgraph of G is spanning if the subgraph includes all the vertices of G. For a set $\mathcal {H}$ of connected graphs, a spanning subgraph H of G is called an $\mathcal {H}$-factor of G if each component of H is isomorphic to an element of $\mathcal {H}$. A graph G is called an $\mathcal {H}$-factor covered graph if G admits an $\mathcal {H}$-factor covering e for any $e\in E(G)$. A graph G is called an $\mathcal {H}$-factor uniform graph if $G-e$ is an $\mathcal {H}$-factor covered graph for any $e\in E(G)$. Let each component in $\mathcal {H}$ be a path with at least d vertices, where $d\ge 2$ is an integer. Then an $\mathcal {H}$-factor, an $\mathcal {H}$-factor covered graph and an $\mathcal {H}$-factor uniform graph are called a $P_{\ge d}$-factor, a $P_{\ge d}$-factor covered graph and a $P_{\ge d}$-factor uniform graph, respectively.

Amahashi and Kano [1] derived a characterization for a graph with a $\{K_{1,l}:1\le l\le m\}$-factor. Kano and Saito [11] posed a sufficient condition for the existence of $\{K_{1,l}:m\le l\le 2m\}$-factors in graphs. Kano, Lu and Yu [10] investigated the existence of $\{K_{1,2},K_{1,3},K_5\}$-factors and $P_{\ge 3}$-factors in graphs depending on the number of isolated vertices. Bazgan et al. [2] put forward a toughness condition for a graph to have a $P_{\ge 3}$-factor. Zhou, Bian and Pan [22], Zhou, Wu and Bian [28], Zhou, Wu and Xu [30], Wang and Zhang [13], Zhou [20] obtained some results on $P_{\ge 3}$-factors in graphs with given properties. Johansson [7] presented a sufficient condition for a graph to have a path-factor. Gao, Chen and Wang [4] showed an isolated toughness condition for the existence of $P_{\ge 3}$-factors in graphs with given properties. Kano, Lee and Suzuki [9] verified that each connected cubic bipartite graph with at least eight vertices admits a $P_{\ge 8}$-factor. Wang and Zhang [14], Zhou and Liu [23] presented some degree conditions for the existence of graph factors. Zhou, Wu and Liu [29], Zhou [21], Yuan and Hao [16] established some relationships between independence numbers and graph factors. Enomoto, Plummer and Saito [3], Zhou, Liu and Xu [25], Zhou [18, 19], Zhou and Sun [26] derived some neighborhood conditions for the existence of graph factors. some other results on graph factors can be found in Wang and Zhang [15], Zhou and Liu [24].

A graph H is factor-critical if $H-x$ has a perfect matching for each $x\in V(H)$. To characterize a graph with a $P_{\ge 3}$-factor, Kaneko [8] introduced the concept of a sun. A sun is a graph formed from a factor-critical graph H by adding n new vertices $x_1,x_2,\ldots ,x_n$ and n new edges $y_1x_1,y_2x_2,\ldots ,y_nx_n$, where $V(H)=\{y_1,y_2,\ldots ,y_n\}$. According to Kaneko, $K_1$ and $K_2$ are also suns. A sun with at least six vertices is called a big sun. A component of G is called a sun component if it is isomorphic to a sun. Let sun(G) denote the number of sun components of G. Kaneko [8] put forward a criterion for a graph with a $P_{\ge 3}$-factor.

Theorem 1.1

[8]. A graph G admits a $P_{\ge 3}$-factor if and only if

$$\begin{aligned} sun(G-X)\le 2|X| \end{aligned}$$

for all $X\subseteq V(G)$.

Later, Zhou and Zhang [17] improved Theorem 1.1 and acquired a criterion for a $P_{\ge 3}$-factor covered graph.

Theorem 1.2

[17]. Let G be a connected graph. Then G is a $P_{\ge 3}$-factor covered graph if and only if

$$\begin{aligned} sun(G-X)\le 2|X|-\varepsilon (X) \end{aligned}$$

for any vertex subset X of G, where $\varepsilon (X)$ is defined by

$$\begin{aligned} \varepsilon (X)=\left\{ \begin{array}{ll} 2,&{}if \ X \ is \ not \ an \ independent \ set;\\ 1,&{}if \ X \ is \ a \ nonempty \ independent \ set \ and \ G-X \ has\\ &{}a \ non-sun \ component;\\ 0,&{}otherwise.\\ \end{array} \right. \end{aligned}$$

Zhou and Sun [27] got a binding number condition for the existence of $P_{\ge 3}$-factor uniform graphs. Gao and Wang [5], Liu [12] improved the above result on $P_{\ge 3}$-factor uniform graphs. Hua [6] investigated the relationship between isolated toughness and $P_{\ge 3}$-factor uniform graphs. It is natural and interesting to put forward some new sufficient conditions to guarantee that a graph is a $P_{\ge 3}$-factor uniform graph. In this article, we proceed to study $P_{\ge 3}$-factor uniform graphs and pose some new graphic parameter conditions for the existence of $P_{\ge 3}$-factor uniform graphs, which are shown in the following.

Theorem 1.3

Let G be a 2-edge-connected graph. If G satisfies

$$\begin{aligned} \delta (G)>\frac{\alpha (G)+4}{2}, \end{aligned}$$

then G is a $P_{\ge 3}$-factor uniform graph.

Theorem 1.4

Let k be a positive integer and $\gamma$ be a real number with $\frac{1}{3}\le \gamma \le 1$, and let G be a $(k+2)$-connected graph of order n with $n\ge 5k+3-\frac{3}{5\gamma -1}$. If

$$\begin{aligned} |N_G(A)|>\gamma (n-3k-2)+k+2 \end{aligned}$$

for any independent set A of G with $|A|=\lfloor \gamma (2k+1)\rfloor$, then G is a $P_{\ge 3}$-factor uniform graph.

The proofs of Theorems 1.3 and 1.4 will be given in Sections 2 and 3.

2 The proof of Theorem 1.3

Proof of Theorem 1.3

For any $e=xy\in E(G)$, let $G'=G-e$. To verify Theorem 1.3, we only need to prove that $G'$ is a $P_{\ge 3}$-factor covered graph. Suppose, to the contrary, that $G'$ is not a $P_{\ge 3}$-factor covered graph. Then it follows from Theorem 1.2 that

$$\begin{aligned} sun(G'-X)\ge 2|X|-\varepsilon (X)+1 \end{aligned}$$

(2.1)

for some vertex subset X of $G'$.

Claim 1. $X\ne \emptyset$.

Proof

Assume that $X=\emptyset$. Then from (2.1) and $\varepsilon (X)=0$ we have $sun(G')\ge 1$. On the other hand, since G is 2-edge-connected, $G'$ is connected, which implies that $\omega (G')=1$. Thus, we derive that $1\le sun(G')\le \omega (G')=1$, that is, $sun(G')=1$. Note that $|V(G')|=|V(G)|\ge 3$ by G being a 2-edge-connected graph. Hence, $G'$ is a big sun, which implies that there exist at least three vertices $x_1,x_2,x_3$ with $d_{G'}(x_i)=1$, $i=1,2,3$. Thus, there exists at least one vertex with degree 1 in G, which contradicts that G is 2-edge-connected. Claim 1 is proved. $\square$

Claim 2. $|X|\ge 2$.

Proof

Let $|X|\le 1$. Combining this with Claim 1, we get $|X|=1$.

If $G'-X$ admits a non-sun component, then $\varepsilon (X)=1$ by the definition of $\varepsilon (X)$. According to (2.1) and $\varepsilon (X)=1$, we obtain

$$\begin{aligned} sun(G'-X)\ge 2|X|-\varepsilon (X)+1=2|X|=2. \end{aligned}$$

(2.2)

Note that $G'-X$ includes a non-sun component. Combining this with (2.2), we get

$$\begin{aligned} \alpha (G')\ge sun(G'-X)+1. \end{aligned}$$

(2.3)

Since $G'=G-e$, we deduce $\alpha (G)\ge \alpha (G')-2$. Then using (2.2) and (2.3), we infer

$$\begin{aligned} \alpha (G)\ge \alpha (G')-2\ge sun(G'-X)-1\ge 2-1=1. \end{aligned}$$

(2.4)

By virtue of (2.2), $G'-X$ has at least two sun components, which implies that $G-X$ admits one vertex v with $d_{G-X}(v)=1$. Thus, we derive

$$\begin{aligned} \delta (G)\le d_G(v)\le d_{G-X}(v)+|X|=|X|+1=2. \end{aligned}$$

(2.5)

It follows from (2.4), (2.5) and $\delta (G)>\frac{\alpha (G)+4}{2}$ that

$$\begin{aligned} 2\ge \delta (G)>\frac{\alpha (G)+4}{2}\ge \frac{5}{2}, \end{aligned}$$

which is a contradiction.

If $G'-X$ does not admit a non-sun component, then $\varepsilon (X)=0$ by the definition of $\varepsilon (X)$. By means of (2.1), $|X|=1$ and $\varepsilon (X)=0$, we get

$$\begin{aligned} \alpha (G')\ge sun(G'-X)\ge 2|X|+1=3. \end{aligned}$$

(2.6)

From (2.6), we have

$$\begin{aligned} \alpha (G)\ge \alpha (G')-2\ge 3-2=1. \end{aligned}$$

(2.7)

Note that $sun(G-X)\ge sun(G'-X)-2\ge 3-2=1$ by (2.6), which implies that $G-X$ has at least one vertex v with $d_{G-X}(v)\le 1$. Thus, we infer

$$\begin{aligned} \delta (G)\le d_G(v)\le d_{G-X}(v)+|X|\le |X|+1=2. \end{aligned}$$

(2.8)

In terms of (2.7), (2.8) and $\delta (G)>\frac{\alpha (G)+4}{2}$, we derive

$$\begin{aligned} 2\ge \delta (G)>\frac{\alpha (G)+4}{2}\ge \frac{5}{2}, \end{aligned}$$

which is a contradiction. This completes the proof of Claim 2. $\square$

Suppose that there exist a isolated vertices, b $K_2$’s and c big sun components $H_1,H_2,\ldots ,H_c$, where $|V(H_i)|\ge 6$, in $G'-X$, and so

$$\begin{aligned} sun(G'-X)=a+b+c. \end{aligned}$$

(2.9)

It follows from (2.1), (2.9), $\varepsilon (X)\le 2$ and Claim 2 that

$$\begin{aligned} a+b+c=sun(G'-X)\ge 2|X|-\varepsilon (X)+1\ge 2|X|-1\ge 3. \end{aligned}$$

(2.10)

Claim 3. $\delta (G)\le |X|+1$.

Proof

If $a\ne 0$, then $d_{G'-X}(v)=0$ for any $v\in V(aK_1)$. Note that $G'=G-e$. Thus, we infer $d_{G-X}(v)\le 1$ for any $v\in V(aK_1)$, and so

$$\begin{aligned} \delta (G)\le d_G(v)\le d_{G-X}(v)+|X|\le |X|+1. \end{aligned}$$

If $a=0$, then $b+c\ne 0$, which implies that $G'-X$ admits at least two vertices with degree 1, and so $G-X$ has at least one vertex v with $d_{G-X}(v)=1$. Thus, we obtain

$$\begin{aligned} \delta (G)\le d_G(v)\le d_{G-X}(v)+|X|=|X|+1. \end{aligned}$$

This completes the proof of Claim 3. $\square$

Next, we consider two cases by the value of $a+c$.

Case 1. $a+c=0$.

In this case, $b\ge 3$ by (2.10).

Claim 4. $\alpha (G)\ge b$.

Proof

If $x\notin V(bK_2)$ or $y\notin V(bK_2)$, then we easily see that $\alpha (G)\ge b$. If $x\in V(bK_2)$ and $y\in V(bK_2)$, then $G-X$ has $(b-2)$ $K_2$’s and a $P_4$ component, and so we easily see that $\alpha (G)\ge (b-2)+2=b$. We have finished the proof of Claim 4. $\square$

According to (2.10), $a+c=0$, Claim 4 and $\delta (G)>\frac{\alpha (G)+4}{2}$, we deduce

$$\begin{aligned} \delta (G)&>\frac{\alpha (G)+4}{2}\ge \frac{b+4}{2}=\frac{a+b+c+4}{2}\\&\ge \frac{2|X|-1+4}{2}=\frac{2|X|+3}{2}>|X|+1, \end{aligned}$$

which contradicts Claim 3.

Case 2. $a+c\ne 0$.

Subcase 2.1. $a\ne 0$.

If $x\notin V(aK_1)$ and $y\notin V(aK_1)$, then $d_{G-X}(v)=0$ for any $v\in V(aK_1)$. Thus, we derive

$$\begin{aligned} \delta (G)\le d_G(v)\le d_{G-X}(v)+|X|=|X|. \end{aligned}$$

(2.11)

It follows from (2.10), (2.11), $\delta (G)>\frac{\alpha (G)+4}{2}$ and $\alpha (G)\ge sun(G-X)\ge sun(G'-X)-2$ that

$$\begin{aligned} |X|&\ge \delta (G)>\frac{\alpha (G)+4}{2}\ge \frac{sun(G'-X)-2+4}{2}=\frac{sun(G'-X)+2}{2}\\&\ge \frac{2|X|-1+2}{2}=|X|+\frac{1}{2}, \end{aligned}$$

which is a contradiction. In what follows, we discuss the case with $x\in V(aK_1)$ or $y\in V(aK_1)$. Without loss of generality, let $x\in V(aK_1)$. We write $Y=V(H_1)\cup \cdots \cup V(H_c)$.

Subcase 2.1.1. $y\in V(bK_2)\cup Y$.

In this subcase, we deduce $\alpha (G)\ge a+b+c$. Combining this with (2.10) and $\delta (G)>\frac{\alpha (G)+4}{2}$, we infer

$$\begin{aligned} \delta (G)>\frac{\alpha (G)+4}{2}\ge \frac{a+b+c+4}{2}\ge \frac{2|X|-1+4}{2}=\frac{2|X|+3}{2}>|X|+1, \end{aligned}$$

which contradicts Claim 3.

Subcase 2.1.2. $y\in V(G)\setminus (V(bK_2)\cup Y)$.

In this subcase, we have $sun(G-X)\ge sun(G'-X)-1$. Combining this with (2.10), $\alpha (G)\ge sun(G-X)$ and $\delta (G)>\frac{\alpha (G)+4}{2}$, we derive

$$\begin{aligned} \delta (G)&>\frac{\alpha (G)+4}{2}\ge \frac{sun(G-X)+4}{2}\ge \frac{sun(G'-X)-1+4}{2}\\&=\frac{sun(G'-X)+3}{2}\ge \frac{2|X|-1+3}{2}=|X|+1, \end{aligned}$$

which contradicts Claim 3.

Subcase 2.2. $c\ne 0$.

Obviously, $\alpha (G')\ge a+b+\sum \limits _{i=1}^{c}{\frac{|V(H_i)|}{2}}\ge a+b+3c$ by $|V(H_i)|\ge 6$. Combining this with (2.10), $c\ne 0$ and $\alpha (G)\ge \alpha (G')-2$, we obtain

$$\begin{aligned} \alpha (G)\ge \alpha (G')-2\ge a+b+3c-2\ge a+b+c\ge 2|X|-1. \end{aligned}$$

(2.12)

By virtue of (2.12), Claim 3 and $\delta (G)>\frac{\alpha (G)+4}{2}$, we deduce

$$\begin{aligned} |X|+1\ge \delta (G)>\frac{\alpha (G)+4}{2}\ge \frac{2|X|-1+4}{2}=|X|+\frac{3}{2}, \end{aligned}$$

which is a contradiction. This completes the proof of Theorem 1.3. $\square$

3 The proof of Theorem 1.4

Proof of Theorem 1.4

For any $e\in E(G)$, we write $G'=G-e$. To prove Theorem 1.4, we only need to justify that $G'$ is a $P_{\ge 3}$-factor covered graph. Suppose, to the contrary, that $G'$ is not a $P_{\ge 3}$-factor covered graph. Then by Theorem 1.2, we have

$$\begin{aligned} sun(G'-X)\ge 2|X|-\varepsilon (X)+1 \end{aligned}$$

(3.1)

for some vertex subset X of $G'$. We write $a=i(G-X)$ and $b=\lfloor \gamma (2k+1)\rfloor$.

Claim 1. $b\ge a+1$.

Proof

Let $b\le a$. We may choose b isolated vertices $x_1,x_2,\ldots ,x_b$ in $G-X$. Write $A=\{x_1,x_2,\ldots ,x_b\}$. Then A is an independent set of G. Thus, we infer

$$\begin{aligned} \gamma (n-3k-2)+k+2<|N_G(A)|\le |X|. \end{aligned}$$

(3.2)

It follows from (3.1), (3.2) and $\varepsilon (X)\le 2$, $\frac{1}{3}\le \gamma \le 1$ and $n\ge 5k+3-\frac{3}{5\gamma -1}$ that

$$\begin{aligned} 0&\ge |X|+sun(G'-X)-n\ge |X|+2|X|-\varepsilon (X)+1-n\\&\ge 3|X|-n-1>3(\gamma (n-3k-2)+k+2)-n-1\\&=(3\gamma -1)n-3\gamma (3k+2)+3k+5\\&\ge (3\gamma -1)\left( 5k+3-\frac{3}{5\gamma -1}\right) -3\gamma (3k+2)+3k+5\\&=(3\gamma -1)(2k+1)-\frac{3(3\gamma -1)}{5\gamma -1}+3\\&\ge 3-\frac{3(3\gamma -1)}{5\gamma -1}>3-3=0, \end{aligned}$$

which is a contradiction. We have finished the proof of Claim 1. $\square$

In what follows, we consider four cases by the value of |X| and derive a contradiction in each case.

Case 1. $|X|=0$.

Note that $G'=G-e$ and G is $(k+2)$-connected. Hence, $G'$ is $(k+1)$-connected and $\omega (G')=1$. Combining this with (3.1) and $\varepsilon (X)=0$, we obtain $1=\omega (G')\ge sun(G')\ge 1$. Thus, we have $sun(G')=\omega (G')=1$. Then using $n\ge 5k+3-\frac{3}{5\gamma -1}\ge 8-\frac{3}{5\times \frac{1}{3}-1}=\frac{7}{2}>3$, we see that $G'$ is a big sun, and so $G'$ has at least three vertices with degree 1, which contradicts that $G'$ is a $(k+1)$-connected graph.

Case 2. $1\le |X|\le k$.

Note that $1\le |X|\le k$ and $G'$ is $(k+1)$-connected. We derive $\omega (G'-X)=1$. According to (3.1) and $\varepsilon (X)\le |X|$, we get

$$\begin{aligned} 1=\omega (G'-X)\ge sun(G'-X)\ge 2|X|-\varepsilon (X)+1\ge |X|+1\ge 2, \end{aligned}$$

which is a contradiction.

Case 3. $|X|=k+1$.

Since G is $(k+2)$-connected, $G-X$ is connected, and so $\omega (G-X)=1$. Note that $G'=G-e$. Thus, we deduce

$$\begin{aligned} \omega (G'-X)\le \omega (G-X)+1=2. \end{aligned}$$

(3.3)

By virtue of (3.1), (3.3), $k\ge 1$ and $\varepsilon (X)\le 2$, we infer

$$\begin{aligned} 2&\ge \omega (G'-X)\ge sun(G'-X)\ge 2|X|-\varepsilon (X)+1\ge 2|X|-1\\&=2(k+1)-1=2k+1\ge 3, \end{aligned}$$

which is a contradiction.

Case 4. $|X|\ge k+2$.

In light of (3.1), $\varepsilon (X)\le 2$ and $\frac{1}{3}\le \gamma \le 1$, we derive

$$\begin{aligned} sun(G-X)&\ge sun(G'-X)-2\ge 2|X|-\varepsilon (X)+1-2\ge 2|X|-3\\&\ge 2(k+2)-3=2k+1\ge \gamma (2k+1)\ge \lfloor \gamma (2k+1)\rfloor =b, \end{aligned}$$

which implies that $G-X$ admits an independent set of order at least b. Then using Claim 1, we may choose a isolated vertices $x_1,x_2,\ldots ,x_a$ and $(b-a)$ nonadjacent vertices $x_{a+1},\ldots ,x_b$ with $d_{G-X}(x_i)=1$ for $a+1\le i\le b$, in $G-X$. Set $A=\{x_1,x_2,\ldots ,x_a,x_{a+1},\ldots ,x_b\}$. Then A is an independent set of G. Thus, we deduce

$$\begin{aligned} \gamma (n-3k-2)+k+2<|N_G(A)|\le |X|+b-a, \end{aligned}$$

that is,

$$\begin{aligned} |X|>\gamma (n-3k-2)+k+2-b+a. \end{aligned}$$

(3.4)

It follows from (3.1), (3.4), $\varepsilon (X)\le 2$ and $n\ge 5k+3-\frac{3}{5\gamma -1}$ that

$$\begin{aligned} 0\ge & {} |X|+2sun(G'-X)-i(G'-X)-n\\\ge & {} |X|+2(2|X|-\varepsilon (X)+1)-(i(G-X)+2)-n\\\ge & {} |X|+2(2|X|-1)-(a+2)-n\\= & {} 5|X|-a-4-n\\> & {} 5(\gamma (n-3k-2)+k+2-b+a)-a-4-n\\= & {} (5\gamma -1)n-5\gamma (3k+2)+5k+10-5b+4a-4\\\ge & {} (5\gamma -1)\left( 5k+3-\frac{3}{5\gamma -1}\right) -5\gamma (3k+2)+5k+6-5b\\= & {} 5\gamma (2k+1)-5b\\= & {} 5\gamma (2k+1)-5\lfloor \gamma (2k+1)\rfloor \\\ge & {} 0, \end{aligned}$$

which is a contradiction. This completes the proof of Theorem 1.4. $\square$

4 Remarks

Remark 1

Next, we show that the condition $\delta (G)>\frac{\alpha (G)+4}{2}$ in Theorem 1.3 cannot be replaced by $\delta (G)\ge \frac{\alpha (G)+4}{2}$. We construct a graph $G=K_{3+t}\vee (4+2t)K_2$, where t is a nonnegative integer. Then G is $(3+t)$-connected, $\delta (G)=4+t$ and $\alpha (G)=4+2t$. Thus, we have $\delta (G)=\frac{\alpha (G)+4}{2}$. For any $e\in E((4+2t)K_2)$, let $G'=G-e=K_{3+t}\vee ((3+2t)K_2\cup (2K_1))$. Select $X=V(K_{3+t})\subseteq V(G')$. Then $|X|=3+t$ and $\varepsilon (X)=2$. Thus, we derive

$$\begin{aligned} sun(G'-X)=5+2t>4+2t=2(3+t)-2=2|X|-\varepsilon (X). \end{aligned}$$

By Theorem 1.2, $G'$ is not a $P_{\ge 3}$-factor covered graph, and so G is not a $P_{\ge 3}$-factor uniform graph.

Remark 2

The conditions with a $(k+2)$-connected graph and $|N_G(A)|>\gamma (n-3k-2)+k+2$ in Theorem 1.4 cannot be replaced by a $(k+1)$-connected graph and $|N_G(A)|\ge \gamma (n-3k-2)+k+1$. Let $\gamma$ be a rational number such that $\frac{1}{3}\le \gamma \le 1$. Then we can write $\gamma =\frac{b}{2k+1}$ for nonnegative integers b and k. Let $G=K_{k+1}\vee ((2k+1)K_2)$, where k is a positive integer. Then G is $(k+1)$-connected and $n=|V(G)|=5k+3>5k+3-\frac{3}{5\gamma -1}$. If A is an independent set of order $b=\gamma (2k+1)$, then

$$\begin{aligned} \gamma (n-3k-2)+k+2>|N_G(A)|=\gamma (2k+1)+k+1=\gamma (n-3k-2)+k+1. \end{aligned}$$

For any $e\in E((2k+1)K_2)$, let $G'=G-e=K_{k+1}\vee ((2k)K_2\cup (2K_1))$. Select $X=V(K_{k+1})\subseteq V(G')$. Then $|X|=k+1$ and $\varepsilon (X)=2$. Thus, we infer

$$\begin{aligned} sun(G'-X)=2k+2>2k=2(k+1)-2=2|X|-\varepsilon (X). \end{aligned}$$

According to Theorem 1.2, $G'$ is not a $P_{\ge 3}$-factor covered graph, and so G is not a $P_{\ge 3}$-factor uniform graph.

5 Conclusion

The concept of path-factor uniform graph was first presented by Zhou and Sun [27], and they showed a binding number condition for the existence of $P_{\ge 3}$-factor uniform graphs. Gao and Wang [5], Liu [12] improved Zhou and Sun’s above result. Hua [6] gave toughness and isolated toughness conditions for graphs to be $P_{\ge 3}$-factor uniform graphs. In our article, we study the relationships between some graphic parameters (for instance, minimum degree, independence number and neighborhood, and so on) and the existence of $P_{\ge 3}$-factor uniform graphs. The theorems derived in this article belong to existence theorems, that is, under what kind of conditions the path-factor uniform graph exists. However, in a specific computer network, it needs to use a certain algorithm to determine the values of some graphic parameters of the fix network graph and show the eligible path-factor uniform graph from the algorithm point of view. The problems of such algorithms are worthy of consideration in future research.

So far, results on the existence of path-factor uniform graphs are very few. There are many problems on graphs which can be considered for path-factor uniform graphs. For example, we can consider the structures and properties of path-factor uniform graphs. In what follows, we put forward open problems as the end of our article.

Problem 1. Find the necessary and sufficient conditions for a graph to be a path-factor uniform graph.

Problem 2. Find relationships between other graphic parameters and path-factor uniform graphs.

Problem 3. What are the structures and properties in path-factor uniform graphs?