Connected [a,b]-factors in Graphs

In this paper, we prove the following result: Let G be a connected graph of order n, and minimum degree . Let a and b two integers such that 2a <= b. Suppose and . Then G has a connected [a,b]-factor. Received February 10, 1998/Revised July 31, 2000     

Decomposition of Graphs into (g, f)-Factors

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg _G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. Revised: June 11, 1998     

图的（g，f）－因子和因子分解

设Ｇ是一个图，ｇ，ｆ是定义在图Ｇ的顶点集上的两个整数值函数且图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ）有本文给出了一个图（ｇ，ｆ）－可因子化的若干充分条件和一个图是（ｇ，ｆ）－消去图的充分必要条件，并研究了这些条件的应用。     

图的（g，f）－因子和因子分解

设Ｇ是一个图，ｇ，ｆ是定义在图Ｇ的顶点集上的两个整数值函数且图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ）有本文给出了一个图（ｇ，ｆ）－可因子化的若干充分条件和一个图是（ｇ，ｆ）－消去图的充分必要条件，并研究了这些条件的应用。     

有约束条件的图的(g,f)-因子

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g＜f.图G的一个(g,f)-因子是G的一个支撑子图F使对任意的x∈V(G)有g(x)≤dF(x)≤f(x).如果过图G的任意k条边都有一个(g,f)-因子,则称图G是一个(g,f)-k-覆盖图.如果图G的任意k条边不属于它的一个(g,f)-因子,则称图G是一个(g,f)-k-消去图.作者分别给出了一个图是(g,f)-k-覆盖图和(g,f)-k-消去图的充分条件.     

关于含1—因子图幂中边不交1—因子

本文讨论一般含1-因子连通图的n次幂中边不交1-因子的个数.从而证明了L.Nebesky(1984)猜想对含1-因子图成立.     

Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

Toughness of Graphs and [2,b]-Factors

A sharp bound of the toughness of a graph for the existence of a [2,b]-factor is given in this paper, whereb > 2.     

On Graphs With Small Ramsey Numbers,II

There exists a constant C such that for every d-degenerate graphs G ₁ and G ₂ on n vertices, Ramsey number R(G ₁,G ₂) is at most Cn, where is the minimum of the maximum degrees of G ₁ and G ₂.* The work of this author was supported by the grants 99-01-00581 and 00-01-00916 of the Russian Foundation for Fundamental Research and the Dutch-Russian Grant NWO-047-008-006. The work of this author was supported by the NSF grant DMS-9704114.     

On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

On Circular Flows Of Graphs

A sufficient condition for graphs with circular flow index less than 4 is found in this paper. In particular, we give a simple proof of a result obtained by Galluccio and Goddyn (Combinatorica, 2002), and obtain a larger family of such graphs. * Partially supported by the National Security Agency under Grants MDA904-01-1-0022.     

On（g,f）—Uniform Graphs

Thegraphsconsideredinthispaperwillbesimpleundirectedgraphs.LetGbeagraphwithvertexsetV(G)andedgesetE(G).ForavertexxofG,thedegreeofxinGisdenotedbydG(x).Theminimumdegreeandthemaximumdegree0fGaredenotedbyS(G)andb(G),respectively.Letgandfbetw0integer-valuedfunctionsdefined0nV(G)suchthatg(x)5f(x)foreveryx6V(G).Thena(g,f)-factorofGisaspanningsubgraphFofGsatisfyingg(x)SdF(x)5f(x)forallxEV(G).Ifg(x)=f(x)foreachxEV(G),thena(g,f)-factoriscalledanf-factor.Iffisaconstantfunctiontakingthevaluek,…     

On （g, f）-Uniform Graphs

A graph G is called a (g, f)-uniform graph if for each edge of G, there is a (g, f)-factor containing it and another (g, f)-factor excluding it. In this paper a necessary and sufficient condition for a graph to be a (g, f)-uniform graph is given and some applications of this condition are discussed. In particular, some simple sufficient conditions for a graph to be an [a, b]-uniform graph are obtained for a≤b.     

分数(g,f)-因子覆盖图

一个图称为分烽（g,f)- 因子覆盖图，如果G中的任何一条边e都包含在一个分数（g,f)- 因子中，并且满足h(e)=1，其中h是分数（g,f)- 因子的导出函数。本文给出了一个图是分数（g,f)- 因子覆盖图的充要条件。     

（mg＋m—1,mf—m＋1）—图的（g,f）—因子

本文证明了（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图具有一些特殊的（ｇ,ｆ）－因子,从而推广到了关于（ｇ,ｆ）－覆盖图和（ｇ,ｆ）－消去图的有关结果,有助于进一步研究（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图的正交因子分解问题。     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

图的[a,b]-因子存在性的两个结果

设G是一个图,a,b是整数且满足0≤a≤b.如果存在G的一个支撑子图F,使对任意的x∈V(G)有a≤dF(x)≤b,则称F是G的—个[a,b]-因子.本文给出图中具有特定性质的[a,b]-因子的两个充分条件.