一类稀疏图的邻和可区别边色数

doi:10.6040/j.issn.1671-9352.0.2016.326

山东大学学报（理学版） ›› 2017, Vol. 52 ›› Issue (8): 94-99.doi: 10.6040/j.issn.1671-9352.0.2016.326

一类稀疏图的邻和可区别边色数

潘文华¹,徐常青^1,2*

1.河北工业大学理学院, 天津 300401;2.河北省大数据计算重点实验室, 天津 300401

收稿日期:2016-07-11 出版日期:2017-08-20 发布日期:2017-08-03
通讯作者: 徐常青(1970— ), 女, 教授, 硕士生导师, 研究方向为图论. E-mail:chqxu@hebut.edu.cn E-mail:whpkxkl@163.com
作者简介:潘文华(1989— ), 女, 硕士研究生, 研究方向为图论. E-mail:whpkxkl@163.com
基金资助:
国家自然科学基金资助项目(11671232,11301134,11301135);河北省自然科学基金资助项目(A2015202301);河北省高等学校科学技术研究重点项目(ZD2015106)

Neighbor sum distinguishing index of a kind of sparse graphs

PAN Wen-hua¹, XU Chang-qing^1,2*

1. School of Science, Hebei University of Technology, Tianjin 300401, China;
2. Hebei Province Key Laboratory of Big Data Calculation, Tianjin 300401, China

Received:2016-07-11 Online:2017-08-20 Published:2017-08-03

摘要/Abstract

摘要： 设φ为图G的正常k-边染色。对任意v∈V(G),令f_φ(v)=∑_uv∈E(G)φ(uv)。若对每条边uv∈E(G)都有f_φ(u)≠f_φ(v),则称φ为图G的k-邻和可区别边染色。图G存在k-邻和可区别边染色的k的最小值称为G的邻和可区别边色数,记作 χ'Σ(G)。确定了一类稀疏图的邻和可区别边色数,得到:若图G不含孤立边,Δ≥6且mad(G)≤5/2,则 χ'Σ(G)=Δ当且仅当G不含相邻最大度点。

关键词: 邻和可区别边染色, 稀疏图, 最大平均度

Abstract: Let φ be a proper k-edge coloring of G. For each vertex v∈V(G), set f_φ(v)=∑_uv∈E(G)φ(uv). φ is called a k-neighbor sum distinguishing edge coloring of G if f_φ(u)≠f_φ(v) for each edge uv∈E(G). The smallest k such that G has a k-neighbor sum distinguishing edge coloring is called the neighbor sum distinguishing index, denoted by χ'_Σ(G). The neighbor sum distinguishing index of a kind of sparse graphs is determined. It is proved that if G is a graph without isolated edges, Δ≥6 and mad(G)≤5/2, then χ'_Σ(G)=Δ if and only if G has no adjacent vertices of maximum degree.

Key words: maximum average degree, neighbor sum distinguishing edge coloring, sparse graph

中图分类号:

O157

潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报（理学版）, 2017, 52(8): 94-99.

PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.

参考文献

[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: North-Holland, 1976.
[2] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Appl Math Lett, 2002, 15(5):623-626.
[3] WANG Weifan, WANG Yiqiao. Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree[J]. J Comb Optim, 2010, 19(4):471-485.
[4] WANG Yi, CHENG Jian, LUO Rong, et al. Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs[J]. J Comb Optim, 2016, 31(2):874-880.
[5] WANG Weifan, WANG Yiqiao. Adjacent vertex-distinguishing edge colorings of K₄-minor free graphs[J]. Appl Math Lett, 2011, 24(12):2034-2037.
[6] HUANG Danjun, MIAO Zhengke, WANG Weifan. Adjacent vertex distinguishing indices of planar graphs without 3-cycles[J]. Discrete Math, 2015, 338(3):139-148.
[7] FLANDRIN E, MARCZYK A, PRZYBYŁO J, et al. Neighbor sum distinguishing index[J]. Graphs and Combin, 2013, 29(5):1329-1336.
[8] WANG Guanghui, YAN Guiying. An improved upper bound for the neighbor sum disthinguishing index of graphs[J]. Discrete Appl Math, 2014, 175:126-128.
[9] DONG Aijun, WANG Guanghui. Neighbor sum distinguishing coloring of some graphs[J]. Discrete Math Algorithms Appl, 2012, 4(4):1250047(12 pages).
[10] WANG Guanghui, CHEN Zhumin, WANG Jihui. Neighbor sum distinguishing index of planar graphs[J]. Discrete Math, 2014, 334:70-73.
[11] DONG Aijun, WANG Guanghui, ZHANG Jianghua. Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree[J]. Discrete Appl Math, 2014, 166:84-90.
[12] GAO Yuping, WANG Guanghui, WU Jianliang. Neighbor sum distinguishing edge colorings of graphs with small maximum average degree[J]. Bull Malays Math Sci Soc, 2016, 39(Supplement 1):247-256.
[13] YU Xiaowei, QU Cunquan, WANG Guanghui, et al. Adjacent vertex distinguishing colorings by sum of sparse graphs[J]. Discrete Math, 2016, 339(1):62-71.
[14] LI Hualong, DING Laihao, LIU Bingqiang, et al. Neighbor sum distinguishing total colorings of planar graphs[J]. J Comb Optim, 2015, 30(3):675-688.
[15] Alon N. Combinatorial Nullstellensatz[J]. Combin Probab Comput, 1999, 8(1/2):7-29.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

一类稀疏图的邻和可区别边色数

Neighbor sum distinguishing index of a kind of sparse graphs

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

多维度评价

本文评价

推荐阅读 0

[1]	张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10.
[2]	姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2015, 50(02): 9-13.
[3]	雒金梅,左连翠*. 关于图的L(2,1)-标号的岛序列[J]. J4, 2011, 46(6): 49-52.
[4]	张欣1,徐兰2，刘桂真1. 稀疏图的k-森林染色[J]. J4, 2011, 46(4): 1-3.