八島 高将

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 is an element of 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{ 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 (5(G) a such that G satisfies the condition degG (x) degG (y) > 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.

Let a and b be positive integers with a < b. In this paper, we obtain a neighborhood-union condition for the existence of a Hamiltonian [a, b]-factor showing the following result: For a Hamiltonian graph G of sufficiently large order n, if delta(G) >= a + 2 and [N-G(x) boolean OR N-G(y)1 >= an/a+b + 3 for any nonadjacent vertices x, y is an element of V(G), then G has an [a, b]-factor avoiding a specified Hamiltonian cycle. (C) 2016 Elsevier B.V. All rights reserved.