Vertex-distinguishing proper edge coloring of composition of complete graph and star

YANG Fang; WANG Zhi-wen; CHEN Xiang-en; MA Chun-yan

Issue 5

Sep. 2013

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2013 > (5): 136-143

YANG Fang, WANG Zhi-wen, CHEN Xiang-en, MA Chun-yan. Vertex-distinguishing proper edge coloring of composition of complete graph and star[J]. Journal of East China Normal University (Natural Sciences), 2013, (5): 136-143.

Citation:

YANG Fang, WANG Zhi-wen, CHEN Xiang-en, MA Chun-yan. Vertex-distinguishing proper edge coloring of composition of complete graph and star[J]. Journal of East China Normal University (Natural Sciences), 2013, (5): 136-143.

Citation:

PDF( 197 KB)

Vertex-distinguishing proper edge coloring of composition of complete graph and star

1.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China;
2.
School of Mathematics and Computer Sciences, Ningxia University, Yinchuan 750021, China

Received Date: 2012-09-01
Rev Recd Date: 2012-12-01
Publish Date: 2013-09-25

Abstract

Abstract

Firstly, we gave an upper bound for the vertex-distinguishing proper edge chromatic number of composition of complete graph $K_{p}$ and star $S_{q}$, which is $pq+1$ for $p\geq 2,~q\geq4$. Then by constructing coloring in terms of the symmetry of regular polygons and the methods of combinatorial analysis, we obtained respectively vertex-distinguishing proper edge chromatic numbers for composition of complete graph $K_{p}$ and star $S_{q}$ when $p=2,~q\geq4$; $p\geq3,~ q=4$; $p$ is even and $p\geq4,~q=5$; $pq$ is odd and $p\geq3,~q\geq5$.
- composition,
- complete graph,
- star,
- vertex-distinguishing proper edge coloring,
- vertex-distinguishing proper edge chromatic number

FullText(HTML)

References(1)

References

[1]

{1} BURRIS A C. Vertex-distinguishing edge-colorings[D]. Memphis:

Memphis State University, 1993.
{2} BALISTER P N, RIORDAN O M, SCHELP R H. Vertex-distinguishing edge

colorings of graphs[J]. J Graph Theory, 2003, 42(2): 95-109.
{3} BAZGAN C, HARKAT-BENHAMDINE A, LI H, et al. On the

vertex-distinguishing proper edge colorings of graphs[J]. J Combin

Theory, 1999, 75(2): 288-301.
{4} BURRIS A C, SCHELP R H. Vertex-distinguishing proper

edge-colorings[J]. J Graph Theory, 1997, 26(2): 73-82.
{5} CHEN X N, GAO Y P. Vertex-distinguishing proper edge-coloring

chromatic numbers of the composition of two graphs[J]. Journal of

Jilin University: Science Edition, 2011, 49(2): 207-212.
{6} HOR\v{N}\'{A}K M, SOT\'{A}K R. Observability of complete

multipartite graphs with equipotent parts[J]. Ars Combinatoria,

1995, 41: 289-301.
{7} \v{C}ERN\'{Y} J, HOR\v{N}\'{A}K M, SOT\'{A}K R. Observability of a

graph[J]. Math Slovaca, 1996, 46(1): 21-31.

Relative Articles

Supplements(0)

Cited By

Proportional views