华东师范大学学报(自然科学版) ›› 2013, Vol. 2013 ›› Issue (5): 136-143.

• 数学 • 上一篇    下一篇

完全图和星的合成的点可区别正常边染色

杨 芳1, 王治文2, 陈祥恩1, 马春燕1   

  1. 1. 西北师范大学~~数学与统计学院, 兰州 730070;
    2. 宁夏大学~~数学与计算机科学学院, 银川 750021
  • 收稿日期:2012-09-01 修回日期:2012-12-01 出版日期:2013-09-25 发布日期:2013-09-30

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

YANG Fang1, WANG Zhi-wen2, CHEN Xiang-en1, MA Chun-yan1   

  1. 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:2012-09-01 Revised:2012-12-01 Online:2013-09-25 Published:2013-09-30

PDF

1921

摘要： 首先,
给出了完全图~$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$.

Key words: composition, complete graph, star, vertex-distinguishing proper edge coloring, vertex-distinguishing proper edge chromatic number

中图分类号: