平面图平方的最小度  

Minimum degree of the square of a planar graph

作　　者：王维凡[1] 罗晓芳 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004 [2]义乌工商管理学院,浙江义乌322000

出　　处：《浙江师范大学学报（自然科学版）》2007年第3期241-245,共5页Journal of Zhejiang Normal University:Natural Sciences

基　　金：国家自然科学基金资助项目(10471131)

摘　　要：设G是一个没有4-圈的平面图,G的平方图G2定义在V(G)上,使得2个点u和v在G2中是相邻的当且仅当它们在G中的距离为1或2.证明了:δ(G2)≤Δ(G)+33,并且当δ(G)≥4时有δ(G2)≤16.其中,δ(H)和Δ(H)分别表示图H的最小度和最大度.Let G be a planar graph without 4-cycles. The square G^2 of G is the graph defined on the vertex set V（ G） such that two vertices u and v are adjacent in G： if and only if they are at distance 1 or 2 in G. It was proved that δ （ G^2）≤ Δ （ G ） ＋ 33, δ（ G^2） ≤ 16 when δ （ G ） ≥4. Here δ （ H ） and Δ （ H ） denoted the minimum degree and the maximum degree of a graph H, respectively.

关 键 词：平面图 平方图 度 圈 

分 类 号：O157.5[理学—数学]