您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (04): 63-66.doi: 10.6040/j.issn.1671-9352.0.2014.327

• 论文 • 上一篇    下一篇

若干图的倍图的邻点可区别边(全)染色

何雪, 田双亮   

  1. 西北民族大学数学与计算机科学学院, 甘肃 兰州 730030
  • 收稿日期:2014-07-15 修回日期:2015-03-05 出版日期:2015-04-20 发布日期:2015-04-17
  • 通讯作者: 田双亮(1965-),男,硕士,教授,研究方向为图论及组合优化.E-mail:sl_tian@163.com E-mail:sl_tian@163.com
  • 作者简介:何雪(1988-),女,硕士,研究方向为图论与组合优化.E-mail:hexuebeautiful@163.com
  • 基金资助:
    西北民族大学研究生科研创新项目(ycx14146);西北民族大学科研创新团队计划资助

Adjacent vertex-distinguishing edge/total colorings of double graph of some graphs

HE Xue, TIAN Shuang-liang   

  1. School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, Gansu, China
  • Received:2014-07-15 Revised:2015-03-05 Online:2015-04-20 Published:2015-04-17

PDF (PC)

1029

摘要： 设G是具有顶点集V(G)和边集E(G)的简单图.如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色.如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色.图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ'as(G)(或χat(G)).给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值.

关键词: 邻点可区别全染色, 倍图, 邻点可区别边染色

Abstract: Let G be a simple graph with vertex set V(G) and edge set E(G). An edge-coloring σ of G is called an adjacent vertex distinguishing edge-coloring of G if Cσ(u)≠Cσ(v) for any uv∈E(G), where Cσ(u) denotes the set of colors of edges incident with u. A total-coloring σ of G is called an adjacent vertex distinguishing total-coloring of G if Sσ(u)≠Sσ(v) for any uv∈E(G), where Sσ(u) denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex-distinguishing edge-coloring (resp. total-coloring) of G is called adjacent vertex-distinguishing edge (resp. total) chromatic number, and denoted by χ'as(G) (resp. χat(G)). The upper bounds for these parameters of the double graph D(G) of graph G are given in this paper. Specifically, the exact value of these parameters for the double graph of complete graphs and trees are determined.

Key words: double graph, adjacent vertex-distinguishing edge coloring, adjacent vertex-distinguishing total coloring

中图分类号: 

  • O157.5
[1] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15:623-626.
[2] 张忠辅, 陈祥恩, 李敬文,等. 关于图的邻点可区别全染色[J]. 中国科学:A辑, 2005, 48(3):289-299. ZHANG Zhongfu, CHEN Xiang'en, LI Jingwen, et al. On adjacent-vertex-distinguishing total coloring of graphs[J]. Science in China: Ser. A, 2005, 48(3):289-299.
[3] 张忠辅, 仇鹏翔, 张东翰,等. 图的倍图与补倍图[J]. 数学进展, 2008, 37(3):303-310. ZHANG Zhongfu, QIU Pengxiang, ZHANG Donghan, et al. The double graph and the complement double graph of a graph[J]. Advances in Mathematics, 2008, 37(3):303-310.
[4] BALISTER P N, GYÖRI E, LEHEL J, et al. Adjacent vertex distinguishing edge-colorings[J]. SIAM J. Discrete Math, 2007, 21(1):237-250.
[5] TIAN Shuangliang, CHEN Ping, SHAO Yabin, et al. Adjacent vertex distinguishing edge-colorings and total-colorings of the cartesian product of graphs[J]. Control and Optimization, 2014, 4(1):49-58.
[6] CHEN Xiang'en, ZHANG Zhongfu. Adjacent vertex distinguishing total chromatic number of Pm×Kn[J]. Journal of Mathematical Research and Exposition, 2006, 26(3):489-494.
[7] BARIL J-L, KHEDDOUCI H, TOGNI O. Adjacent vertex distinguishing edge-colorings of meshes and hypercubes[J]. Australasian Journal of Combinatorics, 2006, 35:89-102.
[8] CHEN Meirun, GUO Xiaofeng. Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes[J]. Information Processing Letters, 2009, 109:599-602.
[9] 田双亮, 陈萍. 两类积图的邻点可区别全染色[J]. 数学研究与评论, 2007, 27(4):733-737. TIAN Shuangliang, CHEN Ping. On the adjacent vertex-distinguishing total coloring of two classes of product graph[J]. Journal of Mathematical Research and Exposition, 2007, 27(4):733-737.
[10] 田京京, 杨立夫, 王树勋,等. 扇的倍图的邻点可区别边色数[J]. 数学的实践与认识, 2008, 38(15):221-224. TIAN Jingjing, YANG Lifu, WANG Shuxun, et al. The chromatic number of adjacent-strong edge coloring of the double graph D(Fm)[J]. Mathematics in Practice and Theory, 2008, 38(15):221-224.
[11] 苏旺辉, 刘永平, 谢继国,等. 完全图的倍图的邻点可区别全染色[J]. 兰州理工大学学报, 2008, 34(3):166-167. SU Wanghui, LIU Yongping, XIE Jiguo, et al. Distinguishable total coloring of adjacent vertex of doubled complete graphs[J]. Journal of Lanzhou University of Technology, 2008, 34(3):166-167.
[12] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: American Elsevier, 1976.
[13] YAP H P. Total Coloring of graph[M]. New York: Springer Verlag, 1996.
[1] 李敬文, 贾西贝, 董威, 李小慧, 闫光辉. 图的邻点可区别全染色算法[J]. 山东大学学报（理学版）, 2015, 50(02): 14-21.
[2] 张芳红1, 王治文2, 陈祥恩1*，姚兵1. K5∨Kt邻点可区别全色数[J]. J4, 2012, 47(12): 37-40.
[3] 李泽鹏1,王治文2, 陈祥恩1*. 平面图的邻点可区别全染色[J]. J4, 2011, 46(4): 4-8.
[4] 文飞1,王治文2, 王鸿杰3, 包世堂4, 李沐春1*,张忠辅1. 若干补倍图的点可区别全染色[J]. J4, 2011, 46(2): 45-50.
[5] 程辉,王志勇. 图的邻点强可区别的EI-全染色[J]. J4, 2010, 45(6): 18-22.
[6] 朱恩强1,王治文2,张忠辅1. 若干倍图的Smarandachely邻点边染色[J]. J4, 2009, 44(12): 25-29.
[7] 田双亮 . 若干广义Petersen图的邻点可区别全染色[J]. J4, 2008, 43(9): 42-44 .
[8] 程 辉,姚 兵,张忠辅, . 联图 Ws∨Km,n的邻点可区别全色数[J]. J4, 2007, 42(6): 81-86 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发