极大外平面图的Wiener指标的上下界  

Sharp Bounds for Wiener Index of Maximal Outerplanar Graphs

作　　者：孙晓慧 安新慧[1] SUN Xiaohui;AN Xinhui(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830017

出　　处：《新疆大学学报（自然科学版）（中英文）》2023年第5期560-564,共5页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：国家自然科学基金“图中距离参数的研究”(11801487).

摘　　要：外平面图是具有平面嵌入的平面图,其中每个顶点位于外部区域的边界上.若通过添加边获得的图不是外平面图,则此时的外平面图是极大外平面图.图G的Wiener指标是所有顶点对之间距离的总和.证明了对于n个顶点的极大外平面图G,有W(K1_P_(n−1))≤W(G)≤W(P_(n)^(2)),其中K_(1)P_(n−1)是通过将一个点和路P_(n−1)的每个顶点相连得到的图,P_(n)^(2)是路的平方图.A graph is outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the boundary of its outer face.An outerplanar graph is maximal outerplanar if no edge can be added without losing outerplanarity.The Wiener index of a graph G is the sum of distances between all pairs of vertices of G.We show that for a maximal outerplanar graph G on n vertices,W(K1_P_(n−1))·W(G)·W(P_(n)^(2)),where K_(1)P_(n−1)is the graph obtained from joining a vertex to each vertex of P_(n−1)and P_(n)^(2) is the square of Pn.

关 键 词：极大外平面图 WIENER指标 极图 平方图 

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