Sufficient Conditions for a Graph $kG$ Admitting all $[1,k]$-factors

1. Introduction

The graphs discussed here are multigraphs, which may admit multiple edges but do not admit loops. A graph is called a simple graph if it admits neither multiple edges nor loops. For convenience, we simply call a multigraph a graph when we show notations and definitions. Let $G$ be a graph. We use $V(G)$ and $E(G)$ to denote the vertex set and the edge set of $G$, respectively. For $x\in V(G)$, we write $d_G(x)$ for the degree of $x$ in $G$, and $N_G(x)$ for the set of the vertices adjacent to $x$ in $G$. We write $N_G(X)=\bigcup _{x\in X}{N}_G(x)$ for any $X\subseteq V(G)$. We denote by $I(G)$ the set of isolated vertices of $G$, and by ${\omega }_{\ge k}(G)$ the number of components of $G$ with order at least $k$. Specially, we write $i(G)=|I(G)|$ and $\omega (G)={\omega }_{\ge 1}(G)$. Let $kG$ denote the graph derived from $G$ by replacing every edge of $G$ with $k$ parallel edges.

Let $g,f:V(G)\to \{0,1,2,3,\cdots \}$ be two functions satisfying $g(x)\le f(x)$ for every $x\in V(G)$. A $(g,f)$-factor of $G$ is defined as a spanning subgraph $F$ of $G$ such that $g(x)\le d_F(x)\le f(x)$ for every $x\in V(G)$. An $(f,f)$-factor is simply called an $f$-factor. If $g(x)\equiv 1$ and $f(x)\equiv k$ for any $x\in V(G)$, then a $(g,f)$-factor is called a $[1,k]$-factor, where $k\ge 1$ is a fixed integer. A $[1,1]$-factor is simply called a $1$-factor.

Let $\phi$ be a nonnegative integer-valued function defined on $V(G)$. In the following, we write $$\begin{array}{rlr}{D}_{g,f}^{even}& =& \{\phi :g(x)\le \phi (x)\le f(x)foreveryx\in V(G)\\ & & and\sum _{x\in V(G)}\phi (x)iseven\}.\end{array}$$ If for each $\phi \in D_{g,f}^{even}$, $G$ admits a $\phi$-factor, then we say that $G$ admits all $(g,f)$-factors. All $(g,f)$-factors are said to be all $[1,k]$-factors if $g(x)\equiv 1$ and $f(x)\equiv k$ for any $x\in V(G)$.

Lots of authors studied factors [1-16] and all factors [17-20] of graphs. The neighborhood conditions for graphs having factors were derived by many authors [21-27]. Lu, Kano and Yu [18] characterized a graph $G$ such that $kG$ admits all $[1,k]$-factors. Lu, Kano and Yu’s results generalized Tutte’s 1-factor theorem [28].

Theorem 1.([18]). Let $k\ge 2$ be an integer, and let $G$ be a connected multigraph. Then $kG$ admits all $[1,k]$-factors if and only if $$k\cdot i(G-X)+{\omega }_{\ge k+1}(G-X)\le |X|+1$$ for any $X\subseteq V(G)$.

Using Theorem 1, we verify some results related to all $[1,k]$-factors in graphs. Our main results will be shown in Section 2.

2. Next section

In this section, we discuss the relationship between neighborhood and all $[1,k]$-factors, and verify two results related to all $[1,k]$-factors.

Theorem 2.Let $k$ be an integer with $k\ge 2$, and let $G$ be a connected multigraph. If $G$ satisfies $$N_G(X)=V(G)or|N_G(X)|>(1+\frac{1}{k+1})|X|-1$$ for every $X\subset V(G)$, then $kG$ admits all $[1,k]$-factors.

 Assume that $G$ satisfies the hypothesis of Theorem 2, but $kG$ does not admit all $[1,k]$-factors. Then by Theorem 1, we derive $$\begin{array}{}\text{(1)}& k\cdot i(G-X)+{\omega }_{\ge k+1}(G-X)\ge |X|+2\end{array}$$ for some subset $X\subset V(G)$. The following proof will be divided into two cases by the value of $i(G-X)$.

Case 1. $i(G-X)=0$.

According to (1), we get $${\omega }_{\ge k+1}(G-X)\ge |X|+2,$$ which implies that $G-X$ has at least $|X|+2$ components with order at least $k+1$. We denote by $Y$ the set of vertices of any $|X|+1$ components of $G-X$ with order at least $k+1$. It is clear that $N_G(Y)\ne V(G)$. Thus, we derive $$\begin{array}{}\text{(2)}& |N_G(Y)|>(1+\frac{1}{k+1})|Y|-1.\end{array}$$

On the other hand, we easily see that $|N_G(Y)|\le |X|+|Y|$. Combining this with (2), we have $$|X|+|Y|\ge |N_G(Y)|>(1+\frac{1}{k+1})|Y|-1,$$ namely, $$\begin{array}{}\text{(3)}& |X|>\frac{1}{k+1}|Y|-1.\end{array}$$

Note that $|Y|\ge (k+1)(|X|+1)$. Then using (3), we admit $$|X|>\frac{1}{k+1}|Y|-1\ge (|X|+1)-1=|X|,$$ this is a contradiction.

Case 2. $i(G-X)>0$.

Obviously, $N_G(V(G)\setminus X)\ne V(G)$. Thus, we have $$\begin{array}{}\text{(4)}& |N_G(V(G)\setminus X)|>(1+\frac{1}{k+1})|V(G)\setminus X|-1=(1+\frac{1}{k+1})(|V(G)|-|X|)-1.\end{array}$$ Using (4) and $|N_G(V(G)\setminus X)|\le |V(G)|-i(G-X)$, we obtain $$|V(G)|-i(G-X)\ge |N_G(V(G)\setminus X)|>(1+\frac{1}{k+1})(|V(G)|-|X|)-1,$$ that is, $$\begin{array}{}\text{(5)}& |V(G)|+(k+1)\cdot i(G-X)<(k+2)\cdot |X|+k+1.\end{array}$$

On the other hand, we easily see that $$\begin{array}{}\text{(6)}& |V(G)|\ge i(G-X)+|X|+(k+1)\cdot (|X|+2)=i(G-X)+(k+2)\cdot |X|+2(k+1).\end{array}$$

It follows from (5) and (6) that $$\begin{array}{rl}& (k+2)\cdot |X|+k+1>|V(G)|+(k+1)\cdot i(G-X)\\ & \ge (G-X)+(k+2)\cdot |X|\\ & +2(k+1)+(k+1)\cdot i(G-X)\\ & =(k+2)\cdot i(G-X)+(k+2)\cdot |X|+2(k+1)\end{array}$$ which implies $$(k+2)\cdot i(G-X)+k+1<0,$$ which is a contradiction. Theorem 2 is proved. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Theorem 3. For any positive integer $k$ with $k\ge 2$, there exist infinitely many graphs $G$ that satisfy $$N_G(Y)=V(G)or|N_G(Y)|\ge (1+\frac{1}{k+1})|Y|-1$$ for every $Y\subset V(G)$, but $kG$ does not admit all $[1,k]$-factors.

 Let $r\ge 1$ be an integer. We construct a graph $G=K_r\vee ((r+2)K_{k+1})$, where $K_r$ denotes the complete graph of order $r$, $K_{k+1}$ denotes the complete graph of order $k+1$ and $\vee$ means “join”.

Next, we demonstrate that $$N_G(Y)=V(G)or|N_G(Y)|\ge (1+\frac{1}{k+1})|Y|-1$$ for every $Y\subset V(G)$. We shall consider two cases by the value of $|Y|$.

Case 1. $|Y|=1$.

In this case, we obviously have that $|N_G(Y)|\ge k+r>\frac{1}{k+1}=(1+\frac{1}{k+1})|Y|-1$.

Case 2. $|Y|\ge 2$.

Case 2.1. $Y\cap V(K_r)\ne \mathrm{\varnothing }$.

It is clear that $N_G(Y)=V(G)$.

Case 2.2. $Y\cap V(K_r)=\mathrm{\varnothing }$.

Let $K_{k+1}(i)$, $1\le i\le r+2$, denote the disjoint copies of $K_{k+1}$ in $G-V(K_r)$. Write $$b_1=\mathrm{\#}\{i:|Y\cap V(K_{k+1}(i))|=1\},$$ $$b_2=\mathrm{\#}\{i:|Y\cap V(K_{k+1}(i))|=2\},\cdots ,$$ and $$b_{k+1}=\mathrm{\#}\{i:|Y\cap V(K_{k+1}(i))|=k+1\}.$$ Thus, we derive $|Y|=b_1+2b_2+\cdots +(k+1)b_{k+1}$ and $|N_G(Y)|=r+k{b}_1+(k+1)(b_2+\cdots +b_{k+1})$. If $|Y|\le (k+1)(r+1+(k-1)b_1+(k-1)b_2+(k-2)b_3+\cdots +b_k)$, then we admit $$|N_G(Y)|=r+|Y|+(k-1)b_1+(k-1)b_2+(k-2)b_3+\cdots +b_k\ge (1+\frac{1}{k+1})|Y|-1.$$

In the following, we may assume that $|Y|>(k+1)(r+1+(k-1)b_1+(k-1)b_2+(k-2)b_3+\cdots +b_k)$. Note that $Y\cap V(K_r)=\mathrm{\varnothing }$. Thus, we have $|Y|\le |V(G)|-|V(K_r)|=(r+2)(k+1)$. Hence, we gain $$(k+1)(r+1+(k-1)b_1+(k-1)b_2+(k-2)b_3+\cdots +b_k)<|Y|\le (r+2)(k+1),$$ namely, $$(k-1)b_1+(k-1)b_2+(k-2)b_3+\cdots +b_k<1,$$ which implies $b_1=b_2=\cdots =b_k=0$, and so $|Y|=(k+1)b_{k+1}$. If $b_{k+1}=r+2$, then we derive $Y=V((r+2)K_{k+1})$, and so $N_G(Y)=V(G)$. Next, we assume that $b_{k+1}\le r+1$. Clearly, $|N_G(Y)|=r+(k+1)b_{k+1}=(k+2)b_{k+1}-1+r+1-b_{k+1}\ge (k+2)b_{k+1}-1=(1+\frac{1}{k+1})|Y|-1$.

Consequently, we verify that $$N_G(Y)=V(G)or|N_G(Y)|\ge (1+\frac{1}{k+1})|Y|-1$$ for every $Y\subset V(G)$.

Set $X=V(K_r)$. Then $i(G-X)=0$ and ${\omega }_{\ge k+1}(G-X)=r+2$. Thus, we deduce $$k\cdot i(G-X)+{\omega }_{\ge k+1}(G-X)=r+2=|X|+2>|X|+1.$$ Therefore, $kG$ does not admit all $[1,k]$-factors by Theorem 1. Theorem 3 is verified. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$