- Tytuł:
- A Degree Condition Implying Ore-Type Condition for Even [2, b]-Factors in Graphs
- Autorzy:
-
Tsuchiya, Shoichi
Yashima, Takamasa - Powiązania:
- https://bibliotekanauki.pl/articles/31341635.pdf
- Data publikacji:
- 2017-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
[ a, b ]-factor
even factor
2-edge-connected
minimum degree - Opis:
- For a graph $G$ and even integers $ b \ge a \ge 2 $, a spanning subgraph $F$ of $G$ such that $ a \le \text{deg}_F (x) \le b $ and $ \text{deg}_F (x) $ is even for all $ x \in 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 $ \text{max} \{ \text{deg}_G (x) , \text{deg}_G (y) \} \ge \text{max} \{ \frac{2n}{2+b} , 3 \} $ for any nonadjacent vertices $x$ and $y$ of $G$. Moreover, we show that for $ b \ge 3a$ and $a > 2$, there exists an infinite family of 2-edge-connected graphs $G$ of order $n$ with $ \delta (G) \ge a$ such that $G$ satisfies the condition $ \text{deg}_G (x) + \text{deg}_G (y) > \frac{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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 797-809
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł