Two sufficient conditions for the existence of path factors in graphs

Document Type : Article

Authors

1 School of Science, Jiangsu University of Science and Technology Mengxi Road 2, Zhenjiang, Jiangsu 212003, People's Republic of China

2 School of Science, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, P. R. China.

3 Department of Mathematics, Changji University, Changji, Xinjiang 831100, P. R. China.

Abstract

A graph G is called a (P≥n, k)-factor critical graph if G − U has a P≥ n -factor for any U ⊆ V(G) with|U|=k.  A graphG is called a (P≥n, m)-factor deleted graph if.............

Keywords

Main Subjects


Refrences:
1.Alspach, B., Heinrich, K., and Liu, G. Orthogonal factorizations of graphs", in: J.H. Dinitz, D. R. Stinson (Eds.), Contemporary Design Theory: A Collection of Surveys, Wiley, New York, pp. 13-37 (1992).
2. Rezaei, S. and Afshin Hemmatyar, A.M. CMORC: Class-based Multipath On-demand Routing protocol for Cognitive radio networks", Scientia Iranica, 24(6), pp. 3117-3131 (2017).
3. Chv_atal, V. Tough graphs and Hamiltonian circuits", Discrete Mathematics, 5, pp. 215-228 (1973).
4. Bondy, J.A. and Murty, U.S.R., Graph Theory, Springer, Berlin (2008). 5. Wang, H. Path factors of bipartite graphs", Journal of Graph Theory, 18, pp. 161-167 (1994). 6. Kaneko, A. A necessary and su_cient condition for the existence of a path factor every component of which is a path of length at least two", Journal of Combinatorial Theory, Series B, 88, pp. 195-218 (2003). 7. Zhou, S. and Zhang, T. Some existence theorems on all fractional (g; f)-factors with prescribed properties", Acta Mathematicae Applicatae Sinica, English Series, 34(2), pp. 344-350 (2018). 3514 S. Zhou et al./Scientia Iranica, Transactions D: Computer Science & ... 26 (2019) 3510{3514 8. Zhou, S., Yang, F., and Sun, Z. A neighborhood condition for fractional ID-[a; b]-factor-critical graphs", Discussiones Mathematicae Graph Theory, 36(2), pp. 409-418 (2016). 9. Zhou, S., Wu, J., and Zhang, T. The existence of P_3- factor covered graphs", Discussiones Mathematicae Graph Theory, 37(4), pp. 1055-1065 (2017). 10. Zhou, S. Some results about component factors in graphs", RAIRO-Operations Research, DOI: 10.1051/ro/2017045. 11. Zhou, S., Liu, H., and Zhang, T. Randomly orthogonal factorizations with constraints in bipartite networks", Chaos, Solitons and Fractals, 112, pp. 31- 35 (2018). 12. Zhou, S. and Bian, Q. Subdigraphs with orthogonal factorizations of digraphs (II)", European Journal of Combinatorics, 36, pp. 198-205 (2014). 13. Zhou, S. Remarks on orthogonal factorizations of digraphs", International Journal of Computer Mathematics, 91(10), pp. 2109-2117 (2014). 14. Zhou, S. A su_cient condition for a graph to be an (a; b; k)-critical graph", International Journal of Computer Mathematics, 87(10), pp. 2202-2211 (2010). 15. Zhou, S. and Sun, Z. Neighborhood conditions for fractional ID-k-factor-critical graphs", Acta Mathematicae Applicatae Sinica, English Series, 34(3), pp. 636-644 (2018). 16. Kawarabayashi, K., Matsuda, H., Oda, Y., and Ota, K. Path factors in cubic graphs", Journal of Graph Theory, 39, pp. 188-193 (2002). 17. Razzazi, M. and Sepahvand, A. Time complexity of two disjoint simple paths", Scientia Iranica, 24(3), pp. 1335-1343 (2017). 18. Johnson, M., Paulusma, D., and Wood, C. Path factors and parallel knock-out schemes of almost clawfree graphs", Discrete Mathematics, 310, pp. 1413- 1423 (2010). 19. Gao, W., Guirao, J., and Wu, H. Two tight independent set conditions for fractional (g; f;m)-deleted graphs systems", Qualitative Theory of Dynamical Systems, 17(1), pp. 231-243 (2018). 20. Gao, W. and Wang, W. Degree sum condition for fractional ID-k-factor-critical graphs", Miskolc Mathematical Notes, 18(2), pp. 751-758 (2017). 21. Gao, W., Liang, L., and Chen, Y. An isolated toughness condition for graphs to be fractional (k;m)- deleted graphs", Utilitas Mathematica, 105, pp. 303- 316 (2017). 22. Kano, M., Katona, G.Y., and Kir_aly, Z. Packing paths of length at least two", Discrete Mathematics, 283, pp. 129-135 (2004). 23. Kelmans, A. Packing 3-vertex paths in claw-free graphs and related topics", Discrete Applied Mathematics, 159, pp. 112-127 (2011).