Toughness and isolated toughness conditions for \(P_{\ge 3}\)-factor uniform graphs. (English) Zbl 1475.05097
Summary: Given a graph \(G\) and an integer \(k\geq 2\). A spanning subgraph \(F\) of a graph \(G\) is said to be a \(P_{\geq k}\)-factor of \(G\) if each component of \(F\) is a path of order at least \(k\). A graph \(G\) is called a \(P_{\geq k}\)-factor uniform graph if for any two distinct edges \(e_1\) and \(e_2\) of \(G, G\) admits a \(P_{\geq k}\)-factor including \(e_1\) and excluding \(e_2\). More recently, S. Zhou and Z. Sun [Discrete Math. 343, No. 3, Article ID 111715, 6 p. (2020; Zbl 1435.05166)] gave binding number conditions for a graph to be \(P_{\geq 2}\)-factor and \(P_{\geq 3}\)-factor uniform graphs, respectively. In this paper, we present toughness and isolated toughness conditions for a graph to be a \(P_{\geq 3}\)-factor uniform graph, respectively.
Citations:
Zbl 1435.05166References:
| [1] | Akiyama, J.; Avis, D.; Era, H., On a \(\{1, 2\}\)-factor of a graph, TRU Math., 16, 97-102 (1980) · Zbl 0461.05047 |
| [2] | 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) · Zbl 0561.05044 |
| [3] | Bazgan, C.; Benhamdine, AH; Li, H.; Woźniak, M., Partitioning vertices of 1- tough graph into paths, Theoret. Comput. Sci., 263, 255-261 (2001) · Zbl 0973.68188 · doi:10.1016/S0304-3975(00)00247-4 |
| [4] | Chvátal, V., Tough graphs and Hamiltonian circuits, Discret. Math., 5, 215-228 (1973) · Zbl 0256.05122 · doi:10.1016/0012-365X(73)90138-6 |
| [5] | 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) · Zbl 1029.05125 · doi:10.1016/S0095-8956(03)00027-3 |
| [6] | Kano, M.; Katona, GY; Király, Z., Packing paths of length at least two, Discret. Math., 283, 129-135 (2004) · Zbl 1042.05084 · doi:10.1016/j.disc.2004.01.016 |
| [7] | Yang, J.; Ma, Y.; Liu, G., Fractional \((g, f)\)-factors in graphs, Appl. Math. J. Chin. Univ. Ser. A, 16, 385-390 (2001) · Zbl 0991.05087 |
| [8] | Zhang, H.; Zhou, S., Characterizations for \(P_{\ge 2}\)-factor and \(P_{\ge 2}\)-factor covered graphs, Discret. Math., 309, 2067-2076 (2009) · Zbl 1205.05187 · doi:10.1016/j.disc.2008.04.022 |
| [9] | Zhou, S.; Wu, J.; Zhang, T., The existence of \(P_{\ge 3}\)-factor covered graphs, Discuss. Math. Graph Theory, 37, 1055-1065 (2017) · Zbl 1372.05178 · doi:10.7151/dmgt.1974 |
| [10] | Zhou, S.; Sun, Z., Binding number conditions for \(P_{\ge 2}\)-factor and \(P_{\ge 3}\)-factor uniform graphs, Discret. Math., 343, 111715 (2020) · Zbl 1435.05166 · doi:10.1016/j.disc.2019.111715 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
