The Distance Matching Extension in K1,k-free Graphs with High Local Connectedness
Tóm tắt
A matching is extendable in a graph G if G has a perfect matching containing it. A distance q matching is a matching such that the distance between any two distinct matching edges is at least q. In this paper, we prove that any distance 2k − 3 matching is extendable in a connected and locally (k − 1)-connected K1,k-free graph of even order. Furthermore, we also prove that any distance q matching M in an r-connected and locally (k − 1)-connected K1,k-free graph of even order is extendable provided that ∣M∣ is bounded by a function on r, k and q. Our results improve some results in [J. Graph Theory 93 (2020), 5–20].
Tài liệu tham khảo
Aldred, R.E.L., Fujisawa, J., Saito, A. Distance matching extension and local structure of graphs. J. Graph Theory, 93: 5–20 (2020)
Aldred, R.E.L., Plummer, M.D. Matching extension in prism graphs. Discrete Appl. Math., 22: 125–32 (2017)
Aldred, R.E.L., Plummer, M.D. Proximity thresholds for matching extension in planar and projective planar triangulations. J. Graph Theory, 67: 38–46 (2011)
Chen, C. Matchings and matching extensions in graphs. Discrete Math., 186(1–3): 95–103 (1998)
Costa, M.-C., de Werra, D., Picouleau, C. Minimal graphs for matching extensions. Discrete Appl. Math., 234: 47–55 (2018)
Diestel, R. Graph Theory, the Fifth Edition. Springer, GTM 173, 2017
Fujisawa, J., Segawa, K., Suzuki, Y. The matching extendability of optimal 1-planar graphs. Graphs Combin., 34: 1089–1099 (2018)
Fujisawa, J., Seno, H. Edge proximity and matching extension in projective planar graphs. J. Graph Theory, 95(3): 341–367 (2020)
Hackfeld, J., Koster, A.M.C.A. The matching extension problem in general graphs is co-NP-complete. J. Comb. Optim., 35(3): 853–859 (2018)
Metsidik, M., Vumar, E. Toughness and matching extension in P3-dominated graphs. Graphs Combin., 26(3): 425–432 (2010)
Oberly, D.J., Sumner, D.P. Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian. J. Graph Theory, 3: 351–356 (1979)
Plummer, M.D. Extending matchings in planar graphs IV. Discrete Math., 109: 207–219 (1992)
Plummer, M.D. Matching extension and the genus of a graph. J. Combin. Theory Ser. B, 44(3): 329–337 (1988)
Plummer, M.D. Toughness and matching extension in graphs. Discrete Math., 72(1–3): 311–320 (1988)
Ryjáček, Z. Matching extension in K1,r-free graphs with independent claw centers. Discrete Math., 164(1–3): 257–263 (1997)
Walcher, K.L. Matching extension in the powers of n-connected graphs. J. Graph Theory, 23(4): 355–360 (1996)
Yang, F., Yuan, J.J. IM-extendable claw-free graphs. J. Math. Study, 32(1): 33–37 (1999)