The existence of path-factor uniform graphs with large connectivity

Zhou, Sizhong; Bian, Qiuxiang

RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2919-2927

A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices. Let k ≥ 2 be an integer. A P$$-factor of G means a path factor in which each component is a path with at least k vertices. A graph G is a P$$-factor covered graph if for any e ∈ E(G), G has a P$$-factor covering e. A graph G is called a P$$-factor uniform graph if for any e₁, e₂ ∈ E(G) with e₁ ≠ e₂, G has a P$$-factor covering e₁ and avoiding e₂. In other words, a graph G is called a P$$-factor uniform graph if for any e ∈ E(G), G − e is a P$$-factor covered graph. In this paper, we present two sufficient conditions for graphs to be P_≥3-factor uniform graphs depending on binding number and degree conditions. Furthermore, we show that two results are best possible in some sense.

Classification : 05C70, 05C38
Keywords: Graph, degree condition, binding number, $$_≥3-factor, $$_≥3-factor uniform graph

[1] C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Woźniak, Partitioning vertices of $1$-tough graph into paths. Theor. Comput. Sci. 263 (2001) 255–261. | DOI

[2] Y. Egawa and M. Furuya, The existence of a path-factor without small odd paths. Electron. J. Comb. 25 (2018) #P1.40. | MR | DOI

[3] W. Gao and W. Wang, Tight binding number bound for $P_{\ge 3}$-factor uniform graphs. Inf. Process. Lett. 172 (2021) 106162. | MR | DOI

[4] W. Gao, W. Wang and Y. Chen, Tight bounds for the existence of path factors in network vulnerability parameter settings. Int. J. Intell. Syst. 36 (2021) 1133–1158. | DOI

[5] H. Hua, Toughness and isolated toughness conditions for $P_{\ge 3}$-factor uniform graphs. J. Appl. Math. Comput. 66 (2021) 809–821. | MR | DOI

[6] M. Johnson, D. Paulusma and C. Wood, Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Math. 310 (2010) 1413–1423. | MR | DOI

[7] 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. Comb. Theory Ser. B 88 (2003) 195–218. | MR | DOI

[8] M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two. Discrete Math. 283 (2004) 129–135. | MR | DOI

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

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

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

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

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

[14] D. Woodall, The binding number of a graph and its Anderson number. J. Comb. Theory Ser. B 15 (1973) 225–255. | MR | DOI

[15] 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 | DOI

[16] S. Zhou, A neighborhood union condition for fractional $(a,b,k)$-critical covered graphs. Discrete Appl. Math. (2021). DOI: . | DOI | MR

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

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

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

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

[21] 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 | DOI

[22] S. Zhou, Z. Sun and H. Liu, Isolated toughness and path-factor uniform graphs. RAIRO-Oper. Res. 55 (2021) 1279–1290. | MR | Zbl | Numdam | DOI

[23] S. Zhou, J. Wu and Y. Xu, Toughness, isolated toughness and path factors in graphs. Bull. Aust. Math. Soc. (2021). DOI: . | DOI | MR

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

[25] 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 | 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

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

[28] 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 | Numdam | DOI