关于图与线图的距离指标关系问题研究

朱 娜盛兴平

（1.安徽理工大学 数学与大数据学院，安徽 淮南 232001；2.阜阳师范学院 数学与统计学院，安徽 阜阳 236037）

0 引言

本文中所有的图都是有限的,简单的,无向的.对于一个图G，分别用V（G）和E（G）表示它的顶点集和边集。G的一条途径是指一个有限非空序列W＝v0e1v1e2v2…ekvk（0≤i≤k），它的项交替地为顶点和边，ei的端点是vi-1和vi，称W是从v0到vk的一条途径，，v0和vk分别称为W的起点和终点。若途径W的边e1，e2，…，ek互不相同，则W称为迹。又若途径W的顶点v0，v1，…vk也不相同，则W称为路。路Pn=v0，v1，…vn表示顶点分别为v0，v1，…vn的路.如果迹的起点和终点相同，则称为闭迹。若一条闭迹的起点和内部顶点互不相同，则称它为圈。[1]一个长为n的圈记作Cn。如果V(H)U V(G)，E(H)U E(G)，并且ΦH是ΦG在E（H）上的限制，就称H是G的子图。假设V'是V的一个非空子集，以V'为顶点集，以两端点均在V'中的边的全体为边集所组成的子图，称为G的由V'导出的子图。

给定一个图G，它的线图L（G）满足：V（L（G））＝E（ G），e1e2∈E（ L（ G）），当且仅当e1与e2在G中有公共点。对于v∈V（G），记dG（v）是v在G中的度，简记为d（v）。用δ（GV）表示G的顶点的最小度。对于v，u∈V（G），dG（u，v）（或者用d（u，v）） 表示在G中u和v之间最短路的长度。对于e1e2∈E（G），定义dG（e1，e2）＝dL（G）（e1，e2）。W（G）指数是一个描述分子结构的不变量，是化学图论中最经典的分子拓扑指数之一，它可以用于设计具有理想性质的分子[2]。A.A.Dobrynin等人在2001年给出了树的W（G）指数[3].A.A.Dobrynin等人在2002年给出了W（G）指数关于六角形系统的结果[4]。近些年，很多人对图的W（G）指数和其线图的W（L（G））指数的关系非常感兴趣，尤其对于一个什么样的图满足W（G）＝W（L（G））做了很多研究。Nathann Cohen等人在2009年给出了对于每一个非负整数g0存在g＞g0，当图G的围长为g时，有很多图G满足W（G）＝W（L（G））[5]。罗宇等人在……