Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

Sufficient Conditions for a Graph \(kG\) Admitting all \([1,k]\)-factors

Jie Wu1
1School of Economic and management, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, China.
  • Received: 19/12/2019
  • Accepted: 23/09/2020
  • Published: 30/06/2024

Abstract

Let \(g,f:V(G)\rightarrow\{0,1,2,3,\cdots\}\) be two functions satisfying \(g(x)\leq 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)\leq d_F(x)\leq f(x)\) for every \(x\in V(G)\). An \((f,f)\)-factor is simply called
an \(f\)-factor. Let \(\varphi\) be a nonnegative integer-valued function defined on \(V(G)\). Set
\[
D_{g,f}^{even}=\Big\{\varphi: g(x)\leq\varphi(x)\leq f(x) \text{ for every } x\in V(G) \text{ and } \sum\limits_{x\in V(G)}\varphi(x) \text{ is even}\Big\}.
\]
If for each \(\varphi\in D_{g,f}^{even}\), \(G\) admits a \(\varphi\)-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)\equiv1\) and \(f(x)\equiv k\) for any \(x\in V(G)\). In this paper, we verify that for a connected multigraph
\(G\) satisfying \(N_G(X)=V(G) \text{ or } |N_G(X)|>\Big(1+\frac{1}{k+1}\Big)|X|-1\) for every \(X\subset V(G)\), \(kG\) admits all \([1,k]\)-factors, where
\(k\geq2\) is an integer and \(kG\) denotes the graph derived from \(G\) by replacing every edge of \(G\) with \(k\) parallel edges.

Keywords: Graph, Spanning subgraph, \(\varphi\)-factor, \([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\limits_{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_{\geq k}(G)\) the number of components of \(G\) with order at least \(k\). Specially, we write \(i(G)=|I(G)|\) and \(\omega(G)=\omega_{\geq1}(G)\). Let \(kG\) denote the graph derived from \(G\) by replacing every edge of \(G\) with \(k\) parallel edges.

Let \(g,f:V(G)\rightarrow\{0,1,2,3,\cdots\}\) be two functions satisfying \(g(x)\leq 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)\leq d_F(x)\leq f(x)\) for every \(x\in V(G)\). An \((f,f)\)-factor is simply called an \(f\)-factor. If \(g(x)\equiv1\) and \(f(x)\equiv k\) for any \(x\in V(G)\), then a \((g,f)\)-factor is called a \([1,k]\)-factor, where \(k\geq1\) is a fixed integer. A \([1,1]\)-factor is simply called a \(1\)-factor.

Let \(\varphi\) be a nonnegative integer-valued function defined on \(V(G)\). In the following, we write \[\begin{aligned} D_{g,f}^{even}&=&\Big\{\varphi: g(x)\leq\varphi(x)\leq f(x) \ for \ every \ x\in V(G)\\ &&and \ \sum\limits_{x\in V(G)}\varphi(x) \ is \ even\Big\}. \end{aligned}\] If for each \(\varphi\in D_{g,f}^{even}\), \(G\) admits a \(\varphi\)-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)\equiv1\) 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\geq2\) 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_{\geq k+1}(G-X)\leq|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\geq2\), and let \(G\) be a connected multigraph. If \(G\) satisfies \[N_G(X)=V(G) \ or \ |N_G(X)|>\Big(1+\frac{1}{k+1}\Big)|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 \[k\cdot i(G-X)+\omega_{\geq k+1}(G-X)\geq|X|+2\tag{1}\] 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_{\geq k+1}(G-X)\geq|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)\neq V(G)\). Thus, we derive \[|N_G(Y)|>\Big(1+\frac{1}{k+1}\Big)|Y|-1.\tag{2}\]

On the other hand, we easily see that \(|N_G(Y)|\leq|X|+|Y|\). Combining this with (2), we have \[|X|+|Y|\geq|N_G(Y)|>\Big(1+\frac{1}{k+1}\Big)|Y|-1,\] namely, \[|X|>\frac{1}{k+1}|Y|-1.\tag{3}\]

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

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

Obviously, \(N_G(V(G)\setminus X)\neq V(G)\). Thus, we have \[|N_G(V(G)\setminus X)|>\Big(1+\frac{1}{k+1}\Big)|V(G)\setminus X|-1=\Big(1+\frac{1}{k+1}\Big)(|V(G)|-|X|)-1.\tag{4}\] Using (4) and \(|N_G(V(G)\setminus X)|\leq|V(G)|-i(G-X)\), we obtain \[|V(G)|-i(G-X)\geq|N_G(V(G)\setminus X)|>\Big(1+\frac{1}{k+1}\Big)(|V(G)|-|X|)-1,\] that is, \[|V(G)|+(k+1)\cdot i(G-X)<(k+2)\cdot|X|+k+1.\tag{5}\]

On the other hand, we easily see that \[|V(G)|\geq i(G-X)+|X|+(k+1)\cdot(|X|+2)=i(G-X)+(k+2)\cdot|X|+2(k+1).\tag{6}\]

It follows from (5) and (6) that \[\begin{aligned}&(k+2)\cdot|X|+k+1>|V(G)|+(k+1)\cdot i(G-X)\\ &\geq(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{aligned}\] which implies \[(k+2)\cdot i(G-X)+k+1<0,\] which is a contradiction. Theorem 2 is proved. \(\Box\)

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

 Let \(r\geq1\) 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)|\geq\Big(1+\frac{1}{k+1}\Big)|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)|\geq k+r>\frac{1}{k+1}=\Big(1+\frac{1}{k+1}\Big)|Y|-1\).

Case 2. \(|Y|\geq2\).

Case 2.1. \(Y\cap V(K_r)\neq\emptyset\).

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

Case 2.2. \(Y\cap V(K_r)=\emptyset\).

Let \(K_{k+1}(i)\), \(1\leq i\leq r+2\), denote the disjoint copies of \(K_{k+1}\) in \(G-V(K_r)\). Write \[b_1=\#\{i:|Y\cap V(K_{k+1}(i))|=1\},\] \[b_2=\#\{i:|Y\cap V(K_{k+1}(i))|=2\},\cdots,\] and \[b_{k+1}=\#\{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+kb_1+(k+1)(b_2+\cdots+b_{k+1})\). If \(|Y|\leq(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\geq\Big(1+\frac{1}{k+1}\Big)|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)=\emptyset\). Thus, we have \(|Y|\leq|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|\leq(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}\leq r+1\). Clearly, \(|N_G(Y)|=r+(k+1)b_{k+1}=(k+2)b_{k+1}-1+r+1-b_{k+1}\geq(k+2)b_{k+1}-1=\Big(1+\frac{1}{k+1}\Big)|Y|-1\).

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

Set \(X=V(K_r)\). Then \(i(G-X)=0\) and \(\omega_{\geq k+1}(G-X)=r+2\). Thus, we deduce \[k\cdot i(G-X)+\omega_{\geq 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. \(\Box\)

References:

  1. K. Huang, K. Lih, A note on \(m\)-near-factor-critical graphs, European Journal of Combinatorics 80(2019)273–276.

  2. K. Ota, T. Tokuda, A degree condition for the existence of regular factors in \(K_{1,n}\)-free graphs, Journal of Graph Theory 22(1996)59–64.

  3. Y. Egawa, K. Kotani, 4-factors in 2-connected star-free graphs, Discrete Mathematics 309(2009)6265–6270.

  4. N. Haghparast, M. Kano, S. Maezawa, K. Ozeki, Connected odd factors of graphs, Australasian Journal of Combinatorics 73(1)(2019):200–206.

  5. S. Zhou, T. Zhang, Z. Xu, Subgraphs with orthogonal factorizations in graphs, Discrete Applied Mathematics 286(2020)29–34.

  6. S. Zhou, Y. Zhang, Z. Sun, The \(A_{\alpha}\)-spectral radius for path-factors in graphs, Discrete Mathematics 347(5)(2024)113940.

  7. S. Zhou, Z. Sun, H. Liu, \(\mathcal{D}\)-index and \(\mathcal{Q}\)-index for spanning trees with leaf degree at most \(k\) in graphs, Discrete Mathematics 347(5)(2024)113927.

  8. S. Zhou, Some results about component factors in graphs, RAIRO–Operations Research 53(3)(2019)723–730.

  9. S. Zhou, Z. Sun, F. Yang, A result on \(P_{\geq3}\)-factor uniform graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 23(1)(2022)3–8.

  10. S. Zhou, Remarks on path factors in graphs, RAIRO-Operations Research 54(6)(2020)1827–1834.

  11. S. Zhou, Y. Zhang, Sufficient conditions for fractional \([a,b]\)-deleted graphs, Indian Journal of Pure and Applied Mathematics, DOI: 10.1007/s13226-024-00564-w

  12. G. Liu, L. Zhang, Tougness and the existence of fractional \(k\)-factors of graphs, Discrete Mathematics 308(2008)1741–1748.

  13. S. Zhou, Y. Xu, Z. Sun, Degree conditions for fractional \((a,b,k)\)-critical covered graphs, Information Processing Letters 152(2019)105838.

  14. S. Zhou, Q. Pan, L. Xu, Isolated toughness for fractional \((2,b,k)\)-critical covered graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 24(1)(2023)11–18.

  15. S. Wang, W. Zhang, Independence number, minimum degree and path-factors in graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 23(3)(2022)229–234.

  16. X. Lv, A degree condition for fractional \((g,f,n)\)-critical covered graphs, AIMS Mathematics 5(2)(2020)872–878.

  17. T. Niessen, A characterization of graphs having all \((g,f)\)-factors, Journal of Combinatorial Theory, Series B 72(1998)152–156.

  18. H. Lu, M. Kano, Q. Yu, Characterizations of graphs \(G\) having all \([1,k]\)-factors in \(kG\), Discrete Mathematics 342(2019)111580.

  19. Y. Yuan, R. Hao, Toughness condition for the existence of all fractional \((a,b,k)\)-critical graphs, Discrete Mathematics 342(2019)2308–2314.

  20. S. Zhou, T. Zhang, Some existence theorems on all fractional \((g,f)\)-factors with prescribed properties, Acta Mathematicae Applicatae Sinica, English Series 34(2)(2018)344–350.

  21. M. Kano, A sufficient condition for a graph to have \([a,b]\)-factors, Graphs and Combinatorics 6(1990)245–251.

  22. H. Matsuda, A neighborhood condition for graphs to have \([a,b]\)-factors, Discrete Mathematics 224(2000)289–292.

  23. S. Zhou, Z. Sun, Some existence theorems on path factors with given properties in graphs, Acta Mathematica Sinica, English Series 36(8)(2020)917–928.

  24. S. Zhou, Z. Sun, Binding number conditions for \(P_{\geq2}\)-factor and \(P_{\geq3}\)-factor uniform graphs, Discrete Mathematics 343(3)(2020)111715.

  25. W. Gao, W. Wang, A tight neighborhood union condition on fractional \((g,f,n',m)\)-critical deleted graphs, Colloquium Mathematicum 149(2017)291–298.

  26. Y. Yuan, R. Hao, Neighborhood union conditions for fractional \([a,b]\)-covered graphs, Bulletin of the Malaysian Mathematical Sciences Society 43(2020)157–167.

  27. A. Anderson, Sufficient conditions for matchings, Proceedings of the Edinburgh Mathematical Society 18(1973)129–136.

  28. W. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22(1947)107–111.

Information
Guidelines
CP Initiatives
Follow CP
Facebook Twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Jie Wu. Sufficient Conditions for a Graph \(kG\) Admitting all \([1,k]\)-factors[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 120. 101-106. DOI: https://doi.org/10.61091/jcmcc120-09.