数学物理学报(英文版) ›› 2013, Vol. 33 ›› Issue (3): 621-630.doi: 10.1016/S0252-9602(13)60025-9

• 论文 • 上一篇    下一篇

ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

姚兵|陈祥恩|镡松龄   

  1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou, Gansu 730070, China; Department of Mathematics and Statistics of Georgia State University, Atlanta, 30303-3083, USA
  • 收稿日期:2010-11-27 修回日期:2012-06-16 出版日期:2013-05-20 发布日期:2013-05-20
  • 基金资助:

    The first author is supported by the National Natural Science Foundation of China (61163054); the second author is supported by the National Natural Science Foundation of China (61163037).

ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

 YAO Bing, CHEN Xiang-En, SHAN Song-Ling   

  1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou, Gansu 730070, China; Department of Mathematics and Statistics of Georgia State University, Atlanta, 30303-3083, USA
  • Received:2010-11-27 Revised:2012-06-16 Online:2013-05-20 Published:2013-05-20
  • Supported by:

    The first author is supported by the National Natural Science Foundation of China (61163054); the second author is supported by the National Natural Science Foundation of China (61163037).

摘要:

It has been known that determining the exact value of vertex distinguishing edge index ′s(G) of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let nd(G) denote the number of vertices of degree d in G, and let  x ′es(G) be the equitable vertex
distinguishing edge index of G. We show that a tree T holds n1(T)≤x  ′s(T) ≤ n1(T) + 1 and  x ′s(T) = x  ′es(T) if T satisfies one of the following conditions (i) n2(T) ≤ Α(T) or (ii) there exists a constant c with respect to 0 < c < 1 such that n2(T)≤ cn1(T) and ∑3≤d≤Δ(T) nd(T) ≤ (1 − c)n1(T) + 1.

关键词: Vertex distinguishing edge coloring, equitable coloring, trees

Abstract:

It has been known that determining the exact value of vertex distinguishing edge index ′s(G) of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let nd(G) denote the number of vertices of degree d in G, and let  x ′es(G) be the equitable vertex
distinguishing edge index of G. We show that a tree T holds n1(T)≤x  ′s(T) ≤ n1(T) + 1 and  x ′s(T) = x  ′es(T) if T satisfies one of the following conditions (i) n2(T) ≤ Α(T) or (ii) there exists a constant c with respect to 0 < c < 1 such that n2(T)≤ cn1(T) and ∑3≤d≤Δ(T) nd(T) ≤ (1 − c)n1(T) + 1.

Key words: Vertex distinguishing edge coloring, equitable coloring, trees

中图分类号: 

  • 05C15