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

Shoichi Tsuchiya; Takamasa Yashima

Discussiones Mathematicae Graph Theory (2017)

  • Volume: 37, Issue: 3, page 797-809
  • ISSN: 2083-5892

Abstract

top
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 { deg G ( x ) , deg G ( y ) } max 2 n 2 + b , 3 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 ) > 2 a n 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.

How to cite

top

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 -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.