Path-factor critical covered graphs and path-factor uniform graphs

Wu, Jie

RAIRO. Operations Research, Tome 56 (2022) no. 6, pp. 4317-4325

A path-factor in a graph G is a spanning subgraph F of G such that every component of F is a path. Let d and n be two nonnegative integers with d ≥ 2. A P$$-factor of G is its spanning subgraph each of whose components is a path with at least d vertices. A graph G is called a P$$-factor covered graph if for any e ∈ E(G), G admits a P$$-factor containing e. A graph G is called a (P$$, n)-factor critical covered graph if for any N ⊆ V(G) with |N| = n, the graph G − N is a P$$-factor covered graph. A graph G is called a P$$-factor uniform graph if for any e ∈ E(G), the graph G − e is a P$$-factor covered graph. In this paper, we verify the following two results: (i) An (n + 1)-connected graph G of order at least n + 3 is a (P_≥3, n)-factor critical covered graph if G satisfies δ(G)>α(G)+2n+3 2; (ii) Every regular graph G with degree r ≥ 2 is a P_≥3-factor uniform graph.

Classification : 05C70, 05C38, 90B99
Keywords: Graph, minimum degree, independence number, $$_≥3-factor, ($$_≥3 $$)-factor critical covered graph, $$_≥3-factor uniform graph

[1] A. Asratian and C. Casselgren, On path factors of $(3,4)$-biregular bigraphs. Graphs Combin. 24 (2008) 405–411. | MR | Zbl | DOI

[2] S. Bekkai, Minimum degree, independence number and pseudo $[2,b]$-factors in graphs. Discrete Appl. Math. 162 (2014) 108–114. | MR | Zbl | DOI

[3] G. Dai, Z. Zhang, Y. Hang and X. Zhang, Some degree conditions for $P_{\ge k}$-factor covered graphs. RAIRO-Oper. Res. 55 (2021) 2907–2913. | MR | Zbl | Numdam | DOI

[4] Y. Egawa, M. Furuya and K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components. J. Graph Theory 89 (2018) 327–340. | MR | Zbl | DOI

[5] A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory Ser. B 88 (2003) 195–218. | MR | Zbl | DOI

[6] M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs. Discuss. Math. Graph Theory 28 (2008) 551–556. | MR | Zbl | DOI

[7] M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs. Appl. Math. Lett. 23 (2010) 385–389. | MR | Zbl | DOI

[8] A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics. Discrete Appl. Math. 159 (2011) 112–127. | MR | Zbl | DOI

[9] M. Kouider and S. Ouatiki, Sufficient condition for the existence of an even $[a,b]$-factor in graph. Graphs Combin. 29 (2013) 1051–1057. | MR | Zbl | DOI

[10] H. Liu, Binding number for path-factor uniform graphs. Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 23 (2022) 25–32. | MR | Zbl

[11] R. Matsubara, H. Matsumura, M. Tsugaki and T. Yamashita, Degree sum conditions for path-factors with specified end vertices in bipartite graphs. Discrete Math. 340 (2017) 87–95. | MR | Zbl | DOI

[12] H. Wang, Path factors of bipartite graphs. J. Graph Theory 18 (1994) 161–167. | MR | Zbl | DOI

[13] S. Wang and W. Zhang, Research on fractional critical covered graphs. Probl. Inf. Transm. 56 (2020) 270–277. | Zbl | DOI

[14] S. Wang and W. Zhang, On $k$-orthogonal factorizations in networks. RAIRO-Oper. Res. 55 (2021) 969–977. | MR | Zbl | Numdam | DOI

[15] S. Wang and W. Zhang, Isolated toughness for path factors in networks. RAIRO-Oper. Res. 56 (2022) 2613–2619. | MR | Zbl | Numdam | DOI

[16] Y. Yuan and R. Hao, Independence number, connectivity and all fractional (a, b, k)-critical graphs. Discuss. Math. Graph Theory 39 (2019) 183–190. | MR | Zbl | DOI

[17] H. Zhang and S. Zhou, Characterizations for $P_{\ge 2}$-factor and $P_{\ge 3}$-factor covered graphs. Discrete Math. 309 (2009) 2067–2076. | MR | Zbl | DOI

[18] S. Zhou, A result on fractional $(a,b,k)$-critical covered graphs. Acta Math. Appl. Sin. Engl. Ser. 37 (2021) 657–664. | MR | Zbl | DOI

[19] S. Zhou, A neighborhood union condition for fractional $(a,b,k)$-critical covered graphs. Discrete Appl. Math. 323 (2022) 343–348. | MR | Zbl | DOI

[20] S. Zhou, A note of generalization of fractional ID-factor-critical graphs. Fund. Inform. 187 (2022) 61–69. | MR | Zbl

[21] S. Zhou, Path factors and neighborhoods of independent sets in graphs. Acta Math. Appl. Sin. Engl. Ser. (2022). DOI: . | DOI | MR | Zbl

[22] S. Zhou, Remarks on restricted fractional $(g,f)$-factors in graphs. Discrete Appl. Math. (2022). DOI: . | DOI | MR | Zbl

[23] S. Zhou and Q. Bian, The existence of path-factor uniform graphs with large connectivity. RAIRO-Oper. Res. 56 (2022) 2919–2927. | MR | Zbl | Numdam | DOI

[24] S. Zhou and H. Liu, Discussions on orthogonal factorizations in digraphs. Acta Math. Appl. Sin. Engl. Ser. 38 (2022) 417–425. | MR | Zbl | DOI

[25] S. Zhou and Z. Sun, Binding number conditions for $P_{\ge 2}$-factor and $P_{\ge 3}$-factor uniform graphs. Discrete Math. 343 (2020) 111715. | MR | Zbl | DOI

[26] S. Zhou, Z. Sun and Q. Bian, Isolated toughness and path-factor uniform graphs (II). Indian J. Pure Appl. Math. (2022). DOI: . | DOI | MR | Zbl

[27] S. Zhou, Q. Bian and Q. Pan, Path factors in subgraphs. Discrete Appl. Math. 319 (2022) 183–191. | MR | Zbl | DOI

[28] S. Zhou, H. Liu and Y. Xu, A note on fractional ID-$[a,b]$-factor-critical covered graphs. Discrete Appl. Math. 319 (2022) 511–516. | MR | Zbl | DOI

[29] S. Zhou, J. Wu and Q. Bian, On path-factor critical deleted (or covered) graphs. Aequationes Math. 96 (2022) 795–802. | MR | Zbl | DOI

[30] S. Zhou, J. Wu and H. Liu, Independence number and connectivity for fractional $(a,b,k)$-critical covered graphs. RAIRO-Oper. Res. 56 (2022) 2535–2542. | MR | Zbl | Numdam | DOI

[31] S. Zhou, J. Wu and Y. Xu, Toughness, isolated toughness and path factors in graphs. Bull. Aust. Math. Soc. 106 (2022) 195–202. | MR | Zbl | DOI