On extremal cacti with respect to the Szeged index
On extremal cacti with respect to the Szeged index
复制标题
DOI：
10.1016/j.amc.2017.03.036
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Shujing Wang
中科院分区：
文献类型：
--
作者：
Shujing Wang
图 G 的 Szeged 指数定义为 S z (G)=Σ e= u v∈ E n u (e) n v (e)，其中 n u (e) 和 n v (e) 分别是 G 中距离顶点 u 比距离 v 更近的顶点数，以及 G 距离顶点 v 比距离 u 更近的顶点数。仙人掌是一种任意两个环最多有一个公共顶点的图。设 C (n, k) 表示所有具有 n 和 k 阶循环的仙人掌类，C n t 表示具有 n 和 t 阶下垂顶点的所有仙人掌类。本文确定了具有 k 个周期的 n 阶仙人掌的 Szeged 指数下界，并识别了所有达到下界的图。同时，还描述了 C n t 中具有最小 Szeged 指数的唯一图。
The Szeged index of a graph G is defined as S z (G)=∑ e= u v∈ E n u (e) n v (e), where n u (e) and n v (e) are, respectively, the number of vertices of G lying closer to vertex u than to vertex v and the number of vertices of G lying closer to vertex v than to vertex u. A cactus is a graph in which any two cycles have at most one common vertex. Let C (n, k) denote the class of all cacti with order n and k cycles, and C n t denote the class of all cacti with order n and t pendant vertices. In this paper, a lower bound of the Szeged index for cacti of order n with k cycles is determined, and all the graphs that achieve the lower bound are identified. As well, the unique graph in C n t with minimum Szeged index is characterized.