Two sufficient conditions for graphs to admit path factors

• Autorzy: Zhou, Sizhong , Wu, Jiancheng
• Języki publikacji: EN

Abstrakty

EN

Let A be a set of connected graphs. Then a spanning subgraph A of G is called an A-factor if each component of A is isomorphic to some member of A. Especially, when every graph in A is a path, A is a path factor. For a positive integer d ≥ 2, we write P≥d = {Pi|i ≥ d}. Then a P≥d-factor means a path factor in which every component admits at least d vertices. A graph G is called a (P≥d, m)-factor deleted graph if G − E′ admits a P≥d-factor for any E′ ⊆ E(G) with |E′| = m. A graph G is called a (P≥d, k)-factor critical graph if G − Q has a P≥d-factor for any Q ⊆ V (G) with |Q| = k. In this paper, we present two degree conditions for graphs to be (P≥3, m)-factor deleted graphs and (P≥3, k)-factor critical graphs. Furthermore, we show that the two results are best possible in some sense.

Słowa kluczowe

EN

graph; degree condition; P≥3-factor; (P≥3, m)-factor deleted graph; (P≥3, k)-factor critical graph.

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 191, nr 1
• Strony: 67--77
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Zhou, Sizhong

• School of Science Jiangsu University of Science and Technology, China

autor

Wu, Jiancheng

• School of Science Jiangsu University of Science and Technology, China,

Bibliografia

• [1] Bazgan C, Benhamdine A, Li H, Wo´zniak M. Partitioning vertices of 1-tough graph into paths, Theoretical Computer Science 2001. 263(1-2):255-261. doi:10.1016/S0304-3975(00)00247-4.
• [2] Gao W, Wang W, Chen Y. Tight bounds for the existence of path factors in network vulnerability parameter settings, International Journal of Intelligent Systems 2021. 36:1133-1158. doi:10.1002/int.22335.
• [3] Kaneko A. A necessary and sufficient 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 2003. 88(2):195-218. doi:10.1016/S0095-8956(03)00027-3.
• [4] Kano M, Katona GY, Kir´aly Z. Packing paths of length at least two, Discrete Mathematics 2004. 283(1-3):129-135. doi:10.1016/j.disc.2004.01.016.
• [5] Kano M , Lee C, Suzuki K. Path and cycle factors of cubic bipartite graphs, Discussiones Mathematicae Graph Theory 2008. 28(3):551-556. doi:10.7151/dmgt.1426.
• [6] Kano M , Lu H, Yu Q. Component factors with large components in graphs, Applied Mathematics Letters 2010. 23(4):385-389. doi:10.1016/j.aml.2009.11.003.
• [7] Katerinis P, Woodall D. Binding numbers of graphs and the existence of k-factors, The Quarterly Journal of Mathematics Oxford 1987. 38:221-228. doi:10.1093/qmath/38.2.221.
• [8] Liu H. Binding number for path-factor uniform graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 2022. 23(1):25-32.
• [9] Las Vergnas M. An extension of Tutte’s 1-factor theorem, Discrete Mathematics 1978. 23:241-255.
• [10] Wang S, Zhang W. Degree conditions for the existence of a {P2, P5}-factor in a graph, RAIRO-Operations Research 2023. 57(4):2231-2237. doi:10.1051/ro/2023111.
• [11] Wang S, Zhang W. Isolated toughness for path factors in networks, RAIRO-Operations Research 2022. 56(4):2613-2619. doi:10.1051/ro/2022123.
• [12] Wang S, Zhang W. Independence number, minimum degree and path-factors in graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 2022. 23(3):229-234.
• [13] Wang S, Zhang W. On k-orthogonal factorizations in networks, RAIRO-Operations Research 2021. 55(2):969-977.
• [14] Wang S, Zhang W. Some results on star-factor deleted graphs, Filomat 2024. 38(3):1101-1107. [15] Woodall D. The binding number of a graph and its Anderson number, Journal of Combinatorial Theory, Series B 1973. 15:225-255. doi:10.1016/0095-8956(73)90038-5.
• [16] Wu J. A sufficient condition for the existence of fractional (g, f, n)-critical covered graphs, Filomat 2024. 38(6):2177-2183.
• [17] Wu J. Path-factor critical covered graphs and path-factor uniform graphs, RAIRO-Operations Research 2022. 56(6):4317-4325. doi:10.1051/ro/2022208.
• [18] Zhou S. A neighborhood union condition for fractional (a, b, k)-critical covered graphs, Discrete Applied Mathematics 2022. 323:343-348. doi:10.1016/j.dam.2021.05.022.
• [19] Zhou S. Degree conditions and path factors with inclusion or exclusion properties, Bulletin Mathematique de la Societe des Sciences Mathematiques de Roumanie 2023. 66(1):3-14.
• [20] Zhou S. Remarks on path factors in graphs, RAIRO-Operations Research 2020. 54(6):1827-1834. doi:10.1051/ro/2019111.
• [21] Zhou S. Some results on path-factor critical avoidable graphs, Discussiones Mathematicae Graph Theory 2023. 43(1):233-244. doi:10.7151/dmgt.2364.
• [22] Zhou S, Bian Q, Sun Z. Two sufficient conditions for component factors in graphs, Discussiones Mathematicae Graph Theory 2023. 43(3):761-766.
• [23] Zhou S, Liu H. Two sufficient conditions for odd [1, b]-factors in graphs, Linear Algebra and its Applications 2023. 661:149-162. doi:10.1016/j.laa.2022.12.018.
• [24] Zhou S, Pan Q, Xu L. Isolated toughness for fractional (2, b, k)-critical covered graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 2023. 24(1):11-18.
• [25] Zhou S, Sun Z, Bian Q. Isolated toughness and path-factor uniform graphs (II), Indian Journal of Pure and Applied Mathematics 2023. 54(3):689-696.
• [26] Zhou S, Sun Z, Liu H. D-index and Q-index for spanning trees with leaf degree at most k in graphs, Discrete Mathematics 2024. 347(5):113927. doi:10.1016/j.disc.2024.113927.
• [27] Zhou S, Sun Z, Liu H. Some sufficient conditions for path-factor uniform graphs, Aequationes Mathematicae 2023. 97(3):489-500.
• [28] Zhou S, Sun Z, Yang F. A result on P≥3-factor uniform graphs, Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 2022. 23(1):3-8.
• [29] Zhou S, Wu J, Bian Q. On path-factor critical deleted (or covered) graphs, Aequationes Mathematicae 2022. 96(4):795-802. doi:10.1007/s00010-021-00852-4.
• [30] Zhou S, Wu J, Liu H. Independence number and connectivity for fractional (a, b, k)-critical covered graphs, RAIRO-Operations Research 2022. 56(4):2535-2542. doi:10.1051/ro/2022119.
• [31] Zhou S, Zhang Y, Sun Z. The Aα-spectral radius for path-factors in graphs, Discrete Mathematics 2024. 347:113940. doi:10.1016/j.disc.2024.113940.

Identyfikatory

DOI

10.3233/FI-242172