Group distance magic and antimagic graphs

Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V (G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V (G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups.     

一类新的魔术染色

借鉴于Kotzig和Rosa在1970年定义的边魔术全标号,我们给具有p个顶点和q条边的图G定义了一个新的染色标号,叫作k-魔术染色f,其中f是一一映射V（G）∪E（G）→{1,2,…,p＋q},使得任何边uv∈E（G）满足f（u）＋f（v）=k＋f（uv）,并得到超级k-魔术染色的概念.我们得到了一些具有k-魔术染色或超级k-魔术染色图的性质以及构造这些图的方法.最后,我们猜测所有的树具有一个超级k-魔术染色.     

Graphs of Large Linear Size Are Antimagic

Given a graph and a colouring , the induced colour of a vertex v is the sum of the colours at the edges incident with v. If all the induced colours of vertices of G are distinct, the colouring is called antimagic. If G has a bijective antimagic colouring , the graph G is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than K₂ are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least for some constant c; we improve on this result, proving the conjecture for graphs with average degree at least some constant d₀.     

An application of the combinatorial Nullstellensatz to a graph labelling problem

An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K₂, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=p^k vertices, where p is an odd prime and k is a positive integer that admits a C_p‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010.     

Total edge irregularity strength of complete graphs and complete bipartite graphs

A total edge irregular k-labelling ν of a graph G is a labelling of the vertices and edges of G with labels from the set {1,…,k} in such a way that for any two different edges e and f their weights φ(f) and φ(e) are distinct. Here, the weight of an edge g=uv is φ(g)=ν(g)+ν(u)+ν(v), i. e. the sum of the label of g and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labelling is called the total edge irregularity strength of G.We have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.     

路及其相关图的序列性

设G是一个简单图,在G上当且仅当两个顶点的距离为2时增加一条边,所得的图称为G的平方,记作G2;在G上每个顶点都增加一条悬挂边所得的图称为G的冠,记作I(G).设Pn是n个顶点的路,本文给出了I(Pn2)、I(Fn)、F2n徊和I(Fn2)的序列标号.     

The Minimum FIll—in for the Corona of Two Graphs

Ｔｈｅ　Ｍｉｎｉｍｕｍ　Ｆｉｌｌ－ｉｎ　ｆｏｒ　ｔｈｅ　Ｃｏｒｏｎａ　ｏｆ　Ｔｗｏ　ＧｒａｐｈｓＴｈｅＭｉｎｉｍｕｍＦｉｌｌ－ｉｎｆｏｒｔｈｅＣｏｒｏｎａｏｆＴｗｏＧｒａｐｈｓ￥ＪｉｎＺｈｉｙｏｎｇ；ＬｉＷｅｎｑｕａｎ（ＨｅｎａｎＵｎｉｖｅｒｓｉｔｙ...     

关于可嵌人曲面图的列表(d,1)-全标号问题

图的(d,1)-全标号问题最初是由Havet等人提出的.在本文中,我们考虑了可嵌入曲面图的列表(d,1)-全标号问题,并证明了其列表(d,1)-全标号数不超过△(G)+2d.     

OPTIMAL LABELLING OF UNIT INTERVAL GRAPHS

This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, modified cutwidth, and bandwidth sum(linear arrangement).     

On Cyclic Packing of a Tree

We prove that there exists a packing of copies of a tree of size into K_n. Moreover, the proof provides an easy algorithm.Acknowledgments. The research of the second author was partially supported by Deutscher Akademischer Austauschdienst.     

具有匹配对网络模型的优美性

在当今网络研究中,人们需要将某些特殊的图分解为指定的结构.优美图可以被运用到图分解中.得到一些构造优美图的可算法化的方法,并构造较为复杂的优美图.     

A simplex-based labelling algorithm for the linear fractional assignment problem

This paper constructs an algorithm to solve the fractional assignment problem. Algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They also neglect the difficulties caused by degeneracy. The proposed algorithm performs optimization once and overcomes degeneracy. The main features of the algorithm are an effective initial heuristic approach, a simple labelling procedure and an implicit primal-dual schema. A numerical example is presented and demonstrates that the proposed algorithm is easy to apply. Computational results are compared with those from other developed methods. The results show that the proposed algorithm is efficient.     

图带宽和与其对偶超图带宽和的关系

设H=（E1,E2,…,Em）是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS（H,f）=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和．论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系．     

Irregularity strength of trees

The main result of this paper establishes that the irregularity strength of any tree with no vertices of degree two is its number of pendant vertices.     

ContributionsIrregularity strength of trees

The main result of this paper establishes that the irregularity strength of any tree with no vertices of degree two is its number of pendant vertices.     

优美图的一些性质

对于一个(p,q)-图G,如果存在一个单射.f:V(G)→{0,1,…,q},使得边标号集合{f(uv)| uv∈E(G)}={1,2,…,q},其中边标号为f(uv)=|f(u)-f(v)|,那么称G是优美图,并称.f是G的一个优美标号.通过研究若干优美图,得出一些优美图的性质.     

几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

积图P_n×P_m的奇优美性和奇强协调性

给出了积图P_n×P_m的奇优美标号和奇强协调标号.     

图P_m×C_n和W(m,n)的序列性

给出了图Pm×Cn,I(Pm×Cn)和W(m,n)的序列标号.证明了图Pm×Cn,I(Pm×Cn)和W(m,n)(m≥1,n≥3且n为奇数)是序列图,从而也是调和图.