Abstract
A spanning subgraph F of a graph G is called a path factor of G if each component of F is a path. A P≥k-factor means a path factor with each component having at least k vertices, where k ≥ 2 is an integer. Bazgan, Benhamdine, Li and Wozniak [C. Bazgan, A. H. Benhamdine, H. Li, M. Wozniak, Partitioning vertices of 1-tough graph into paths, Theoret. Comput. Sci. 263(2001)255-261.] obtained a toughness condition for a graph to have a P≥3-factor. We introduce the concept of a P≥k-factor deleted graph, that is, if a graph G has a P≥k-factor excluding e for every e ∈ E(G), then we say that G is a P≥k-factor deleted graph. In this paper, we show four sufficient conditions for a graph to be a P≥3-factor deleted graph. Furthermore, it is shown that four results are best possible in some sense.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bazgan, C., Benhamdine, A.H., Li, H., Wozniak, M. Partitioning vertices of 1-tough graph into paths. Theoretical Computer Science, 263: 255–261 (2001)
Bondy, J.A., Murty, U.S.R. Graph Theory. Springer, Berlin, 2008
Chiba, S., Yamashita, T. A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs. Discrete Mathematics, 340: 2871–2877 (2017)
Chvátal, V. Tough graphs and Hamiltonian Circuits. Discrete Mathematics, 5: 215–228 (1973)
Eomoto, H. Toughness and the existence of k-factors III. Discrete Mathematics, 189: 277–282 (1998)
Gao, W., Liang, L., Xu, T., Zhou, J. Tight toughness condition for fractional (g, f, n)-critical graphs. Journal of the Korean Mathematical Society, 51: 55–65 (2014)
Gao, W., Wang, W. Toughness and fractional critical deleted graph. Utilitas Mathematica, 98: 295–310 (2015)
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 Theorey, 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)
Ma, Y., Liu, G. Isolated toughness and the existence of fractioanl factors. Acta Mathematicae Applicatae Sinica, Chinese Series, 26: 133–140 (2003)
Plummer, M. Graph factors and factorizations: 1985–2003: A survey. Discrete Mathematics, 307: 791–821 (2007)
Sun, Z., Zhou, S. Isolated toughness and k-Hamiltonian [a, b]-factors. Acta Mathematicae Applicatae Sinica-English Series, 36: 539–544 (2020)
Wang, C. Graph Theory. Beijing Institute of Technology Press, Beijing, 1997
Wang, S., Zhang, W. On k-orthogonal factorizations in networks. RAIRO-Operations Research, 55: 969–977 (2021)
Wang, S., Zhang, W. Research on fractional critical covered graphs. Problems of Information Transmission, 56: 270–277 (2020)
Xiong, L. Characterization of forbidden subgraphs for the existence of even factors in a graph. Discrete Applied Mathematics, 223: 135–139 (2017)
Yang, J., Ma, Y., Liu, G. Fractional (g, f)-factors in graphs. Applied Mathematics—A Journal of Chinese Universities, Series A, 16: 385–390 (2001)
Zhou, S. A neighborhood union condition for fractional (a, b, k)-critical covered graphs. Discrete Applied Mathematics, DOI: https://doi.org/10.1016/j.dam.2021.05.022
Zhou, S. A result on fractional (a, b, k)-critical covered graphs. Acta Mathematicae Applicatae Sinica-English Series, 37: 657–664 (2021)
Zhou, S. Binding numbers and restricted fractional (g, f)-factors in graphs. Discrete Applied Mathematics, DOI: https://doi.org/10.1016/j.dam.2020.10.017
Zhou, S. Remarks on path factors in graphs. RAIRO-Operations Research, 54: 1827–1834 (2020)
Zhou, S., Bian, Q., Pan, Q. Path factors in subgraphs. Discrete Applied Mathematics, DOI: https://doi.org/10.1016/j.dam.2021.04.012
Zhou, S., Bian, Q., Sun, Z. Two sufficient conditions for component factors in graphs. Discussiones Mathematicae Graph Theory, DOI: https://doi.org/10.7151/dmgt.2401
Zhou, S., Liu, H., Xu, Y. A note on fractional ID-[a, b]-factor-critical covered graphs. Discrete Applied Mathematics, DOI: https://doi.org/10.1016/j.dam.2021.03.004
Zhou, S., Sun, Z., Pan, Q. A sufficient condition for the existence of restricted fractional (g, f)-factors in graphs. Problems of Information Transmission, 56: 332–344 (2020)
Zhou, S., Xu, J., Xu, L. Component factors and binding number conditions in graphs. AIMS Mathematics, 6: 12460–12470 (2021)
Zhou, S., Zhang, T., Xu, Z. Subgraphs with orthogonal factorizations in graphs. Discrete Applied Mathematics, 286: 29–34 (2020)
Acknowledgments
The authors are very grateful to the anonymous referees for their valuable comments and suggestions, which have greatly improved the final version of this article.
Funding
This work is supported by Six Talent Peaks Project in Jiangsu Province, China (Grant No. JY-022)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhou, Sz., Sun, Zr. & Liu, Hx. On P≥3-factor Deleted Graphs. Acta Math. Appl. Sin. Engl. Ser. 38, 178–186 (2022). https://doi.org/10.1007/s10255-022-1053-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-022-1053-0