Isolated toughness and path-factor uniform graphs

Zhou, Sizhong; Sun, Zhiren; Liu, Hongxia

RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1279-1290

A P$$-factor of a graph G is a spanning subgraph of G whose components are paths of order at least k. We say that a graph G is P$$-factor covered if for every edge e ∈ E(G), G admits a P$$-factor that contains e; and we say that a graph G is P$$-factor uniform if for every edge e ∈ E(G), the graph G−e is P$$-factor covered. In other words, G is P$$-factor uniform if for every pair of edges e₁, e₂ ∈ E(G), G admits a P$$-factor that contains e₁ and avoids e₂. In this article, we testify that (1) a 3-edge-connected graph G is P$$-factor uniform if its isolated toughness I(G) > 1; (2) a 3-edge-connected graph G is P$$-factor uniform if its isolated toughness I(G) > 2. Furthermore, we explain that these conditions on isolated toughness and edge-connectivity in our main results are best possible in some sense.

Classification : 05C70, 05C38, 90B10
Keywords: Graph, isolated toughness, edge-connectivity, path-factor, path-factor uniform graph

[1] S. Abdullah and M. Aslam, New multicriteria group decision support systems for small hydropower plant locations selection based on intuitionistic cubic fuzzy aggregation information. Int. J. Intell. Syst. 35 (2020) 983–1020. | DOI

[2] J. Akiyama, D. Avis and H. Era, On a $\{1,2\}$-factor of a graph. TRU Math. 16 (1980) 97–102. | MR | Zbl

[3] F. Chiclana, F. Mata, L. Pérez and E. Herrera-Viedma, Type-1 OWA unbalanced fuzzy linguistic aggregation methodology: application to eurobonds credit risk evaluation. Int. J. Intell. Syst. 33 (2018) 1071–1088. | DOI

[4] W. Gao and W. Wang, New isolated toughness condition for fractional $(g,f,n)$-critical graphs. Colloquium Math. 147 (2017) 55–66. | MR | Zbl | DOI

[5] W. Gao, L. Liang and Y. Chen, An isolated toughness condition for graphs to be fractional $(k,m)$-deleted graphs. Util. Math. 105 (2017) 303–316. | MR | Zbl

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

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

[10] J. Li, H. Yan, Z. Liu, X. Chen, X. Huang and D. Wong, Location-sharing systems with enhanced privacy in mobile online social networks. IEEE Syst. J. 11 (2017) 439–448. | DOI

[11] J. Li, L. Sun, Q. Yan, Z. Li, W. Srisa-An and H. Ye, Significant permission identification for machine-learning-based android malware detection. IEEE Trans. Ind. Inf. 14 (2018) 3216–3225. | DOI

[12] Z. Sun and S. Zhou, A generalization of orthogonal factorizations in digraphs. Inf. Process. Lett. 132 (2018) 49–54. | MR | Zbl | DOI

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

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

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

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

[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, Some results about component factors in graphs. RAIRO:OR 53 (2019) 723–730. | MR | Zbl | Numdam | DOI

[19] S. Zhou, Remarks on path factors in graphs. RAIRO:OR 54 (2020) 1827–1834. | MR | Zbl | Numdam | DOI

[20] S. Zhou, Some results on path-factor critical avoidable graphs. Discuss. Math. Graph Theory (2020). DOI: . | DOI | MR | Zbl

[21] S. Zhou, Binding numbers and restricted fractional $(g,f)$-factors in graphs. Discrete Appl. Math. (2020). DOI: . | DOI | MR | Zbl

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

[23] S. Zhou and Z. Sun, A neighborhood condition for graphs to have restricted fractional $(g,f)$-factors. Contrib. Discrete Math. 16 (2021) 138–149. | MR | Zbl | DOI

[24] S. Zhou, F. Yang and L. Xu, Two sufficient conditions for the existence of path factors in graphs. Sci. Iran. 26 (2019) 3510–3514.

[25] S. Zhou, Y. Xu and Z. Sun, Degree conditions for fractional $(a,b,k)$-critical covered graphs. Inf. Process. Lett. 152 (2019). | Zbl | MR | DOI

[26] S. Zhou, Z. Sun and Q. Pan, A sufficient condition for the existence of restricted fractional $(g,f)$-factors in graphs. Prob. Inf. Transm. 56 (2020) 332–344. | MR | Zbl | DOI

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

[28] S. Zhou, Q. Bian and Z. Sun, Two sufficient conditions for component factors in graphs. Discuss. Math. Graph Theory (2021). DOI: . | DOI | MR

[29] S. Zhou, H. Liu and Y. Xu, A note on fractional ID-[$a,b$]-factor-critical covered graphs. Discrete Appl. Math. (2021). DOI: . | DOI | MR | Zbl