no. 5
On 2 -matching covered graphs and 2 -matching deleted graphs
RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3667-3674

For a family of connected graphs 𝒜, a spanning subgraph H of a graph G is called an 𝒜-factor of G if each component of H is isomorphic to some graph in 𝒜. A graph G has a perfect 2-matching if G has a spanning subgraph H such that each component of H is either an edge or a cycle, i.e., H is a {P2, C$$|i ≥ 3}-factor of G. A graph G is said to be 2-matching covered if, for every edge e ∈ E(G), there is a perfect 2-matching M$$ of G such that e belongs to M$$. A graph G is called a 2-matching deleted graph if, for every edge e ∈ E(G), G − e possesses a perfect 2-matching. In this paper, we first obtain respective new characterizations for 2-matching covered graphs in bipartite and non-bipartite graphs by new proof technologies, distinct from Hetyei’s or Berge’s classical results. Secondly, we give a necessary and sufficient condition for a graph to be a 2-matching deleted graph. Thirdly, we we prove that planar graphs with minimum degree at least 4 and K$$-free graphs (r ≥ 3) with minimum degree at least r + 1 are 2-matching deleted graphs, respectively.

DOI : 10.1051/ro/2022172
Classification : 05C70, 05C38
Keywords: Graph theory, perfect 2-matching, {$$2, $$i|$$ ≥ 3}-factor, 2-matching covered graphs, 2-matching deleted graphs 
@article{RO_2022__56_5_3667_0,
     author = {Dai, Guowei},
     title = {On $2$-matching covered graphs and $2$-matching deleted graphs},
     journal = {RAIRO. Operations Research},
     pages = {3667--3674},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {5},
     doi = {10.1051/ro/2022172},
     mrnumber = {4502920},
     zbl = {1502.05200},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022172/}
}
TY  - JOUR
AU  - Dai, Guowei
TI  - On $2$-matching covered graphs and $2$-matching deleted graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 3667
EP  - 3674
VL  - 56
IS  - 5
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022172/
DO  - 10.1051/ro/2022172
LA  - en
ID  - RO_2022__56_5_3667_0
ER  - 
%0 Journal Article
%A Dai, Guowei
%T On $2$-matching covered graphs and $2$-matching deleted graphs
%J RAIRO. Operations Research
%D 2022
%P 3667-3674
%V 56
%N 5
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022172/
%R 10.1051/ro/2022172
%G en
%F RO_2022__56_5_3667_0
Dai, Guowei. On $2$-matching covered graphs and $2$-matching deleted graphs. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3667-3674. doi: 10.1051/ro/2022172

[1] J. Akiyama and M. Kano, Factors and factorizations of graphs, in Lecture Notes in Mathematics. Springer, Berlin, 2031 (2011) 1–347. | MR | Zbl

[2] A. Amahashi and M. Kano, Factors with given components. Discrete Math. 42 (1982) 1–6. | MR | Zbl | DOI

[3] K. Ando, Y. Egawa, A. Kaneko, K. I. Kawarabayashi and H. Matsuda, Path factors in claw-free graphs. Discrete Math. 243 (2002) 195–200. | MR | Zbl | DOI

[4] C. Berge, Regularizable graphs I. Discrete Math. 23 (1978) 85–89. | MR | Zbl | DOI

[5] J. A. Bondy and U. S. R. Murty, Graph theory with applications. Macmillan, London (1976). | MR | Zbl | DOI

[6] V. Chvátal, Tough graphs and Hamiltonian Circuits. Discrete Math. 5 (1973) 215–228. | MR | Zbl | DOI

[7] G. Dai, Remarks on component factors in graphs. RAIRO:RO 56 (2022) 721–730. | MR | Zbl | Numdam | DOI

[8] G. Dai, The existence of path-factor covered graphs. Discuss. Math. Graph Theory 43 (2023) 5–16. | MR | Zbl | DOI

[9] G. Dai and Z. Hu, P 3 -factors in the square of a tree. Graphs Combin. 36 (2020) 1913–1925. | MR | Zbl | DOI

[10] G. Dai, Z. Zhang, Y. Hang and X. Zhang, Some degree conditions for P ≥ 3 -factor covered graphs. RAIRO:RO 55 (2021) 2907–2913. | MR | Zbl | Numdam | DOI

[11] G. Dai, Y. Hang, X. Zhang, Z. Zhang and W. Wang, Sufficient conditions for graphs with { P 2 , P 5 } -factor. RAIRO:RO 56 (2022) 2895–2901. | MR | Zbl | Numdam | DOI

[12] 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. | MR | Zbl | DOI

[13] A. Kaneko, A. Kelmans and T. Nishimura, On packing 3 -vertex paths in a graph. J. Graph Theory 36 (2001) 175–197. | MR | Zbl | DOI

[14] M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs. Discuss. Math. Graph Theory 28 (2008) 551–556. | MR | Zbl | DOI

[15] K. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs. J. Graph Theory 39 (2002) 188–193. | MR | Zbl | DOI

[16] M. D. Plummer, Perspectives: Graph factors and factorization: 1985–2003: A survey. Discrete Math. 307 (2007) 791–821. | MR | Zbl | DOI

[17] W. T. Tutte, The factors of graphs. Canad. J. Math. 4 (1952) 314–328. | MR | Zbl | DOI

[18] H. Wang, Path factors of bipartite graphs. J. Graph Theory 18 (1994) 161–167. | MR | Zbl | DOI

[19] D. R. Woodall, The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15 (1973) 225–255. | MR | Zbl | DOI

[20] J. Yang, Y. Ma and G. Liu, Fractional ( g , f ) -factors in graphs. Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390. | MR | Zbl

[21] Q. R. Yu and G. Z. Liu, Graph Factors and Matching Extensions. Higher Education Press, Beijing (2009). | MR | Zbl

Cité par Sources :