Abstract
Given a graph G and an integer \(k\ge 2\). A spanning subgraph F of a graph G is said to be a \(P_{\ge k}\)-factor of G if each component of F is a path of order at least k. A graph G is called a \(P_{\ge k}\)-factor uniform graph if for any two distinct edges \(e_{1}\) and \(e_{2}\) of G, G admits a \(P_{\ge k}\)-factor including \(e_{1}\) and excluding \(e_{2}\). More recently, Zhou and Sun (Discret Math 343:111715, 2020) gave binding number conditions for a graph to be \(P_{\ge 2}\)-factor and \(P_{\ge 3}\)-factor uniform graphs, respectively. In this paper, we present toughness and isolated toughness conditions for a graph to be a \(P_{\ge 3}\)-factor uniform graph, respectively.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akiyama, J., Avis, D., Era, H.: On a \(\{1, 2\}\)-factor of a graph. TRU Math. 16, 97–102 (1980)
Akiyama, J., Kano, M.: Path factors of a graph. In: F. Harary JS, Maybee (Eds.) Graphs and Applications, Proc. 1st Colorado Symposium on Graph Theory, Wiley, New York, 1982, pp. 1-21. (1985)
Bazgan, C., Benhamdine, A.H., Li, H., Woźniak, M.: Partitioning vertices of 1- tough graph into paths. Theoret. Comput. Sci. 263, 255–261 (2001)
Chvátal, V.: Tough graphs and Hamiltonian circuits. Discret. Math. 5, 215–228 (1973)
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. J. Combin. Theory Ser. B 88, 195–218 (2003)
Kano, M., Katona, G.Y., Király, Z.: Packing paths of length at least two. Discret. Math. 283, 129–135 (2004)
Yang, J., Ma, Y., Liu, G.: Fractional \((g, f)\)-factors in graphs. Appl. Math. J. Chin. Univ. Ser. A 16, 385–390 (2001)
Zhang, H., Zhou, S.: Characterizations for \(P_{\ge 2}\)-factor and \(P_{\ge 2}\)-factor covered graphs. Discret. Math. 309, 2067–2076 (2009)
Zhou, S., Wu, J., Zhang, T.: The existence of \(P_{\ge 3}\)-factor covered graphs. Discuss. Math. Graph Theory 37, 1055–1065 (2017)
Zhou, S., Sun, Z.: Binding number conditions for \(P_{\ge 2}\)-factor and \(P_{\ge 3}\)-factor uniform graphs. Discret. Math. 343, 111715 (2020)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was supported by National Natural Science Foundation of China under Grant Nos. 11971011, 11571135 and sponsored by Qing Lan Project of Jiangsu Province, P.R. China.
Rights and permissions
About this article
Cite this article
Hua, H. Toughness and isolated toughness conditions for \(P_{\ge 3}\)-factor uniform graphs. J. Appl. Math. Comput. 66, 809–821 (2021). https://doi.org/10.1007/s12190-020-01462-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12190-020-01462-0