-
本文所考虑的图都是有限、无向的简单图.设图G是一个化学分子结构图模型，即一个具有n个顶点的连通图.图G的Hosoya指标和Merrifield-Simmons指标分别定义为图的包括空边集在内的对集(独立边集)总数和包括空点集在内的点独立集总数，图G的这两个指标分别记为z(G)和i(G).图的Hosoya指标的概念由文献[1]引入.文献[2]首先提出了图的Fibonacci数的概念，即Merrifield-Simmons指标，Fn是第n个Fibonacci数，满足F0=0，F1=1，Fn+1=Fn+Fn-1.文献[3]给出了图的Merrifield-Simmons指标和Hosoya指标的计算公式.这两种指标均是研究物质分子结构与物理和化学性质之间的拓扑参数，将其应用到化学分子图研究中，其中一个重要方向是研究给定图类的Hosoya指标和Merrifield-Simmons指标的极大或极小图.关于Hosoya指标或Merrifield-Simmons指标，已经得到了很多图类的极图[4-12].
用NG(v)表示图G中点v的邻点集，且NG[v]={v}∪NG(v)，并用Pn，Sn和Kn分别表示n点路、n点星和n点完全图，其它没有定义的图论的概念和术语可参考文献[13].
用Kn1，n2，…，nk表示各部顶点数分别是n1，n2，…，nk的n阶完全k部图集合.本文证明了图
${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 在Kn1，n2，…，nk中具有最大的Merrifield-Simmons指标和最小的Hosoya指标，确定了图${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 的Merrifield-Simmons指标值，并证明了图${{K}_{\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, \cdots, q+1}_{r个}}}$ 在Kn1，n2，…，nk中具有最小的Merrifield-Simmons指标和最大的Hosoya指标，其中n=kq+r，0≤r < k.引理1[3] 设G是一个图，v是G的一个顶点，w~v表示G中和顶点v相邻的顶点，则有
注1 根据引理1，对于两连通图G1和G2，若G1是G2的去点或去边真子图，则有
引理2[3] 设G是一个图，v是G的一个顶点，则有
引理3[3]
$i\left(P_{n}\right)=F_{n+2}, i\left(K_{n}\right)=n+1, i\left(S_{n}\right)=2^{n-1}+1$ .引理4[3]
$z\left(P_{n}\right)=F_{n+1}, z\left(S_{n}\right)=n$ .引理5[3] 若G1，G2，…，Gt是图G的连通分支，则有：
(ⅰ)
$i(G)=\prod\limits_{k=1}^{t} i\left(G_{k}\right)$ ；(ⅱ)
$z(G)=\prod\limits_{k=1}^{t} z\left(G_{k}\right)$ .令z(n1，n2，…，nk)和i(n1，n2，…，nk)分别表示n阶完全k部图Kn1，n2，…，nk的Hosoya指标和Merrifield-Simmons指标.
定理1 设G∈Kn1，n2，…，nk，则有
$z(G)\ge z(\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1)$ ，等式成立当且仅当$G\cong {{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ .证 先说明一下Kn1，n2，…，nk中各部顶点数相差最大数的含义.如k=4，n=9时的Hosoya指标有z(2，2，2，3)，z(1，2，3，3)，z(1，2，2，4)，z(1，1，3，4)，z(1，1，2，5)和z(1，1，1，6)，它们从大到小排列，其中各部顶点相差最大数分别是1，2，3，3，4和5，z(1，1，1，6)是各部顶点相差最大数最大的.一般地，显然图
${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 是在Kn1，n2，…，nk中各部顶点数相差最大数最大的.下面证明${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 在Kn1，n2，…，nk中的Hosoya指标最小，故只需证明在Kn1，n2，…，nk中各部顶点数相差最大数越大Hosoya指标越小.假设存在两个独立集点数n1，n2满足n2>n1.
当k=2时，对kn1-1，n2+1和kn1，n2运用引理1，有：
由引理1及引理4，有
当k≥3时，对Kn1，n2，n3，…，nk和Kn1-1，n2+1，n3，…，nk运用引理1，有：
最后一个不等式成立是因为Kn2-n1+2，n3，…，nk是K1，n2-n1+1，n3，…，nk去掉点数1和n2-n1+1两部之间所有的边所得到的真子图.根据注1，有
又因为
结论成立.
定理2 设G∈Kn1，n2，…，nk，则有
$z(G)\le z(\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, q+1, \cdots, q+1}_{r个})$ ，等式成立当且仅当$G\cong {{K}_{(\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, q+1, \cdots, q+1}_{r个})}}$ ，其中n=kq+r，0≤r < k.证 显然图
${{K}_{(\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, q+1, \cdots, q+1}_{r个})}}$ 是Kn1，n2，…，nk中各部顶点数最多相差1的n阶完全k部图.仿定理1可证明此定理.定理3 设G∈Kn1，n2，…，nk，则有
$i(G)\le i(\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1)$ ，等式成立当且仅当$G\cong {{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ ，并且$i(\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1)={{2}^{n-k+1}}+k-1$ .证 显然图
${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 是在Kn1，n2，…，nk中各部顶点数相差最大数最大的.下面证明${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 在Kn1，n2，…，nk中的Merrifield-Simmons指标最大，故只需证明在Kn1，n2，…，nk中各部顶点数相差最大数越大Merrifield-Simmons指标越大.不失一般性，假设存在两个独立集点数n1，n2，满足n2>n1.
对Kn1-1，n2+1，n3，…，nk和Kn1，n2，n3，…，nk运用引理2及引理3、引理5，有：
所以
下面计算图
${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ 的Merrifield-Simmons指标.运用引理3，有结论成立.
同理可以得到下面定理：
定理4 设G∈Kn1，n2，…，nk，则有
$i(G)\le i(\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, q+1, \cdots, q+1}_{r个})$ ，等式成立当且仅当$G\cong {{K}_{(\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, q+1, \cdots, q+1}_{r个})}}$ ，其中n=kq+r，0≤r < k.
Extremal Complete K-Partite Graphs with Respect to Hosoya Index and Merrifield-Simmons Index
-
摘要: 图的Hosoya指标和Merrifield-Simmons指标是化学图论中两个重要的拓扑指标.考虑点数为n的完全K部图集合Kn1，n2，…，nk，证明了在图集Kn1，n2，…，nk中${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$具有最小的Hosoya指标和最大的Merrifield-Simmons指标，并且图$ {{K}_{\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, \cdots, q+1}_{r个}}}$在Kn1，n2，…，nk中具有最小的Merrifield-Simmons指标和最大的Hosoya指标，其中n=kq+r，0 ≤ r < k.
-
关键词:
- Hosoya指标 /
- Merrifield-Simmons指标 /
- 完全K部图
Abstract: Hosoya index and Merrifield-Simmons index are the two valuable topological indices in chemical graph theory. We consider the Hosoya indices and Merrifield-Simmons indices of graphs in Kn1, n2, …, nk, where Kn1, n2, …, nk denotes the set of graphs with order n and complete K-partite. In this paper we prove that in Kn1, n2, …, nk, the ${{K}_{\underbrace{1, 1, \cdots, 1}_{k-1个}, n-k+1}}$ has minimal Hosoya index and maximal Merrifield-Simmons index, and ${{K}_{\underbrace{q, q, \cdots, q}_{k-r个}, \underbrace{q+1, \cdots, q+1}_{r个}}}$(where n=kq+r, 0 ≤ r < k) has maximal Hosoya index and minimal Merrifield-Simmons index.-
Key words:
- Hosoya index /
- Merrifield-Simmons index /
- complete K-partite graph .
-
-
[1] HOSOYA H. Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons[J]. Bull Chem Soc Jpn, 1971, 44(9): 2332-2339. doi: 10.1246/bcsj.44.2332 [2] MERRIFIELD R E, SIMMONS H E. Topological Methods in Chemistry[M]. New York: Wiley, 1989. [3] GUTMAN I, POLANSKY O E. Mathematical Concepts in Organic Chemistry[M]. Berlin: Springer, 1986. [4] 陈兰.单圈图Merrifield-Simmons指标的第四大值[J].西南师范大学学报(自然科学版), 2009, 34(3): 24-27. doi: http://xbgjxt.swu.edu.cn/jsuns/jscnuhhse/ch/reader/view_abstract.aspx?file_no=xnsfdxxb200903007&flag=1 [5] 陈兰.具有第四大和第五大Merrifield-Simmons指标的n阶单圈图[J].青海师范大学学报(自然科学版), 2010, 26(1): 9-11. doi: 10.3969/j.issn.1001-7542.2010.01.003 [6] 田双亮, 田文文, 王倩, 等.多元素链的Merrifield-Simmons指标和Hosoya指标[J].山西大学学报(自然科学版), 2014, 37(1): 48-52. doi: http://d.old.wanfangdata.com.cn/Periodical/sxdxxb201401008 [7] 赵晓翠, 田双亮, 田文文.几类图的Merrifield-Simmons指标及扇和轮的Hosoya指标[J].山东理工大学学报(自然科学版), 2015, 29(1): 27-31. doi: 10.3969/j.issn.1672-6197.2015.01.007 [8] 刘睿琳, 田双亮, 田文文.五边形链的Merrifield-Simmons指标[J].西北民族大学学报(自然科学版), 2016, 37(2): 1-5. doi: 10.3969/j.issn.1009-2102.2016.02.001 [9] 许克祥.关于Hosoya指标和Merrifield-Simmons指标的k色极图[J].厦门大学学报(自然科学版), 2010, 49(3): 312-315. doi: http://d.old.wanfangdata.com.cn/Periodical/xmdxxb201003004 [10] 黄丽娜, 李沐春, 刘海忠.图的邻点可区别V-全色数的一个上界[J].西南大学学报(自然科学版), 2017, 39(12): 81-85. [11] 王文杰, 黄丽娜, 李沐春. T-型六角系统的点可区别边染色[J].西南大学学报(自然科学版), 2018, 40(10): 77-82. doi: http://d.old.wanfangdata.com.cn/Periodical/xnnydxxb201810013 [12] 宋海洋, 王淑玲, 刘嫚, 等.平面图的单射染色[J].西南师范大学学报(自然科学版), 2017, 42(4): 7-13. doi: http://xbgjxt.swu.edu.cn/jsuns/jscnuhhse/ch/reader/view_abstract.aspx?file_no=x201704002&flag=1 [13] BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: Macmillan Press, 1976. -
计量
- 文章访问数: 781
- HTML全文浏览数: 673
- PDF下载数: 84
- 施引文献: 0
下载: