Abstract
A path factor of G is a spanning subgraph of G such that its each component is a path. A path factor is called a P≥n-factor if its each component admits at least n vertices. A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e ∈ E(G), which is defined by [Discrete Mathematics, 309, 2067–2076 (2009)]. We first define the concept of a (P≥n, k)-factor-critical covered graph, namely, a graph G is called (P≥n, k)-factor-critical covered if G-D is P≥n-factor covered for any D ⊆ V(G)with ∣D∣ = k. In this paper, we verify that (i) a graph G with k(G) ≥ k + 1 is (P⊆2, k)-factor-critical covered if bind \(\left( G \right) > {{2 + k} \over 3}\); (ii) a graph G with ∣V(G)∣ ≥ k + 3 and k(G) ≥ k + 1 is (P≥3, k)-factor-critical covered if bind\(\left( G \right) \ge {{4 + k} \over 3}\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akiyama, J., Avis, D., Era, H.: On a {1, 2}-factor of a graph. TRU Math., 16, 97–102 (1980)
Asratian, A., Casselgren, C.: On path factors of (3,4)-biregular bigraphs. Graphs and Combinatorics, 24, 405–411 (2008)
Gao, W., Dimitrov, D., Abdo, H.: Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete and Continuous Dynamical Systems-Series S, 12(4–5), 711–721 (2019)
Gao, W., Guirao, J.: Parameters and fractional factors in different settings. Journal of Inequalities and Applications, 152, (2019), https://doi.org/10.1186/s13660-019-2106-7
Gao, W., Guirao, J., Chen, Y.: A toughness condition for fractional (k, m)-deleted graphs revisited. Acta Mathematica Sinica, English Series, 35(7), 1227–1237 (2019)
Johnson, M., Paulusma, D., Wood, C.: Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics, 310, 1413–1423 (2010)
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, 88, 195–218 (2003)
Kano, M., Katona, G. Y., Király, Z.: Packing paths of length at least two. Discrete Mathematics, 283, 129–135 (2004)
Kano, M., Lee, C., Suzuki, K.: Path and cycle factors of cubic bipartite graphs. Discussiones Mathematicae Graph Theory, 28, 551–556 (2008)
Kano, M., Lu, H., Yu, Q.: Component factors with large components in graphs. Applied Mathematics Letters, 23, 385–389 (2010)
Kawarabayashi, K., Matsuda, H., Oda, Y., et al.: Path factors in cubic graphs. Journal of Graph Theory, 39, 188–193 (2002)
Katerinis, P., Woodall, D.: Binding numbers of graphs and the existence of k-factors. The Quarterly Journal of Mathematics Oxford, 38, 221–228 (1987)
Kelmans A., Packing 3-vertex paths in claw-free graphs and related topics. Discrete Applied Mathematics, 159, 112–127 (2011)
Matsubara, R., Matsumura, H., Tsugaki, M., et al.: Degree sum conditions for path-factors with specified end vertices in bipartite graphs. Discrete Mathematics, 340, 87–95 (2017)
Plummer, M., Saito, A.: Toughness, binding number and restricted matching extension in a graph. Discrete Mathematics, 340, 2665–2672 (2017)
Woodall, D.: The binding number of a graph and its Anderson number. Journal of Combinatorial Theory, Series B, 15, 225–255 (1973)
Zhang, H., Zhou, S.: Characterizations for P≥2-factor and P≥3-factor covered graphs. Discrete Mathematics, 309, 2067–2076 (2009)
Zhou, S.: A sufficient condition for graphs to be fractional (k, m)-deleted graphs. Applied Mathematics Letters, 24(9), 1533–1538 (2011)
Zhou, S.: Binding numbers for fractional ID-k-factor-critical graphs. Acta Mathematica Sinica, English Series, 30(1), 181–186 (2014)
Zhou, S.: Remarks on orthogonal factorizations of digraphs. International Journal of Computer Mathematics, 91(10), 2109–2117 (2014)
Zhou, S.: Remarks on path factors in graphs. RAIRO-Operations Research, DOI:https://doi.org/10.1051/ro/2019111
Zhou, S.: Some new sufficient conditions for graphs to have fractional k-factors. International Journal of Computer Mathematics, 88(3), 484–490 (2011)
Zhou, S.: Some results about component factors in graphs. RAIRO-Operations Research, 53(3), 723–730 (2019)
Zhou, S., Sun, Z., Ye, H.: A toughness condition for fractional (k, m)-deleted graphs. Information Processing Letters, 113(8), 255–259 (2013)
Zhou, S., Wu, J., Zhang, T.: The existence of P≥3-factor covered graphs. Discussiones Mathematicae Graph Theory, 37(4), 1055–1065 (2017)
Zhou, S., Xu, Y., Sun, Z.: Degree conditions for fractional (a, b, k)-critical covered graphs. Information Processing Letters, 152, Article 105838 (2019), DOI: https://doi.org/10.1016/j.ipl.2019.105838
Zhou, S., Yang, F., Xu, L.: Two sufficient conditions for the existence of path factors in graphs. Scientia Iranica, DOI: https://doi.org/10.24200/SCI.2018.5151.1122
Acknowledgements
The authors would like to thank the anonymous referees for their valuable comments and suggestions.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Supported by Six Big Talent Peak of Jiangsu Province (Grant No. JY-022), 333 Project of Jiangsu Province, and the National Natural Science Foundation of China (Grant No. 11371009)
Rights and permissions
About this article
Cite this article
Zhou, S.Z., Sun, Z.R. Some Existence Theorems on Path Factors with Given Properties in Graphs. Acta. Math. Sin.-English Ser. 36, 917–928 (2020). https://doi.org/10.1007/s10114-020-9224-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-020-9224-5
Keywords
- Graph
- binding number
- P≥2-factor
- P≥3-factor
- (P≥2, k)-factor-critical covered graph
- (P≥3, k)-factor-critical covered graph