1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Existence of Path-Factor Covered Graphs

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Dec 2019
Accepted: 06 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A spanning subgraph H of a graph G is called a Pk-factor of G if every component of H is isomorphic to a path of order at least k, where k ≥ 2. A graph G is called a Pk-factor covered graph if there is a Pk-factor of G covering e for any eE(G). In this paper, we obtain two special classes of P≥2-factor covered graphs. We also obtain two special classes of P≥3-factor covered graphs. Furthermore, it is shown that these results are all sharp.

Keywords

MSC 2010

[1] J. Akiyama, D. Avis and H. Era, On a {1, 2}-factor of a graph, TRU Math. 16 (1980) 97–102.Search in Google Scholar

[2] J. Akiyama and M. Kano, Factors and factorizations of graphs—a survey, J. Graph Theory 9 (1985) 1–42. doi:10.1002/jgt.319009010310.1002/jgt.3190090103Search in Google Scholar

[3] A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6. doi:10.1016/0012-365X(82)90048-610.1016/0012-365X(82)90048-6Search in Google Scholar

[4] K. Ando, Y. Egawa, A. Kaneko, K.I. Kawarabayashi and H. Matsuda, Path factors in claw-free graphs, Discrete Math. 243 (2002) 195–200. doi:10.1016/S0012-365X(01)00214-X10.1016/S0012-365X(01)00214-XSearch in Google Scholar

[5] C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Woźniak, Partitioning vertices of 1-tough graphs into paths, Theoret. Comput. Sci. 263 (2001) 255–261. doi:10.1016/S0304-3975(00)00247-410.1016/S0304-3975(00)00247-4Search in Google Scholar

[6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, NewYork-Amsterdam-Oxford, 1982).Search in Google Scholar

[7] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. doi:10.1016/0012-365X(73)90138-610.1016/0012-365X(73)90138-6Search in Google Scholar

[8] Y. Egawa, M. Furuya and K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components, J. Graph Theory 89 (2018) 327–340. doi:10.1002/jgt.2225310.1002/jgt.22253Search in Google Scholar

[9] A. Kaneko, A. Kelmans and T. Nishimura, On packing 3-vertex paths in a graph, J. Graph Theory 36 (2001) 175–197. doi:10.1002/1097-0118(200104)36:4〈175::AID-JGT1005〉3.0.CO;2-TSearch in Google Scholar

[10] A. Kaneko, 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 (2003) 195–218. doi:10.1016/S0095-8956(03)00027-310.1016/S0095-8956(03)00027-3Search in Google Scholar

[11] M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two, Discrete Math. 283 (2004) 129–135. doi:10.1016/j.disc.2004.01.01610.1016/j.disc.2004.01.016Search in Google Scholar

[12] M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs, Discuss. Math. Graph Theory 28 (2008) 551–556. doi:10.7151/dmgt.142610.7151/dmgt.1426Search in Google Scholar

[13] K-i. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs, J. Graph Theory 39 (2002) 188–193. doi:10.1002/jgt.1002210.1002/jgt.10022Search in Google Scholar

[14] M.D. Plummer, Graph factors and factorization: 19852003 : A survey, Discrete Math. 307 (2007) 791–821. doi:10.1016/j.disc.2005.11.05910.1016/j.disc.2005.11.059Search in Google Scholar

[15] W.T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952) 314–328. doi:10.4153/CJM-1952-028-210.4153/CJM-1952-028-2Search in Google Scholar

[16] H. Wang, Path factors of bipartite graphs, J. Graph Theory 18 (1994) 161–167. doi:10.1002/jgt.319018020710.1002/jgt.3190180207Search in Google Scholar

[17] J. Yang, Y. Ma and G. Liu, Fractional (g, f)-factors in graphs, Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390.Search in Google Scholar

[18] Q.R. Yu and G.Z. Liu, Graph Factors and Matching Extensions (Springer, Berlin, Heidelberg Press, Beijing, 2009). doi:10.1007/978-3-540-93052-8Search in Google Scholar

[19] H. Zhang and S. Zhou, Characterizations for P2-factor and P3-factor covered graphs, Discrete Math. 309 (2009) 2067–2076. doi:10.1016/j.disc.2008.04.02210.1016/j.disc.2008.04.022Search in Google Scholar

[20] S.Z. Zhou and J.C. Wu, The existence of P3-factor covered graphs, Discuss. Math. Graph Theory 37 (2017) 1055–1065. doi:10.7151/dmgt.197410.7151/dmgt.1974Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo