Geodesic
A Degree Condition Implying Ore-Type Condition for Even [2, b]-Factors in Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 797-809 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For a graph G and even integers b ≥ a ≥ 2, a spanning subgraph F of G such that a ≤deg_F (x) ≤ b and deg_F (x) is even for all x ∈ V (F) is called an even [a, b]-factor of G. In this paper, we show that a 2-edge-connected graph G of order n has an even [2, b]-factor if max{deg_G (x) , deg_G (y) }≥max{2n/2+b , 3 } for any nonadjacent vertices x and y of G. Moreover, we show that for b ≥ 3a and a gt; 2, there exists an infinite family of 2-edge-connected graphs G of order n with δ (G) ≥ a such that G satisfies the condition deg_G (x) + deg_G (y) gt; 2an/a+b for any nonadjacent vertices x and y of G, but has no even [a, b]-factors. In particular, the infinite family of graphs gives a counterexample to the conjecture of Matsuda on the existence of an even [a, b]-factor.
Keywords: [ a, b ]-factor, even factor, 2-edge-connected, minimum degree 
@article{DMGT_2017_37_3_a20,
     author = {Tsuchiya, Shoichi and Yashima, Takamasa},
     title = {A {Degree} {Condition} {Implying} {Ore-Type} {Condition} for {Even} [2, {b]-Factors} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {797--809},
     year = {2017},
     volume = {37},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a20/}
}
TY  - JOUR
AU  - Tsuchiya, Shoichi
AU  - Yashima, Takamasa
TI  - A Degree Condition Implying Ore-Type Condition for Even [2, b]-Factors in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 797
EP  - 809
VL  - 37
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a20/
LA  - en
ID  - DMGT_2017_37_3_a20
ER  - 
%0 Journal Article
%A Tsuchiya, Shoichi
%A Yashima, Takamasa
%T A Degree Condition Implying Ore-Type Condition for Even [2, b]-Factors in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 797-809
%V 37
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a20/
%G en
%F DMGT_2017_37_3_a20
Tsuchiya, Shoichi; Yashima, Takamasa. A Degree Condition Implying Ore-Type Condition for Even [2, b]-Factors in Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 797-809. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a20/

[1] M. Kouider and P.D. Vestergaard, On even [2, b ] -factors in graphs, Australas. J. Combin. 27 (2003) 139–147.

[2] M. Kouider and P.D. Vestergaard, Even [ a, b ] -factors in graphs, Discuss. Math. Graph Theory 24 (2004) 431–441. doi:10.7151/dmgt.1242

[3] L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970) 391–416. doi:10.1016/S0021-9800(70)80033-3

[4] H. Matsuda, Ore-type conditions for the existence of even [2, b ] -factors in graphs, Discrete Math. 304 (2005) 51–61. doi:10.1016/j.disc.2005.09.009

[5] W.T. Tutte, Graph factors, Combinatorica 1 (1981) 79–97. doi:10.1007/BF02579180