ON ORTHOGONAL [0,k_1]~m_1-FACTORIZATION OF GRAPHS

1BasicDefinitionsandNotationsWedealwithfiniteundirectedgraphswhichmadhavemultipleedgesbuthavenoloops.LetGbeagraphwithvertexsetV(G)andedgesetE(G).ForeachxEV(G),wedenotethedegreeofzinGbydG(x).Letg,fbetwointeger-valuedfunctionsdefinedonV(G)suchthatg(x)5f(x)forallxEV(G).A(g,f)-factorofGisaspanningsubgraphFofGsuchthatg(x)SdF(x)5f(x)forallxEV(G),andwecallthatFisa(g,f)-factorOfG.Ifg(x)5dG(x)Sf(x)forallxEV(G),thenwecallthatGis(g,f)-graph.Inparticular,g(x)=a,f(x)=bforallxEV(G),thenwecal…     

(g,f)-FACTORIZATIONS OF GRAPHS ORTHOGONAL TO [1,2]-SUBGRAPH

1.IntroductionAllgraphsunderconsiderationaresimple.LetCbeagraphwithvertexsetV(G)andedgesetE(G).Anedgejoiningvenicesuandvisdenotedbyac.Foravertexv6V(G),wedenotethedegreeofvinGbydG(v).Letg(x)andf(x)beinteger--valuedfunctionsdefinedonV(G)withf(x)2g(x)forallxEV(G).AgraphGiscalleda(g,f)-graphifg(v)5dG(v)5f(v)foreachvertexvEV(G),anda(g,f)--factorofagraphGisaspanning(g,f)-subgraphofG.A(g,f)-factorizationF~{FI,F2,'',Fi}ofthegraphGisapartitionofE(G)intoedge-disjointspanning(g,f)-subgraphs…     

On Factor-Uniform Graphs

Graphsunderconsiderationarefiniteundirected,andbasicgraph-theoreticnotationandtermsusedarethesamewiththatin[1].LetG=(V(G),E(G))beagraphwhichmayhaveloopsormultipleedges,Z~{0,if,12,.'.},g,f:V(G)-Z,p(g,f)~{xEV(G)lg(x)~f(x)}andp(g,f)GPgV(G).Supposeg(x)5f(x)forallxEV(G)andg(x)~f(x)(mod2)forallxEP.Thena(P,f)-congruent(g,f)-factorofGisaspanningsubgraphFofGsuchthatg(x)5dF(x)5f(x)forallxEV(G)anddF(x)~f(x)(mod2)forallxCP.Giscalled(g,f;p)-covered(-deleted,resp.)if,foreachedgeeofG,thereexist…     

FRACTIONAL (g, f)-FACTORS OF GRAPHS

1 IntroductionThe graphs considered in this paper will be finite undirected graphs wllicll 11lay llavemultiple edges but no loops. Let G be a grapll with vertex set V(G) and edge set E(G). Fora vertex x of G, the degree of x in G is denoted by dG(z). Let g and f be two integer-valuedfunctions defined o11 V(G) such that 0 < g(z) 5 f(x) fOr all x E V(G). Then a (g, f)-factorof G is a spanning 8ubgraph F of G satisfying g(x) < dG(z) 5 f(x) for all x E V(F). Ifg(x) = f(x) for all x E V(…     

ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS

1 IntroductionIn this paper we con8ider finite undirected simple graphs. Let G be a graph with vertexset V(G) and edge set E(G). Let g and f be two po8itive iuteger-valued functions defined onV(G) such that g(x) 5 f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanningsubgraph H of G satisfying g(x) 5 dH(x) 5 f(x) for each x E V(H). In particular, if G itselfis a (g, f)-factor, then G is called a (g, f)-grapl1. A subgrapl1 H of G is called an rmsubgraphif H has m edg…     

ON ORTHOGONAL (0,f)-FACTORIZATIONS

1991MRSubjectClassification05C701IntroductionAllgraphsconsi(lere(1arefilliteulldirectedsimplegraphs.LetgandfI)einteger-v;tllle(1fllnctionsdefinedonV(G)suchthat05g(x)5f(x)foreverya:EV(G).A(g,f)--tActorofGisaspanningsubgraphFofGsuchthatg(x)5da(x)5f(x)foreveryxEV(G).IfGitselfisa(g,f)-factor,thenGiscalls(1a(g,f)--graph.A(g,f)--factorizationF={FI,F2,'.F,,,}ofGisapartitionofGilltoedge-disjoint(g,f)--factorsFI5F2,'5Fm.LetHbeasubgrapllofGwith?nedges,thenFiscalledorthogonaltoHifeach…     

On the Factorizations of （mg, mf）-graph

Let G be an (mg, mf)-graph, where g and f are integer-valued functions defined on V(G) and such that 0≤g(x)≤f(x) for each x ∈ V(G). It is proved that(1) If Z ≠ , both g and f may be not even, G has a (g, f)-factorization, where Z = {x ∈ V(G): mf(x)-dG(x)≤t(x) or dG(x)-mg(x)≤ t(x), t(x)= f(x)-g(x)>0}.(2) Let G be an m-regular graph with 2n vertices, m≥n. If (P1, P2,..., Pr) is a partition of m, P1 ≡ m (mod 2), Pi ≡ 0 (mod 2), i = 2,..., r, then the edge set E(G) of G can be parted into r parts E1 , E2,...,Er of E(G) such that G[Ei] is a Pi-factor of G.     

关于图是(g,f,n)-临界图的充分条件

设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)＜f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.     

图中推广的正交因子分解

设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k相似文献   

A polynomial algorithm for finding (g,f)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x)≤ f(x) for every vertex x of V(G). A (g. f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g. f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

On Domination and Independence Numbers of Graphs

A set S of vertices of a graph G is dominating if each vertex x not in S is adjacent to some vertex in S, and is independent if no two vertices in S are adjacent. The domination number, γ(G), is the order of the smallest dominating set in G. The independence number, α(G), is the order of the largest independent set in G. In this paper we characterize bipartite graphs and block graphs G for which γ(G) = α(G).     

A characterization of well-covered graphs that contain neither 4- nor 5-cycles

A graph is well covered if every maximal independent set has the same cardinality. A vertex x, in a well-covered graph G, is called extendable if G – {x} is well covered and β(G) = β(G – {x}). If G is a connected, well-covered graph containing no 4- nor 5-cycles as subgraphs and G contains an extendable vertex, then G is the disjoint union of edges and triangles together with a restricted set of edges joining extendable vertices. There are only 3 other connected, well-covered graphs of this type that do not contain an extendable vertex. Moreover, all these graphs can be recognized in polynomial time.     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.     

几类特殊Corona图的b-染色数与b-连续性研究

在一个图G的正常k染色中,如果每一个颜色类中都至少存在一个顶点,使得其在其它的k-1个颜色类中都至少有一个邻居,则称这样的正常k染色为b-染色.一个图G的b-染色数是最大的正整数k,使得用k种颜色能够对G进行b-染色,用b(G)来表示.如果对于任意的正整数k:χ(G)≤k≤b(G),用k种颜色可以对图G进行b-染色,则称图G是b-连续的.设G1与G2为任意图,称图G=G_1·G_2为图G_1与G_2的Corona图,其中G包含G_1的一个拷贝,包含G_2的|V(G_1)|个拷贝,且G_1的第i个顶点与G_2的第i个拷贝的所有顶点都邻接.研究了路图与路图、星形图以及轮图所构成的Corona图P_n·P_m、P_n·K_(1,m)以及P_n·W_(m+1)的m-度,b-染色数与b-连续性.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

Graham’s pebbling conjecture on product of complete bipartite graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are complete bipartite graphs.     

完全二部图K_(1,n),K_(2,n)和K_(3,n)的点强可区别全染色

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2.     

上连通和超连通的三次Bi-Cayley图

Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.