L(p,q)-labeling of sparse graphs
L(p,q)-labeling of sparse graphs
复制标题
DOI：
10.1007/s10878-012-9507-6
复制
发表时间：
2013-05
影响因子：
1
通讯作者：
C. Charpentier;Mickaël Montassier;A. Raspaud
中科院分区：
文献类型：
--
作者：
C. Charpentier;Mickaël Montassier;A. Raspaud
设q为正整数。用跨度标记图G的L（p，q）-是用0到s之间的整数标记其顶点，使得G的相邻顶点使用至少间隔p的颜色标记，并且具有共同邻居的顶点使用至少间隔q的颜色标记。记λp，q（G）为使得G有L（p，q）-标号的最小整数k，图G的最大平均度记为，是它的子图（即）的平均度中的最大值.我们考虑图Gwith，3和。本文证明了每个具有最大平均度和最大度Δ的图G有：λp，q（G）≤（2 q −1）Δ+6p+10q−8，如果p ≥ 2 q.λp，q（G）≤（2 q − 1）Δ+4p+14q−9，如果2 q> p. λ p，q（G）≤（2 q − 1）Δ+4p+6q−5，如果m <3.λp，q（G）≤（2 q − 1）Δ +4p +4q−4，如果p，q（G）≤（2 q −1）Δ+4p+4q−4.我们还给出了p，q或Δ的某些具体值的精确界.通过这种方式，我们改进了Lih和Wang（SIAM J. Discrete Math.17（2）：264-275，2003）的结果。
Letpandqbe positive integers. AnL(p,q)-labeling of a graphGwith a spansis a labeling of its vertices by integers between 0 andssuch that adjacent vertices ofGare labeled using colors at leastpapart, and vertices having a common neighbor are labeled using colors at leastqapart. We denote byλp,q(G) the least integerksuch thatGhas anL(p,q)-labeling with spank.The maximum average degree of a graphG, denoted by, is the maximum among the average degrees of its subgraphs (i.e.). We consider graphsGwith, 3 and. These sets of graphs contain planar graphs with girth 5, 6 and 7 respectively.We prove in this paper that every graphGwith maximum average degreemand maximum degreeΔhas:λp,q(G)≤(2q−1)Δ+6p+10q−8 ifandp≥2q.λp,q(G)≤(2q−1)Δ+4p+14q−9 ifand 2q>p.λp,q(G)≤(2q−1)Δ+4p+6q−5 ifm<3.λp,q(G)≤(2q−1)Δ+4p+4q−4 if.We give also some refined bounds for specific values ofp,q, orΔ. By the way we improve results of Lih and Wang (SIAM J. Discrete Math. 17(2):264–275, 2003).