Please wait a minute...
浙江大学学报(理学版)  2016, Vol. 43 Issue (6): 668-671    DOI: 10.3785/j.issn.1008-9497.2016.06.007
数学与计算机科学     
关于边-多重路替换图的1,2,3-猜想和1,2-猜想
吕大梅, 林文松
1. 南通大学 理学院, 江苏 南通 226007;
2. 东南大学 数学系, 江苏 南京 211189
1,2,3-conjecture and 1,2-conjecture for the edge-multiplicity-paths-replacements
LYU Damei, LIN Wensong
1. School of Science, Nantong University, Nantong 226007, Jiangsu Province, China;
2. Department of Mathematics, Southeast University, Nanjing 211189, China
 全文: PDF(262 KB)  
摘要: fEG)→Z+是图G的一个边标号,若对G的每个顶点v,cv)=fe)定义一个正常的点着色,则称f是邻点可区别的边标号. 设gVG)∪EG)→Z+是图G的一个全标号,若对G的每个顶点v,cv)=gv)+ge)定义一个正常的点着色,则称g是邻点可区别的全标号.对这2个概念的2个猜想分别是1,2,3-猜想(每一个连通图GK2均有用1,2,3进行标号的邻点可区别的边标号)和1,2-猜想(每一个简单图均有用1,2进行标号的邻点可区别的全标号).主要证明了1,2,3-猜想和1,2-猜想对每一个图的边-多重路替换图都是成立的.
关键词: 1,2,3-猜想1,2-猜想边-路替换图    
Abstract: Let f:E(G)→Z+ be an edge-weighting(labeing) of a graph G. For each vV(G), if c(v)=f(e) yields a proper coloring of the graph,then f is defined as a neighbour-distinguishing edge labeling of G. Let g:V(G)∪E(G)→Z+ be a total-weighting(labeing) of a graph G. For each vV(G), if c(v)=g(v)+g(e) yields a proper coloring of the graph,then g is defined as a neighbour-distinguishing total labeling of G. For them, there exist two conjectures such as 1,2,3-conjecture(i.e., every connected graph GK2 has a neighbour-distinguishing edge labeling in {1,2,3}) and 1,2-conjecture(i.e., every simple graph has a neighbour-distinguishing total labeling in {1,2}). This paper shows that 1,2,3-conjecture and 1,2-conjecture hold for the edge-multiplicity-paths-replacements for any graph.
Key words: 1,2,3-conjecture    1,2-conjecture    edge-path-replacement
收稿日期: 2015-11-03 出版日期: 2017-03-07
CLC:  O157.5  
作者简介: 吕大梅(1976-), ORCID:http://orcid.org/0000-0002-9607-1131, female, master, lecturer, the field of interest is graph theory with applications, E-mail:damei@ntu.edu.cn.
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  
吕大梅
林文松

引用本文:

吕大梅, 林文松. 关于边-多重路替换图的1,2,3-猜想和1,2-猜想[J]. 浙江大学学报(理学版), 2016, 43(6): 668-671.

LYU Damei, LIN Wensong. 1,2,3-conjecture and 1,2-conjecture for the edge-multiplicity-paths-replacements. Journal of ZheJIang University(Science Edition), 2016, 43(6): 668-671.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2016.06.007        https://www.zjujournals.com/sci/CN/Y2016/V43/I6/668

[1] ADDARIO-BERRY L, DALAL K, REED B A. Degree constrained subgraphs[J]. Discrete Applied Mathematics, 2008,156(7):1168-1174.
[2] KARONSKI M, LUCZAK T, THOMASON A. Edge weights and vertex colours[J]. Journal of Combinatorial Theory:Ser B,2004,91(1):151-157.
[3] PRZYBYLO J, WOZNIAK M. 1, 2 Conjecture[J/OL]. Matematyka Dyskretna, 2007. www.ii.uj.edu.pl/documents/12980385/35169997/MD24.pdf.
[4] BACA M, JENDROL S, MILLER M, et al. On irregular total labellings[J]. Discrete Math, 2007,307:1378-1388.
[5] CHARTRAND G, JACOBSON M S, LEHEL J, et al. Irregular networks[C]//The 250th Anniversary Conference on Graph Theory. Winnipeg:Utilitas Mathematica Publishing lnc., 1986.
[6] WHITTLESEY M A,GEORGES J P, MAURO D W. On the λ-number of Qn and related graphs[J]. Discrete Math,1995(8):449-506.
[7] LYU D M. L(2,1)-labelings of the edge-path-replacement of a graph[J]. Comb Optim, 2013,26:385-392.
[8] LYU D M. L(d,1)-labelings of the edge-path-replacement of a graph[J]. Comb Optim, 2013,26:819-831.
[9] KARST N, OEHRLEIN J, TROXELL D S, et al. L(d,1)-labelings of the edge-path-replacement by factorization of graphs[J]. Comb Optim,2015,30:34-41.
[1] 杜娟, 吕大梅, 张科. Cartesian积的局部边-路替换图的L(2,1)-标号[J]. 浙江大学学报(理学版), 2016, 43(6): 679-681.