Isolated toughness for path factors in networks

Wang, Sufang; Zhang, Wei

RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2613-2619

Let ℋ be a set of connected graphs. Then an ℋ-factor is a spanning subgraph of G, whose every connected component is isomorphic to a member of the set ℋ. An ℋ-factor is called a path factor if every member of the set ℋ is a path. Let k ≥ 2 be an integer. By a P$$-factor we mean a path factor in which each component path admits at least k vertices. A graph G is called a (P$$, n)-factor-critical covered graph if for any W ⊆ V(G) with |W| = n and any e ∈ E(G − W), G − W has a P$$-factor covering e. In this article, we verify that (1) an (n + λ + 2)-connected graph G is a (P_≥2, n)-factor-critical covered graph if its isolated toughness I(G)>n+λ+2 2λ+3, where n and λ are two nonnegative integers; (2) an (n + λ + 2)-connected graph G is a (P_≥3, n)-factor-critical covered graph if its isolated toughness I(G)>n+3λ+5 2λ+3, where n and λ be two nonnegative integers.

Classification : 05C70, 05C38
Keywords: Graph, isolated toughness, $$_≥k-factor, $$_≥k-factor covered graph, ($$_≥k, $$)-factor-critical covered graph

[1] R. Anstee and Y. Nam, More sufficient conditions for a graph to have factors. Discrete Math. 184 (1998) 15–24. | MR | DOI

[2] Y. Egawa, M. Kano and M. Yokota, Existence of all generalized fractional $(g,f)$-factors of graphs. Discrete Appl. Math. 283 (2020) 265–271. | 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] 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

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

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

[8] K. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs. J. Graph Theory 39 (2002) 188–193. | MR | DOI

[9] M. Las Vergnas, An extension of Tutte’s 1-factor theorem. Discrete Math. 23 (1978) 241–255. | MR | DOI

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

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

[12] S. Wang and W. Zhang, Remarks on fractional ID-$[a,b]$-factor-critical covered network graphs. Proc. Roman. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 22 (2021) 209–216. | MR

[13] J. Yang, Y. Ma and G. Liu, Fractional $(g,f)$-factors in graphs. Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390. | MR

[14] Y. Yuan and R. Hao, A neighborhood union condition for fractional ID-$[a,b]$-factor-critical graphs. Acta Math. Appl. Sin. Engl. Ser. 34 (2018) 775–781. | 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, Binding numbers and restricted fractional $(g,f)$-factors in graphs. Discrete Appl. Math. 305 (2021) 350–356. | MR | DOI

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

[20] S. Zhou, T. Zhang and Z. Xu, Subgraphs with orthogonal factorizations in graphs. Discrete Appl. Math. 286 (2020) 29–34. | MR | DOI

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

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

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

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

[25] S. Zhou, Z. Sun and H. Liu, On $P_{\ge 3}$-factor deleted graphs. Acta Math. Appl. Sin. Engl. Ser. 38 (2022) 178–186. | MR | DOI

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