DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

G. Dai

Guowei Dai

Central China Normal University

email: daiguowei1990@163.com

0000-0001-5839-4573

Title:

The existence of path-factor covered graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(1) (2023) 5-16

Received: 2019-12-01 , Revised: 2020-07-02 , Accepted: 2020-07-06 , Available online: 2020-09-09 , https://doi.org/10.7151/dmgt.2353

Abstract:

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

Keywords:

path-factor, $P_{\geq2}$-factor covered graph, $P_{\geq3}$-factor covered graph, claw-free graph, isolated toughness

References:

  1. J. Akiyama, D. Avis and H. Era, On a $\{1,2\}$-factor of a graph, TRU Math. 16 (1980) 97–102.
  2. J. Akiyama and M. Kano, Factors and factorizations of graphs–-a survey, J. Graph Theory 9 (1985) 1–42.
    https://doi.org/10.1002/jgt.3190090103
  3. A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6.
    https://doi.org/10.1016/0012-365X(82)90048-6
  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.
    https://doi.org/10.1016/S0012-365X(01)00214-X
  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.
    https://doi.org/10.1016/S0304-3975(00)00247-4
  6. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, NewYork-Amsterdam-Oxford, 1982).
  7. V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
    https://doi.org/10.1016/0012-365X(73)90138-6
  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.
    https://doi.org/10.1002/jgt.22253
  9. A. Kaneko, A. Kelmans and T. Nishimura, On packing $3$-vertex paths in a graph, J. Graph Theory 36 (2001) 175–197.
    https://doi.org/10.1002/1097-0118(200104)36:4<175::AID-JGT1005>3.0.CO;2-T
  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.
    https://doi.org/10.1016/S0095-8956(03)00027-3
  11. M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two, Discrete Math. 283 (2004) 129–135.
    https://doi.org/10.1016/j.disc.2004.01.016
  12. M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs, Discuss. Math. Graph Theory 28 (2008) 551–556.
    https://doi.org/10.7151/dmgt.1426
  13. K-i. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs, J. Graph Theory 39 (2002) 188–193.
    https://doi.org/10.1002/jgt.10022
  14. M.D. Plummer, Graph factors and factorization$:1985$–$2003 :$ A survey, Discrete Math. 307 (2007) 791–821.
    https://doi.org/10.1016/j.disc.2005.11.059
  15. W.T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952) 314–328.
    https://doi.org/10.4153/CJM-1952-028-2
  16. H. Wang, Path factors of bipartite graphs, J. Graph Theory 18 (1994) 161–167.
    https://doi.org/10.1002/jgt.3190180207
  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.
  18. Q.R. Yu and G.Z. Liu, Graph Factors and Matching Extensions (Springer, Berlin, Heidelberg Press, Beijing, 2009).
    https://doi.org/10.1007/978-3-540-93052-8
  19. H. Zhang and S. Zhou, Characterizations for $P_{\geq2}$-factor and $P_{\geq3}$-factor covered graphs, Discrete Math. 309 (2009) 2067–2076.
    https://doi.org/10.1016/j.disc.2008.04.022
  20. S.Z. Zhou and J.C. Wu, The existence of $P_{\geq3}$-factor covered graphs, Discuss. Math. Graph Theory 37 (2017) 1055–1065.
    https://doi.org/10.7151/dmgt.1974

Close