ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

doi:10.1016/S0252-9602(13)60025-9

Acta mathematica scientia,Series B ›› 2013, Vol. 33 ›› Issue (3): 621-630.doi: 10.1016/S0252-9602(13)60025-9

• Articles • Previous Articles Next Articles

ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

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

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).

Abstract

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 n_d(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 n₁(T)≤x ′_s(T) ≤ n₁(T) + 1 and x ′_s(T) = x ′_es(T) if T satisfies one of the following conditions (i) n₂(T) ≤ Α(T) or (ii) there exists a constant c with respect to 0 < c < 1 such that n₂(T)≤ cn₁(T) and ∑_{3≤d≤Δ(T)} n_d(T) ≤ (1 − c)n₁(T) + 1.

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

CLC Number:

05C15

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.

Trendmd

References

[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

ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 10

[1]	Zhang Zhongfu; Wang Weifan; Li Jingwen; Yao Bing; Bu Yuehua. EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE [J]. Acta mathematica scientia,Series B, 2006, 26(3): 477-482.
[2]	Liu Hongmei. CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS [J]. Acta mathematica scientia,Series B, 2006, 26(2): 314-320.
[3]	WANG Wei-Fan, ZHANG Ke-Min. ENTIRE CHROMATIC NUMBER AND -MATCHING OF OUTERPLANE GRAPHS [J]. Acta mathematica scientia,Series B, 2005, 25(4): 672-680.
[4]	WANG Wei-Fan, ZHANG Ke-Min. A SEVEN-COLOR THEOREM ON EDGE-FACE COLORING OF PLANE GRAPHS [J]. Acta mathematica scientia,Series B, 2001, 21(2): 243-248.