关于Hosoya指标和Merrifield-Simmons指标的k色极图

Extremal k-Chromatic Graphs with Respect to Hosoya Index and Merrifield-Simmons Index

图的Hosoya指标定义为图中包含空边集在内的对集总数.图的Merrifield-Simmons指标定义为图中包含空点集在内的点独立集总数.考虑点数为n的k色连通图的集合Gn,k,证明了Tur n图Tn(k)是Gn,k中Hosoya指标最大且Merrifield-Simmons指标最小的图,还确定了k=2,3时Gn,k中Hosoya指标最小且Merrifield-Simmons指标最大的图.

The Hosoya index and the Merrifield-Simmons index of a graph are defined as the total number of the matchings including the empty edge set and the total number of the independent vertex sets including the empty vertex set,respectively.We consider the Hosoya indices and the Merrifield-Simmons indices of graphs in Gm,k,where Gm,k denotes the set of graphs with order n and chromatic number k.In this paper,we prove that in Gm,k the Turán graph Tn（k） has maximal Hosoya index and minimal Merrifield-Simmons index,and determine the graph from Gm,k for k=2,3 with minimal Hosoya index and maximal Merrifield-Simmons index.