Connected [k, k + 1]-factors of graphs

✍ Scribed by Mao-cheng Cai

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 541 KB
• Volume: 169
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00328-t

✦ Synopsis

Let k be an odd integer /> 3, and G be a connected graph of odd order n with n/>4k -3, and minimum degree at least k. In this paper it is proved that if for each pair of nonadjacent vertices u, v in G max{dG(u), d~(v)} >~n/2, then G has an almost k--factor F + and a matching M such that F-and M are edge-disjoint and F-+M is a connected [k,k + 1]-factor of G (an almost k±-factor F ± is a factor that every vertex has degree k except at most one with degree k 4-1 ).

As an immediate consequence, the result gives a solution to a problem of Kano on the existence of connected [k, k + 1 ]-factors

The terminology used here is rather standard. All graphs under consideration are undirected, finite and simple. A graph G = (V,E) consists of a non-empty set V(G) of vertices and a set E(G) of edges. Let xy denote the edge joining vertices x and y.

If a graph H is a subgraph of G, we write H C_ G. Given disjoint subsets X and Y of V(G), we denote by G[X] the subgraph of G induced by X, and write

Sometimes x is used for a singleton {x} and co(H, Y) = eo(V(H), Y) for a subgraph H of G -Y. Given a graph G = (V,E) and x E V(G), the set of vertices adjacent to x is denoted by No(x), do(x) = [No(x)[ is said to be the degree of x and No[x] = No(x) U x. Let G be a graph and f an integer-valued function defined on V(G) such