×

Some existence theorems on path factors with given properties in graphs. (English) Zbl 1447.05177

Summary: A path factor of \(G\) is a spanning subgraph of \(G\) such that each of its component is a path. A path factor is called a \(P_{\geq n}\)-factor if each of its component admits at least \(n\) vertices. A graph \(G\) is called \(P_{\geq n}\)-factor covered if \(G\) admits a \(P_{\geq n}\)-factor containing \(e\) for any \(e \in E(G)\), which is defined in [H. Zhang and S. Zhou, Discrete Math. 309, No. 8, 2067–2076 (2009; Zbl 1205.05187)]. We first define the concept of a \((P_{\geq n}, k)\)-factor-critical covered graph, namely, a graph \(G\) is called \((P_{\geq n}, k)\)-factor-critical covered if \(G-D\) is \(P_{\geq n}\)-factor covered for any \(D \subseteq V(G)\) with \(|D| = k\). In this paper, we verify that (i) a graph \(G\) with \(k(G) \geq k + 1\) is \((P_{\geq 2}, k)\)-factor-critical covered if \(\text{bind}(G) > \frac{2 + k}{3} \); (ii) a graph \(G\) with \(|V(G)| \geq k + 3\) and \(k(G) \geq k + 1\) is \((P_{\geq 3}, k)\)-factor-critical covered if \(\text{bind}(G) \ge \frac{4 + k}{3}\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
90B10 Deterministic network models in operations research

Citations:

Zbl 1205.05187
PDFBibTeX XMLCite
Full Text: DOI

References:

[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] Asratian, A.; Casselgren, C., On path factors of (3,4)-biregular bigraphs, Graphs and Combinatorics, 24, 405-411 (2008) · Zbl 1177.05089 · doi:10.1007/s00373-008-0803-y
[3] 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) · Zbl 1419.05167 · doi:10.3934/dcdss.2019045
[4] Gao, W., Guirao, J.: Parameters and fractional factors in different settings. Journal of Inequalities and Applications, 152, (2019), 10.1186/s13660-019-2106-7 · Zbl 1499.05515
[5] 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) · Zbl 1415.05149 · doi:10.1007/s10114-019-8169-z
[6] Johnson, M.; Paulusma, D.; Wood, C., Path factors and parallel knock-out schemes of almost claw-free graphs, Discrete Mathematics, 310, 1413-1423 (2010) · Zbl 1219.05140 · doi:10.1016/j.disc.2009.04.022
[7] 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) · Zbl 1029.05125 · doi:10.1016/S0095-8956(03)00027-3
[8] Kano, M.; Katona, G. Y.; Király, Z., Packing paths of length at least two, Discrete Mathematics, 283, 129-135 (2004) · Zbl 1042.05084 · doi:10.1016/j.disc.2004.01.016
[9] Kano, M.; Lee, C.; Suzuki, K., Path and cycle factors of cubic bipartite graphs, Discussiones Mathematicae Graph Theory, 28, 551-556 (2008) · Zbl 1173.05028 · doi:10.7151/dmgt.1426
[10] Kano, M.; Lu, H.; Yu, Q., Component factors with large components in graphs, Applied Mathematics Letters, 23, 385-389 (2010) · Zbl 1213.05158 · doi:10.1016/j.aml.2009.11.003
[11] Kawarabayashi, K.; Matsuda, H.; Oda, Y., Path factors in cubic graphs, Journal of Graph Theory, 39, 188-193 (2002) · Zbl 1176.05064 · doi:10.1002/jgt.10022
[12] Katerinis, P.; Woodall, D., Binding numbers of graphs and the existence of k-factors, The Quarterly Journal of Mathematics Oxford, 38, 221-228 (1987) · Zbl 0639.05050 · doi:10.1093/qmath/38.2.221
[13] Kelmans, A., Packing 3-vertex paths in claw-free graphs and related topics, Discrete Applied Mathematics, 159, 112-127 (2011) · Zbl 1206.05058 · doi:10.1016/j.dam.2010.05.001
[14] Matsubara, R.; Matsumura, H.; Tsugaki, M., Degree sum conditions for path-factors with specified end vertices in bipartite graphs, Discrete Mathematics, 340, 87-95 (2017) · Zbl 1351.05129 · doi:10.1016/j.disc.2016.07.015
[15] Plummer, M.; Saito, A., Toughness, binding number and restricted matching extension in a graph, Discrete Mathematics, 340, 2665-2672 (2017) · Zbl 1369.05176 · doi:10.1016/j.disc.2016.10.003
[16] Woodall, D., The binding number of a graph and its Anderson number, Journal of Combinatorial Theory, Series B, 15, 225-255 (1973) · Zbl 0253.05139 · doi:10.1016/0095-8956(73)90038-5
[17] Zhang, H.; Zhou, S., Characterizations for P≥_2-factor and P≥_3-factor covered graphs, Discrete Mathematics, 309, 2067-2076 (2009) · Zbl 1205.05187 · doi:10.1016/j.disc.2008.04.022
[18] Zhou, S., A sufficient condition for graphs to be fractional (k, m)-deleted graphs, Applied Mathematics Letters, 24, 9, 1533-1538 (2011) · Zbl 1218.05159 · doi:10.1016/j.aml.2011.03.041
[19] Zhou, S., Binding numbers for fractional ID-k-factor-critical graphs, Acta Mathematica Sinica, English Series, 30, 1, 181-186 (2014) · Zbl 1287.05124 · doi:10.1007/s10114-013-1396-9
[20] Zhou, S., Remarks on orthogonal factorizations of digraphs, International Journal of Computer Mathematics, 91, 10, 2109-2117 (2014) · Zbl 1303.05159 · doi:10.1080/00207160.2014.881993
[21] Zhou, S.: Remarks on path factors in graphs. RAIRO-Operations Research, DOI:10.1051/ro/2019111 · Zbl 1462.05307
[22] Zhou, S., Some new sufficient conditions for graphs to have fractional k-factors, International Journal of Computer Mathematics, 88, 3, 484-490 (2011) · Zbl 1230.05243 · doi:10.1080/00207161003681286
[23] Zhou, S., Some results about component factors in graphs, RAIRO-Operations Research, 53, 3, 723-730 (2019) · Zbl 1426.05142 · doi:10.1051/ro/2017045
[24] Zhou, S.; Sun, Z.; Ye, H., A toughness condition for fractional (k, m)-deleted graphs, Information Processing Letters, 113, 8, 255-259 (2013) · Zbl 1273.05128 · doi:10.1016/j.ipl.2013.01.021
[25] Zhou, S.; Wu, J.; Zhang, T., The existence of P≥_3-factor covered graphs, Discussiones Mathematicae Graph Theory, 37, 4, 1055-1065 (2017) · Zbl 1372.05178 · doi:10.7151/dmgt.1974
[26] Zhou, S., Xu, Y., Sun, Z.: Degree conditions for fractional (a, b, k)-critical covered graphs. Information Processing Letters, 152, Article 105838 (2019), DOI: 10.1016/j.ipl.2019.105838 · Zbl 1481.05132
[27] Zhou, S., Yang, F., Xu, L.: Two sufficient conditions for the existence of path factors in graphs. Scientia Iranica, DOI: 10.24200/SCI.2018.5151.1122
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.