两类三圈图的拓扑指标.pdf

Master’s thesis
THE TOPOLOGICAL INDICES
OF two types TRICYCLIC
GRAPHS
By
Hua Wan
A thesis submitted to the Graduate department of Qinghai Normal University
in partial fulfillment of the requirement for the degree of
Master of Science
Qinghai Normal University
Xining, People’s Republic of China
March 2012
°c Copyright 2012
原创性声明
本人郑重声明:所呈交的学位论文,是本人在导师指导下,独
立进行研究所取得的成果。除文中已经注明引用的内容外,本论文
不包含任何其他个人或集体已经发表或撰写过的科研成果。对本论
文的研究作出重要贡献的个人和集体,均已在文中以明确方式标
明。本声明的法律责任由本人承担。
论文作者签名: 日期:
关于学位论文使用授权的声明
本人完全了解青海师范大学有关保留、使用学位论文的规定,
同意学校保留或向国家有关部门或机构送交论文的复印件和电子
版,允许论文被查阅和借阅;本人授权青海师范大学可以将本学位
论文全部或部分内容编入有关数据库进行检索,可以采用影印、缩
印或其他复制手段保存论文和汇编本学位论文。
(保密的论文在解密后应遵守此规定)
论文作者签名: 导师签名: 日期:
摘要
摘摘摘要要要
设G = (V, E)是一个简单连通图,V (E)和E(G)分别是G的顶点集和边集.
|V (E)| = n, |E(G)| = m分别表示G的顶点数和边数. 三圈图是指边数与顶
点数之差等于2的连通图. 若S ⊆ V (G),且S中的任意两个顶点都不相邻, 则
称S为图G的一个独立集. 图G的Merrifield-Simmons指标定义为图G的所有独立
集的数目之和,记为i(G). 用m(G, k)表示G的k−匹配数,则G的Hosoya指标定义
[n/P2]
为z(G) = m(G, k):图G的Wiener指标是指图G中所有顶点对之间的距离之
k=0
和,即
X
W (G) = dG(u, v),
{u,v}⊆G
其中dG(u, v)表示G中顶点u, v之间的距离.
Merrifield-Simmons指标,Hosoya指标和Wiener指标是化学图论中三个重要
的拓扑指标,在数学,化学上被广泛研究; 而Wiener指标被证实在定量结构―活
性/性质相关性(QSAR/QSPR)中是一个非常有用的量,并且, 在通讯网络的研究
中也广泛运用到Wiener指标.
本文主要研究了含有三个圈的三圈图的Merrifield-Simmons指标,Hosoya指
标以及Wiener指标. 首先,给出一些图的变换;然后,利用这些图的变换以及计
算公式, 刻画了含有三个圈的三圈图的最大,次小Hosoya指标, 最小Merrifield-
Simmons指标, 最小,次小Wiener指标,及相应图的特征;论文最后给出了含有四个
圈的三圈图关于Merrifield-Simmons指标,Hosoya指标和Wiener指标的部分结果.
关关关键键键词词词: Merrifield-Simmons指标, Hosoya指标, Wiener指标, 三圈图.
I
Abstract
Abstract
Let G = (V, E) be a simple connected graph with the vertex set V (G) and
the edge set E(G). V (G) = n and E(G) = m denote the number of edges and
vertices, respectively. A tricyclic graph is a connected graph with n vertices and
n + 2 edges.
Let S be a subset of the vertex set of G, if any two vertices in S are not
adjacent then S is a independent vertex set of G. The Merrifield-Simmons index
of the graph G, denoted by i(G), is the number of