王大勇,杨玉军

(烟台大学数学与信息科学学院,山东 烟台 264005)

1 引言与预备知识

(1)

后来, 人们进一步将顶点的度考虑进来, 定义了2种修正的基尔霍夫型指标. 一种是度和基尔霍夫指标[2], 记作Kf+(G), 定义为

(2)

其中di表示G中顶点i的度.另一种是度乘积基尔霍夫指标[3], 定义为

(3)

基尔霍夫指标不仅是图上的一个重要的不变量, 而且在化学上还是一个重要的分子结构描述符,在QSAR(定量结构活性关系)和QSPR(定量结构性质关系)中有着重要的应用. 因此, 图的基尔霍夫指标得到了广泛的研究. 基尔霍夫指标的研究主要集中于基尔霍夫指标的计算. 一方面, 对于一些特殊图类, 人们给出了这些图的基尔霍夫指标的精确的显式表达式. 另一方面, 对于一些通过在图上做一元或者二元运算得到的图, 如剖分图、三角化图以及合成图等[4-8], 人们给出了这些图的由原图中的参数表示的基尔霍夫指标计算公式, 从而使得这些图的基尔霍夫指标的计算得到了极大的简化. 在本文中, 我们将给出嵌入在定向曲面上的三角化图G的点面图K(G)的基尔霍夫指标的计算公式. 首先给出点面图的定义.

定义1 设图G是嵌入在定向表面Σ上的三角化图(即每个面都是三角形),顶点集合为V(G)={v1,v2,…,vn},边集合为E(G)={e1,e2,…,em}和面集合为F(G)={φ1,φ2,…,φf}.图G的点面图K(G)定义为

V(K(G))=V(G)∪F(G)

且K(G)的边集合为

V(φ),φ∈F(G)}.

由点面图的定义可以看出, 图G的点面图K(G)可以通过下面的方式得到: 在图G的每个面中插入一个新的顶点, 然后再将新的顶点与所在面的3个顶点连边……