A DEGREE CONDITION FOR THE EXISTENCE OF CONNECTED [k, k 1]-FACTORS

ＡＤＥＧＲＥＥＣＯＮＤＩＴＩＯＮＦＯＲＴＨＥＥＸＩＳＴＥＮＣＥＯＦＣＯＮＮＥＣＴＥＤ［ｋ，ｋ＋１］－ＦＡＣＴＯＲＳＡＤＥＧＲＥＥＣＯＮＤＩＴＩＯＮＦＯＲＴＨＥＥＸＩＳＴＥＮＣＥＯＦＣＯＮＮＥＣＴＥＤ［ｋ，ｋ＋１］－ＦＡＣＴＯＲＳ￥ＣＡＩＭａｏｃｈｅｎ...     

A LOCALIZATION CONDITION FORBIPANCYCLIC BIPARTITE GRAPHS

1.IntroductionThefollowingNash--william'stheoremtellsusthatthehamiltonianproblemconcerningbipartitegraphsisimportant,thoughwedonotseemuchliteratureonit.Theorem111]Thejollowingproblemsareequivalent:1)thedete~inationofallhamiltoniangmphs,2)thedete~inationof…     

BINDING NUMBER AND MINIMUM DEGREE FOR [a,b]-FACTORS

We give some sufficient conditions on the binding number and the minimumdegree for a graph to have an [a, b]-factor.     

REMARKS ON THE BINDING NUMBER FOR [a,b]-FACTORS

We give some answers to the following question:If the binding numberof a graph G is more than 1+(a-1)/b,does G have an [a,b] -factor?     

A NOTE ON CONNECTED FACTORS IN CLAW-FREE GRAPHS

1. IntroductionAll graphs considered here are finite and undirected, without loops or multiple edges. Thevertex set, edge set and the degree of a vertex v of a graph G are denoted, respectively, byV(G),E(G) and dG(v). For a set S G V(G) the subgraph of G induced by S is denoted byG[S].Let G be a graph, j and g positive integer Valued functions on V(G) with f(v) S g(v) 5dG(u) for all v 6 V(G). A spanmng SUbgraph F Of G is called an [f,g]-factor Of G if forall v E V(G), f(v) 5 dF(v…     

PATH EXTENSIBILITY OF CONNECTED,LOCALLY 2-CONNECTED K_(1,3)-FREE GRAPHS

1.IntroductionandNotationqInthispaperswewillconsideronlyfinite,undirectedgraphs,withoutloopsandmultipleedges.Weusethenotationsandterminologyin[1].Inaddition,ifGisagraph,wedenotebyV(G)andE(G),respectively,thevertexsetandtheedgesetofG.ForanyaEV(G),ACV(G),BC…     

THE LINEAR ARBORICITY OF COMPOSITION GRAPHS

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G) 1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.     

FORBIDDEN SUBGRAPHS,DEGREES,NEIGHBORHOOD UNIONS AND CIRCUMFERENCES OF GRAPHS

Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:(1) Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G(?)|V_1(L)∩S_c|≥2 if L≌K_(1,3),and |V(L)∩S_c|≥1 if L≌P_4,then thecircumference of G is at least c,where V_1(L)is the set of vertices with degree 1 of L,S_c isthe set of vertices with degree at least c/2 of G and P_4 is a path of order 4.(2) Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K_(1,3)or P_4,d_L(u,v)=2(?)|N(u)∪N(v)|≥s,then the circumferencec (G) of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c(G)≥s+3.     

(4m, m)-CHOOSABILITY OF PLANE GRAPHS

1 IntroductionAll graphs considered in tabs paper are abate and sable. Undecked notations and termalnologies can be found in [if.Let G = (V, E,F) be a plase graph, where V, E and F denote the s6t of venices, edgesand faces of G, respectively. We use NG(v) and dG(v) to denote the set and nUmber of venicesadjacent to a vertex yi respectively, and use 6(G) to denote the inininuun degree of G. A vertexv is called a k-vertex if v has degree k. A face of a plane graph is said to be incident w…     

CYCLES CONTAINING MANY VERTICES OF SUBSETS IN GRAPHS WITH LARGE DEGREE SUMS AND NEIGHBORHOOD UNIONS

1. ResultsWe use[IJ for terminology and notations not defined here and consider simple graph only.Let G be a graph of order n and X C V(G). A graph G is called 1--tough if w(G\S) 5 ISIfor any S g V(G) with w(G\S) > 1, where w(G\S) denotes the number of components ofgraph G\S. A cycle C of G is called X-longest if no cycle of G contains more venices of Xthan C, and by c(X) we denote the number of venices of X in an X-longest cycle. A cycle Cof G is called X-dominating if all neigh…