Acta mathematica scientia, Series B >
ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES
Received date: 2010-11-27
Revised date: 2012-06-16
Online 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.
Key words： Vertex distinguishing edge coloring; equitable coloring; trees
YAO Bing , CHEN Xiang-En , SHAN Song-Ling . ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES[J]. Acta mathematica scientia, Series B, 2013 , 33(3) : 621 -630 . DOI: 10.1016/S0252-9602(13)60025-9
[1] Balister P N, Bollob´as B, Schelp R H. Vertex-distinguishing colorings of graphs with Δ(G) = 2. Discrete Mathmatics, 2002, 252(1/3): 17–29
[2] Bazgan C, Harkat-Benhamdine A, Li H,Wo´zniak M. On the vertex proper edge-colorings of graphs. Rapport de Recherche 1129, L R I, Universit´e de Paris-Sud, Centre d’Orsay, 1997; Also J Combin Theory, 1999, 75B: 288–301
[3] Burris A C, Schelp R H. Vertex-Distingushing proper edge-colorings. Journal of Graph Theory, 1997, 26(2): 73–82
[4] ˆCern´y J, Horˆn´ak M, Sot´ak R. Observability of A Graph. Mathematics in Slovaca, 1996, 46: 21–31
[5] Horˇn´ak M, Sot´ak R. Observability of complete multipartite graphs with equipotent parts. Ars Combinatoria,
1995, 41: 289–301
[6] Horˇn´ak M, Sot´ak R. Asymptotic behavior of the observability of Qn. Discrete Mathematics, 1997, 176: 139–148
[7] Balister P N, Kostochka A, Li H, Schelpa R H. Balanced edge colorings. Journal of Combinatorial Theory, 2004, 90B: 3–20
[8] Bazgan C, Harkat-Benhamdine A, Li H, Wo´zniak M. A note on the vertex-distinguishing proper coloring of graphs with large minimum degree. Discrete Mathematics, 2001, 236: 37–42
[9] Kemnitz A, Marangio M. d-Strong Edge Colorings of Graphs. Submitted to Discrete Mathematics
[10] Yao B, Zhang Z F, Wang J F. Some results on spanning trees. Acta Mathematicae Applicatae Sinica, English Series, 2010, 26(4): 607–616
[11] Yao B, Cheng H, Yao M, Zhang Z F. Behaviors of vetex neighbors of trees under some graph colorings. Acta Mathematica Scientia, 2011, 31A(2): 567–576
[12] Zhang Z F, Chen X E, Li J W, Yao B, Lu X Z, Wang J F. On adjacent-vertex-distinguishing total coloring of graphs. Science in China: Mathematics, 2005, 48A(3): 289–299
[13] Ostrovskii M I. Minimum congestion spanning trees in bipartite and random graphs. Acta Mathematica Scientia, 2011, 31B(2): 634–640
[14] Chen Dong, Wang Weifan. The numbers of spanning trees in some graphs. Acta Mathematica Scientia, 2008, 28A(5): 906–913
/
| 〈 |
|
〉 |