A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs

Shoichi Tsuchiya, and Takamasa Yashima. "A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs." Discussiones Mathematicae Graph Theory 37.3 (2017): 797-809. <http://eudml.org/doc/288445>.

@article{ShoichiTsuchiya2017,
abstract = {For a graph G and even integers b ⩾ a ⩾ 2, a spanning subgraph F of G such that a ⩽ degF (x) ⩽ b and degF (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 degG (x),degG (y)⩾max 2n2+b,3 $\max \lbrace \deg _G (x),\deg _G (y)\rbrace \ge \max \left\lbrace \{\{\{2n\} \over \{2 + b\}\},3\} \right\rbrace $ for any nonadjacent vertices x and y of G. Moreover, we show that for b ⩾ 3a and a > 2, there exists an infinite family of 2-edge-connected graphs G of order n with δ(G) ⩾ a such that G satisfies the condition [...] degG (x)+degG (y)>2ana+b $\deg _G (x) + \deg _G (y) > \{\{2an\} \over \{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.},
author = {Shoichi Tsuchiya, Takamasa Yashima},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {[a,b]-factor; even factor; 2-edge-connected; minimum degree},
language = {eng},
number = {3},
pages = {797-809},
title = {A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs},
url = {http://eudml.org/doc/288445},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Shoichi Tsuchiya
AU - Takamasa Yashima
TI - A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 797
EP - 809
AB - For a graph G and even integers b ⩾ a ⩾ 2, a spanning subgraph F of G such that a ⩽ degF (x) ⩽ b and degF (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 degG (x),degG (y)⩾max 2n2+b,3 $\max \lbrace \deg _G (x),\deg _G (y)\rbrace \ge \max \left\lbrace {{{2n} \over {2 + b}},3} \right\rbrace $ for any nonadjacent vertices x and y of G. Moreover, we show that for b ⩾ 3a and a > 2, there exists an infinite family of 2-edge-connected graphs G of order n with δ(G) ⩾ a such that G satisfies the condition [...] degG (x)+degG (y)>2ana+b $\deg _G (x) + \deg _G (y) > {{2an} \over {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.
LA - eng
KW - [a,b]-factor; even factor; 2-edge-connected; minimum degree
UR - http://eudml.org/doc/288445
ER -