On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

A Graceful Numbering of A Class of Graphs

The graphs considered here are finite, undirected and simple. The sets ofvertices and edges of a graph G are denoted by V(G) and E(G), respectively.A graph G is called to be numbered if each vertex υ of G is assigned a nonnegative integer φ(υ), and each edge {u,υ} is assigned the absolute value of thedifference of the numbers at its endpoints, i.e.,|φ(u)-φ(υ)|.     

HAMILTONIAN DECOMPOSITION OF CAYLEY GRAPHS OF ORDERS p~2 AND pq

1. IntroductionLet G be a finite group and S a subset of G such that S--1 ~ S, and 1 f S. The Cayleygraph Cay (G, S) is defined as the simple graph with V ~ G, and E = {glgZ I g,'g, or g,'g,6 S, gi, gi E G}. Cay (G, S) is vertex-transitive, and it is connected if and only if (S) = G,i.e. S is a generating set of G[1]. If G = Zn, then Cay (Zn, S) is called a circulant graph. Ithas been proved that any connected Cayley graph on a finite abelian group is hamiltonianl2].Furthermore, …     

A conjecture on k-factor-critical and 3-γ-critical graphs

For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination number γ(G) of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,if γ(G-v) γ(G) for any vertex v in G.A graph G is domination edge critical,if γ(G ∪ e) γ(G) for any edge e ∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical) if it is domination vertex critical(resp.domination edge critical) and γ(G) = k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.     

Longest Cycles in 3-Connected k-Regular Claw-Free Graphs

All graphs considered here are undirected aud finite without loop or multipleedges. A graph is called claw-free if it do not contain a K_(1,3) as an inducedsubgraph. Let δ(G) denote the minimum degree of a graph G, and let V(G) andE(G) be the vertex set and edge set of G, respectively. For a subset S of V(G)and a subgraph H of G,G[S] and G-H denote the subgraphs of G induced by the     

THE MINIMAL CLOSED NON-TRIVIAL IDEALS OF TOEPLITZ ALGEBRAS ON DISCRETE GROUPS

61. IntroductionLet G be a discrete (not necessarily abelian) group. For any subset G of G, we saythat (G, G ) is a quasi-partial ordered group if e 6 G , G ' G G G and G = G ' G ',where e is the unit of G and G ' = {g--' I g e G }; further, (G, G ) is referred to as aquasi-ordered group if G = G u G '. Note that when G7 = G n G ' = {e}, a quasi-partial ordered group (resp. quasi-ordered group) (G, G ) is known as a pajrtially ordered(resp. ordered) group.Let { 6, I g e G } b…     

Number of Induced Matchings of Graphs

A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.     

Neighbor sum distinguishing total colorings of triangle free planar graphs

A total k-coloring c of a graph G is a proper total coloring c of G using colors of the set[k] = {1, 2,..., k}. Let f(u) denote the sum of the color on a vertex u and colors on all the edges incident to u. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G such that for each edge uv ∈ E(G), f(u) = f(v). By χ nsd(G), we denote the smallest value k in such a coloring of G. Pil′sniak and Wo′zniak conjectured that χ nsd(G) ≤Δ(G) + 3 for any simple graph with maximum degree Δ(G). In this paper, by using the famous Combinatorial Nullstellensatz, we prove that the conjecture holds for any triangle free planar graph with maximum degree at least 7.     

ON EDGE-HAMILTONIAN PROPERTY OF BI-CAYLEY GRAPHS

Let G be a finite group, and S be a subset of G. The bi-Cayley graph BCay(G, S)of G with respect to S is defined as the bipartite graph with vertex set G × {0, 1} and edge set {(g, 0),(gs, 1)| g ∈ G, s ∈ S}. In this paper, we first provide two interesting results for edge-hamiltonian property of Cayley graphs and bi-Cayley graphs. Next,we investigate the edge-hamiltonian property of Γ = BCay(G, S), and prove that Γis hamiltonian if and only if Γ is edge-hamiltonian when Γ is a connected bi-Cayley graph.     

Continuous Forcing Spectra of Even Polygonal Chains

Let G be a graph that admits a perfect matching M.A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G.The cardinality of a forcing set of M with the smallest size is called the forcing number of M,denoted by f(G,M).The forcing spectrum of G is defined as:Spec(G)={f(G,M)|M is a perfect matching of G}.In this paper,by applying the Ztransformation graph(resonance graph)we show that for any polyomino with perfect matchings and any even polygonal chain,their forcing spectra are integral intervals.Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks.Forcing spectra of two extremal chains are determined.     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

M(G,x)≤2的图匹配等价的充要条件

对一个图G,设μ(G,x)表示它的匹配多项式,M(G,x)表示μ(G,x)的最大实数根.令Г_1={G|M(G,x)<2}和Г2={G|M(G,x)≤2}.给出了Г_i(i=1,2)中的两个图G和H匹配等价的充要条件.     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

正则图的限制性边连通度

将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度. 用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度. 如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k＞|G|/2时,k正则图G是极大限制性边连通的,其中k≥2, |G|≥4; k的下界在某种程度上是不可改进的.     

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G,如果对于V(G)的任意k元子集S,子图G-S都包含分数完美匹配,那么称G为分数后-因子临界图.如果图G的每个k-匹配M都包含在一个分数完美匹配中,那么称图G为分数k-可扩图.给出一个图是分数k-因子临界图和分数k-可扩图的充分条件,并给出一个图是分数k-因子临界图的充分必要条件.     

CHROMATIC NUMBER OF SQUARE OF MAXIMAL OUTERPLANAR GRAPHS

Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.     

关于图P_n~k的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的.     

给定匹配数和独立数时图零度的上界

设G是一个有n个点的简单图,分别记η(G),m(G)和α(G)为图G的零度、匹配数和独立数.设θ(G)是一个非负整数,定义为使图G成为二部图至少需要从G的边集中删去的边数.本文运用二部划分运算,证明了对于有n个点并且不含有圈长为2的倍数的圈为子图的简单图G,有η(G)≤n-2m(G)+20(G)和η(G)≤2α(G)+2θ(G)-n.     

On the Number of Group-Weighted Matchings

Let G be a bipartite graph with a bicoloration {A,B}, |A|=|B|. Let E(G) A x B denote the edge set of G, and let m(G) denote the number of perfect matchings of G. Let K be a (multiplicative) finite abelsian group |K| = k, and let w:E(G) K be a weight assignment on the edges of G. FOr S E(G) let w(S) = _eSw(e). A perfect matching M of G is a w-matching if w(M)=1. We shall be interested in m(G,w), the number of w-matchings of G.It is shown that if deg(a) d for all a A, then either G has no w-matchings, or G has at least (d - k + 1)! w-matchings.