Vertex-distinguishing proper edge coloring of composition of complete graph and star
-
摘要: 首先, 给出了完全图~$K_{p}$~和星~$S_{q}$~的合成的点可区别正常边色数的一个上界:~当~$p\geq2$,~$q\geq4$~时, 上界是~$pq+1$. 再利用正多边形的对称性以及组合分析的方法来构造染色, 分别得到了当$~p=2,~ q\geq4$; $p\geq3,~ q=4$;~$p$~是偶数且~$p\geq4,~ q=5$; $pq$~是奇数 且~$p\geq3,~ q\geq5$时,~完全图~$K_{p}$~和星~$S_{q}$~的合成的点可区别正常边色数.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$.
-
[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 edgecolorings of graphs[J]. J Graph Theory, 2003, 42(2): 95-109.{3} BAZGAN C, HARKAT-BENHAMDINE A, LI H, et al. On thevertex-distinguishing proper edge colorings of graphs[J]. J CombinTheory, 1999, 75(2): 288-301.{4} BURRIS A C, SCHELP R H. Vertex-distinguishing properedge-colorings[J]. J Graph Theory, 1997, 26(2): 73-82.{5} CHEN X N, GAO Y P. Vertex-distinguishing proper edge-coloringchromatic numbers of the composition of two graphs[J]. Journal ofJilin University: Science Edition, 2011, 49(2): 207-212.{6} HOR\v{N}\'{A}K M, SOT\'{A}K R. Observability of completemultipartite 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 agraph[J]. Math Slovaca, 1996, 46(1): 21-31. -
点击查看大图
计量
- 文章访问数: 1514
- HTML全文浏览量: 23
- PDF下载量: 1783
- 被引次数: 0
下载: