点面图的基尔霍夫指标

Kirchhoff Index of Vertex-Face Graphs

图中任意2个顶点之间的电阻距离定义为将图中的每条边用单位电阻代替后所得到的电网络中这2个节点之间的等效电阻.图的基尔霍夫指标定义为图中所有顶点对之间的电阻距离之和.设G是嵌入在可定向曲面上的具有n个顶点的三角化图,在图G的每个面中插入一个新的顶点并将该点和其所在面的边界上的3个顶点之间连边,所得的图称为图G的点面图,记作K(G).本文给出了图G的点面图K(G)的基尔霍夫指标计算公式.所得结果表明,K(G)的基尔霍夫指标可以由图G的顶点数、面数以及基尔霍夫指标等参数表示.

The resistance distance between any two vertices in a graph is defined as the effective resistance between them in the electrical network constructed from the graph by replacing each edge with a unit resistor. The Kirchhoff index of a graph is defined as the sum of resistance distances between all pairs of vertices. Let G be a triangulation graph with n vertices embedded on an orientable surface. The vertex-face graph of G , denoted by K(G), is the graph obtained from G by first inserting a new vertex to each face of G and then adding edges between the newly inserted vertex to every vertex of the corresponding face. In this paper, formula for the Kirchhoff index of K(G) of graph G is obtained. It turns out that the Kirchhoff index of K(G) can be expressed in terms of parameters of G , such as the number of vertices, the number of faces, and the Kirchhoff of G .