围长至少为6的平面图的L(p,q)-标号

J4 ›› 2011, Vol. 46 ›› Issue (4): 9-16.

围长至少为6的平面图的L(p,q)-标号

朱海洋¹,吕新忠²，刘海洋²,盛景军¹,杭丹³

1.徐州空军学院后勤指挥系, 江苏徐州 221000; 2.浙江师范大学数理与信息工程学院，浙江金华 321004;
3.徐州空军学院基础部, 江苏徐州 221000

收稿日期:2010-04-06 发布日期:2011-04-21
作者简介:朱海洋(1979- ),助教,硕士,主要从事运筹学,图论及其应用方面的研究. Email: tulunzhuhaiyang7@126.com
基金资助:
国家自然科学基金资助项目(10971198)

The L(p,q)-labeling of planar graphs with girth g(G)≥6

ZHU Hai-yang¹, LVXin-zhong², SHENG Jing-jun¹, HANG Dan³

1. Department of Logistics Command, Xuzhou Air Force College, Xuzhou 221000, Jiangsu, China;
2. College of Mathematics, Physics and Information Engineering Zhejiang Normal University, Jinhua 321004, Zhejiang, China;
3. Department of Basic Courses, Xuzhou Air Force College, Xuzhou 221000, Jiangsu, China

Received:2010-04-06 Published:2011-04-21

摘要/Abstract

摘要：

令λ_p,q(G)为图G的L(p,q)-标号数,其中p和q是正整数且p≥q。证明了若G是围长g(G)≥6的平面图,则λ_p,q(G)≤(2q-1)Δ(G)+4p+6q-5;若G是围长g(G)≥6且Δ(G)≠5的平面图,则λ_p,q(G)≤(2q-1)Δ(G)+10p-2q-4。这一结果暗含着对于g(G)≥6且Δ(G)≠5的平面图G,Wegner的猜想成立。

关键词: 平面图;围长;L(p,q)-标号;L(p,q)-标号数

Abstract:

Let p and q be two positive integers with p≥q, and let λp,q(G) be the L(p,q)-labeling number of a planar graph G. It is proved that λ_p,q(G)≤(2q-1)Δ(G)+4p+6q-5 if G is a planar graphs with girth g(G)≥6, and that λ_p,q(G)≤(2q-1)Δ(G)+10p-2q-4 if G is a planar graphs with girth g(G)≥6 and Δ(G)≠5, which implies that Wegner’s conjecture holds for a planar graph G with girth g(G)≥6 and Δ(G)≠5.

Key words: planar graph; girth; L(p,q)-labeling; L(p,q)-labeling number

朱海洋1,吕新忠2，刘海洋2,盛景军1,杭丹3. 围长至少为6的平面图的L(p,q)-标号[J]. J4, 2011, 46(4): 9-16.

ZHU Hai-yang1, L Xin-zhong2, SHENG Jing-jun1, HANG Dan3 . The L(p,q)-labeling of planar graphs with girth g(G)≥6[J]. J4, 2011, 46(4): 9-16.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed