Binding Number and Fractional k-Factors of Graphs

In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It is proved that a graph G has a fractional 1-factor if bind(G)≥1and has a fractional k-factor if bind(G)≥k−1k. Furthermore, it is showed that both results are best possible in some sense.

Binding Numbers for Fractional ID-k-factor-critical Graphs

LetG be a graph,and k≥2 be a positive integer.A graph G is fractional independentset-deletable k-factor-critical（in short,fractional ID-k-factor-critical）,if G I has a fractional k-factor for every independent set I of G.The binding number bind（G）of a graph G is defined as bind（G）=min｜NG（X）｜｜X｜：=X V（G）,NG（X）=V（G）.In this paper,it is proved that a graph G is fractional ID-k-factor-critical if n≥6k 9 and bind（G）〉（3k 1）（n 1）kn 2k＋2.

MIMUMUM DEGREE AND BINDING NUMBER FOR k-FACTORS WITH PRESCRIBED PROPERTIES

Let integer k≥1, G be a graph of order n,n≥max {4k - 6, 4} and kn=0 (mod 2). Assume that the binding number of G is more than 2-2/n or the minimum degree of G is more than n/2. We prove that (i) G hasa k-fartor that contains a given edge; (ii) G has a k-factor that does not contain a given edge.

Binding Number, Minimum Degree and Bipancyclism in Bipartite Graphs

Let G =（V1,V2,E） be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B（G）,is defined to be n if G =Kn and min i∈{1,2}｜N（S）｜〈n min ｜N（S）｜/｜S｜otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B（G） 〉 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows：Let 0 〈 c 〈 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n（n is large enough） vertices such that B（G） c and δ（G）（2-c）n/（3-c）＋2/3.Then G is bipancyclic.

ON THE EDGE-BINDING NUMBER OF SOME PLANE GRAPHS

Let G(V,E) be a simple graph, the edge-binding number b1 (G) of G is defined as where N(S) denotes the adjacent edges set of S. In this paper, we obtained the edge-binding number of outer plane graphs, Halin graph and tree.

Remarks on Component Factors

In this remark,we first simply survey the important results on component factors in graphs.Then,we focus on the binding number condition of component factors in some special settings.The main contributions in this remark are two folded:(1)we reveal that the existence of some special component factors is equal to some specific binding number conditions;(2)the parameter conditions for a graph G with a P≥3-factor are determined.

Some Existence Theorems on Path Factors with Given Properties in Graphs

A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e∈E(G),which is defined by[Discrete Mathematics,309,2067-2076(2009)].We first define the concept of a(P≥n,k)-factor-critical covered graph,namely,a graph G is called(P≥n,k)-factor-critical covered if G-D is P≥n-factor covered for any D⊆V(G)with|D|=k.In this paper,we verify that(i)a graph G withκ(G)≥k+1 is(P≥2,k)-factor-critical covered if bind(G)>2+k/3;(ii)a graph G with|V(G)|≥k+3 andκ(G)≥k+1 is(P≥3,k)-factor-critical covered if bind(G)≥4+k/3.