单圈图Sigma指数的极大值

doi:10.12677/aam.2025.143114

期刊菜单

单圈图Sigma指数的极大值
On the Maximum Sigma Index of Unicyclic Graphs

DOI: 10.12677/aam.2025.143114, PDF, HTML, XML,
作者: 汤晓儀：广东工业大学数学与统计学院，广东广州
关键词: Sigma指数；Albertson指数；单圈图；Sigma Index； Albertson Index； Unicyclic Graphs

摘要: 无向连通图

G

的Sigma指数定义为

σ (G) = \sum_{u v \in E (G)} {(d_{G} (u) - d_{G} (v))}^{2}

，其中，

d_{G} (u)

和

d_{G} (v)

分别表示顶点

u

和

v

在图

G

中的度。本文研究了

n

阶单圈图的Sigma指数，用不同的方法讨论了其最大值。在本文中，我们也得到了单圈图中Sigma指数第二大值，并刻画了其极图。

Abstract: The sigma of an undirected graph

G

is defined as

σ (G) = \sum_{u v \in E (G)} {(d_{G} (u) - d_{G} (v))}^{2}

, where

d_{G} (u)

and

d_{G} (v)

denote the degrees of vertices

u

and

v

, respectively. In this paper, we investigate the Sigma index of n-vertex unicyclic graphs and discuss its maximum value using different methods. Furthermore, we determine the second largest Sigma index and extremal graph among unicyclic graphs.

文章引用：汤晓儀. 单圈图Sigma指数的极大值[J]. 应用数学进展, 2025, 14(3): 276-283. https://doi.org/10.12677/aam.2025.143114

1. 引言

1.1. 研究背景

设 $G = (V, E)$ 为n阶简单无向连通图，其中 $V (G) = {v_{1}, v_{2}, \dots, v_{n}}$ 为图G的顶点集， $E (G) = {u v | u, v \in V (G)}$ 为图G的边集。设顶点 $u \in V (G)$ ，与u相邻的所有顶点组成的集合称为顶点u的邻域，记为 $N_{G} (u)$ 。在图G中与u关联的边数，称为顶点u在图G中的度，记为 $d_{G} (u)$ 。此外，图G中顶点的最大度和最小度分别记为 $Δ (G)$ 和 $δ (G)$ ，度为1的顶点称为悬挂点；若 $Δ (G) = δ (G)$ ，则称图G为正则图，否则称之为非正则图。如何量化图的非正则程度是图论中的一个重要的研究课题，为此多个学者定义并研究了量化图的非正则指数，图的非正则性质在化学领域和神经网络[1]-[6]等科学领域都发挥着重要的作用。其中，最著名的非正则指数是由Albertson [7]提出的Albertson指数：

$Alb (G) = \sum_{u v \in V (G)} | d_{G} (u) - d_{G} (v) |$

以及Bell提出的Bell指数[8]：

$B (G) = \sum_{u \in V (G)} {(d_{G} (u) - \frac{2 m}{n})}^{2}$ .

图的Sigma指数由Gutman等人在文献[9]中第一次提出，它是Albertson指数的一种拓展，用符号 $σ (G)$ 表示，其定义如下：

$σ (G) = \sum_{u v \in E (G)} {(d_{G} (u) - d_{G} (v))}^{2} .$

该指数作为衡量图的非正则性质的重要工具，进一步丰富了图论在化学和网络科学等领域的应用。

2018年，Gutman等在文献[9]中定义了图的Sigma指数，并研究了Sigma指数的逆问题，他们证明了图的Sigma指数是一个偶数，并构造了一类图来说明Sigma指数能够覆盖所有正偶数。在该研究中，他们还建立了Sigma指数与遗忘指数 $F (G)$ 和第二Zagreb指数 $M_{2} (G)$ 之间的联系：

$σ (G) = F (G) - 2 M_{2} (G)$ .

其中， $F (G) = \sum_{u \in V (G)} d_{G}^{3} (u) = \sum_{u v \in E (G)} (d_{G}^{2} (u) + d_{G}^{2} (v))$ 和 $M_{2} (G) = \sum_{u v \in E (G)} d (u) d (v)$ ，这一发现为后续研究图的Sigma指数相关性质开辟了新途径。

Abdo等在文献[10]中刻画了所有连通图中具有最大Sigma指数的图的特征，同时给出了图的Sigma指数的下界。对于某些特定的图类，Réti在文献[11]中将Sigma指数与若干著名的度量非正则性的指数进行了对比。Ali等在文献[12]中确定了k-圈图中，具有最大Sigma指数的唯一的图。Vukicevic等在文献[13]中研究了在化学树(即度小于等于4的树)中最大Sigma指数的极值问题。

1.2. 预备知识

设G为n阶单圈图，其唯一的圈 $C_{r}$ 的顶点依次记为 $v_{1}, v_{2}, \dots, v_{r}$ 。删除图G中圈 $C_{r}$ 上的边会得到r个顶点不交的树 $T_{1}, T_{2}, \dots, T_{r}$ ，其中树 $T_{i}$ 与圈 $C_{r}$ 恰好有一个公共顶点 $v_{i}$ ，其中 $1 \leq i \leq r$ 。我们将单圈图记作 $C_{r} (T_{1}, T_{2}, \dots, T_{r})$ ，且 $T_{i}$ 的顶点个数 $| V {(T)}_{i} | = t_{i} + 1$ 。显然，任何圈长为r的n阶单圈图G都可以表示为 $C_{r} (T_{1}, T_{2}, \dots, T_{r})$ ，且满足 $\sum_{i = 1}^{r} t_{i} = n - r$ 。若对于 $i = 1, 2, \dots, r$ ，每一棵树 $T_{i}$ 是以顶点 $v_{i}$ 为中心、顶点数为 $t_{i} + 1$ 的星图 $S_{t_{i} + 1}$ ，此时我们记 $S_{n, r} (t_{1}, t_{2}, \dots, t_{r}) = C_{r} (T_{1}, T_{2}, \dots, T_{r})$ 。特别地，当 $t_{1} = n - r$ 且 $t_{2} = \dots = t_{r} = 0$ 时，则我们记 $S_{n, r} = S_{n, r} (t_{1}, t_{2}, \dots, t_{r})$ 。

对于连通图G，给定边子集 $E_{1} \subseteq E (G)$ ， $G - E_{1}$ 表示从图G中删除边子集 $E_{1}$ 中所有的边而得到的子图。令 $\bar{G}$ 表示图G的补图，对于补图的边子集 $E_{2} \subseteq E (\bar{G})$ ， $G + E_{2}$ 表示在图G的基础上，添加边子集 $E_{2}$ 中所有的边后所得到的图。

在本文中，我们采用了一种新的方法对具有最大Sigma指数的单圈图进行了刻画。此外，本文还确定了单圈图中Sigma指数第二大的图。

2. 结论及证明

引理 2.1 设G为一个连通图，顶点w为图G的最大度点，即 $d_{G} (w) = Δ (G)$ 。若存在一个顶点 $u \neq w$ 且u的邻域 $N_{G} (u) = {u_{1}, u_{2}, \dots, u_{k}, v}$ ，其中 $k \geq 1$ ， $d_{G} (u_{1}) = d_{G} (u_{2}) = \dots = d_{G} (u_{k}) = 1$ ，且 $d_{G} (v) \geq 2$ ，则令 $G^{'} = G - {u u_{i} : 1 \leq i \leq k} + {w u_{j} : 1 \leq j \leq k}$ ，如图1所示，那么 $σ (G^{'}) > σ (G)$ 。

Figure 1. The graphs of G and $G^{'}$ in Lemma 2.1

图1. 引理2.1中图G和图 $G^{'}$

证明：从图G变换为图 $G^{'}$ 时，只有顶点u和w的度发生了变化，而其余顶点的度保持不变。即 $d_{G^{'}} (w) = d_{G} (w) + d_{G} (u) - 1$ ， $d_{G^{'}} (u) = 1$ ，而对于其它顶点 $x \in V (G) \ {w, u}$ ，有 $d_{G'} (x) = d_{G} (x)$ 。

当 $v \neq w$ 时，我们有：

$\begin{matrix} σ (G^{'}) - σ (G) = \sum_{x \in N_{G} (w)} [{(d_{G^{'}} (w) - d_{G^{'}} (x))}^{2} - {(d_{G} (w) - d_{G} (x))}^{2}] \\ + \sum_{i = 1}^{k} [{(d_{G^{'}} (w) - 1)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G^{'}} (v) - 1)}^{2} - {(d_{G} (v) - d_{G} (u))}^{2} \\ = \sum_{x \in N_{G} (w)} [{(d_{G} (w) + d_{G} (u) - 1 - d_{G} (x))}^{2} - {(d_{G} (w) - d_{G} (x))}^{2}] \\ + \sum_{i = 1}^{k} [{(d_{G} (w) + d_{G} (u) - 2)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G} (v) - 1)}^{2} - {(d_{G} (v) - d_{G} (u))}^{2} \\ \geq \sum_{i = 1}^{k} [{(d_{G} (w) + d_{G} (u) - 2)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G} (v) - 1)}^{2} - {(d_{G} (v) - d_{G} (u))}^{2} \\ = (d_{G} (u) - 1) [{(d_{G} (w) - 1)}^{2} + 2 (d_{G} (w) - 1) (d_{G} (u) - 1)] + 2 d_{G} (v) d_{G} (u) - 2 d_{G} (v) - d_{G}^{2} (u) + 1 \\ > (d_{G} (u) - 1) [{(d_{G} (w) - 1)}^{2} + 2 (d_{G} (w) - 1) (d_{G} (u) - 1)] - d_{G}^{2} (u) + 1 \\ = (2 d_{G} (w) - 3) {(d_{G} (u) - 1)}^{2} + [{(d_{G} (w) - 1)}^{2} - 2] (d_{G} (u) - 1) . \end{matrix}$

由于 $d_{G} (w) \geq d_{G} (u) \geq 2$ ，我们可以得到不等式 $σ (G^{'}) - σ (G) > {(d_{G} (u) - 1)}^{2} - (d_{G} (u) - 1) \geq 0$ 。当 $v = w$ 时，此结论可以类似地证明。故引理2.1成立。

由引理2.1我们可得到以下推论：

推论 2.1 [2] 设T是一个不同构于 $S_{n}$ 和 $P_{n}$ 的n阶树，则有：

$2 = σ (P_{n}) < σ (T) < σ (S_{n}) = (n - 1) {(n - 2)}^{2}$ .

引理 2.2 设 $G = C_{r} (T_{1}, T_{2}, \dots, T_{r})$ 是一个n阶单圈图，其中圈 $C_{r} = v_{1} v_{2} \dots v_{r} v_{1}$ 。假设 $T_{1}$ 是不同构于以 $v_{1}$ 为中心的星图，设 $T_{1}$ 中与 $v_{1}$ 相邻且度数大于等于2的顶点为y。对于 $i = 2, \dots, r$ ， $T_{i}$ 均为以 $v_{i}$ 为中心的星图。我们设v为顶点 $v_{1}, v_{2}, \dots, v_{r}$ 中度数最大的顶点， $u_{1}$ 为 $T_{1}$ 中距离 $v_{1}$ 最远的悬挂点，其邻接顶点为u。若u的邻域为 $N_{G} (u) = {u_{1}, u_{2}, \dots, u_{t}, w}$ ，其中 $u_{1}, \dots, u_{t}$ 是悬挂点，且 $d_{G} (w) \geq 2$ ，则令 $G^{'} = G - {u u_{i} : 1 \leq i \leq t} + {v u_{j} : 1 \leq j \leq t}$ ，如图2所示。如果顶点u满足

$d_{G} (u) = \max {d_{G} (x) | x \in V (T_{1}) \ {v_{1}}}$ ，那么 $σ (G^{'}) > σ (G)$ 。

Figure 2. The graphs of G and $G^{'}$ in Lemma 2.2

图2. 引理2.2中图G和图 $G^{'}$

证明：为了研究Sigma的极值问题，我们在点边变换的过程中选择距离最远的悬挂点进行变换，确保变换后能够通过增加度数差，从而有效地增大Sigma指数。如果选择其他顶点进行变换，存在导致Sigma指数减小的情况。因此，从图G变换为图 $G^{'}$ 时，只有顶点u和v的度发生了变化，而其余顶点的度保持不变。即 $d_{G^{'}} (v) = d_{G} (v) + d_{G} (u) - 1$ ， $d_{G^{'}} (u) = 1$ ，而对于其它顶点 $x \in V (G) \ {v, u}$ ， $d_{G^{'}} (x) = d_{G} (x)$ 。

若 $v \neq v_{1}$ ，则我们有：

$\begin{matrix} σ (G^{'}) - σ (G) = \sum_{x \in N_{G} (v)} [{(d_{G^{'}} (v) - d_{G^{'}} (x))}^{2} - {(d_{G} (v) - d_{G} (x))}^{2}] \\ + \sum_{i = 1}^{t} [{(d_{G^{'}} (v) - 1)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G^{'}} (w) - d_{G^{'}} (u))}^{2} - {(d_{G} (w) - d_{G} (u))}^{2} \\ > \sum_{i = 1}^{t} [{(d_{G} (v) + d_{G} (u) - 1 - 1)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G} (w) - 1)}^{2} - {(d_{G} (w) - d_{G} (u))}^{2} \\ = (d_{G} (u) - 1) [{(d_{G} (v) - 1)}^{2} + 2 (d_{G} (u) - 1) (d_{G} (v) - 1)] - 2 d_{G} (w) + 1 - d_{G}^{2} (u) + 2 d_{G} (w) d_{G} (u) \\ > (d_{G} (u) - 1) [{(d_{G} (v) - 1)}^{2} + 2 (d_{G} (u) - 1) (d_{G} (v) - 1)] - d_{G}^{2} (u) + 1 \\ = (2 d_{G} (v) - 3) {(d_{G} (u) - 1)}^{2} + [{(d_{G} (v) - 1)}^{2} - 2] (d_{G} (u) - 1) . \end{matrix}$

因为 $d_{G} (v) \geq 3$ 且 $d_{G} (u) \geq 2$ ，所以 $σ (G^{'}) - σ (G) > 0$ 。

若 $v = v_{1}$ 且顶点u和顶点v不相邻，则我们有：

$\begin{matrix} σ (G^{'}) - σ (G) = \sum_{_{x \in N_{G} (v) \ {y}}} [{(d_{G^{'}} (v) - d_{G^{'}} (x))}^{2} - {(d_{G} (v) - d_{G} (x))}^{2}] + \sum_{i = 1}^{t} [{(d_{G^{'}} (v) - 1)}^{2} - {(d_{G} (u) - 1)}^{2}] \\ + {(d_{G^{'}} (v) - d_{G^{'}} (y))}^{2} - {(d_{G} (v) - d_{G} (y))}^{2} + {(d_{G^{'}} (w) - d_{G^{'}} (u))}^{2} - {(d_{G} (w) - d_{G} (u))}^{2} \\ > \sum_{i = 1}^{t} [{(d_{G} (v) + d_{G} (u) - 1 - 1)}^{2} - {(d_{G} (u) - 1)}^{2}] \\ + {(d_{G} (v) + d_{G} (u) - 1 - d_{G} (y))}^{2} - {(d_{G} (v) - d_{G} (y))}^{2} + {(d_{G} (w) - 1)}^{2} - {(d_{G} (w) - d_{G} (u))}^{2} \\ = (d_{G} (u) - 1) [{(d_{G} (v) - 1)}^{2} + 2 (d_{G} (u) - 1) (d_{G} (v) - 1)] \\ - 2 d_{G} (w) + 1 - d_{G}^{2} (u) + 2 d_{G} (w) d_{G} (u) + {(d_{G} (u) - 1)}^{2} + 2 (d_{G} (u) - 1) (d_{G} (v) - d_{G} (y)) \\ > (2 d_{G} (v) - 1) {(d_{G} (u) - 1)}^{2} + (d_{G}^{2} (v) + 1 - 2 d_{G} (y)) (d_{G} (u) - 1) - d_{G}^{2} (u) + 1 \\ \geq (2 \times 3 - 1) {(d_{G} (u) - 1)}^{2} + (3^{2} + 1 - 2 d_{G} (u)) (d_{G} (u) - 1) - d_{G}^{2} (u) + 1 \\ = 2 (d_{G} (u) + 2) (d_{G} (u) - 1) \\ > 0. \end{matrix}$

若 $v = v_{1}$ 且顶点u和顶点v相邻，则我们有：

$\begin{matrix} σ (G^{'}) - σ (G) = \sum_{x \in N_{G} (v) \ {u}} [{(d_{G^{'}} (v) - d_{G^{'}} (x))}^{2} - {(d_{G} (v) - d_{G} (x))}^{2}] \\ + \sum_{i = 1}^{t} [{(d_{G^{'}} (v) - 1)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G^{'}} (v) - d_{G^{'}} (u))}^{2} - {(d_{G} (v) - d_{G} (u))}^{2} \\ > \sum_{i = 1}^{t} [{(d_{G} (v) + d_{G} (u) - 2)}^{2} - {(d_{G} (u) - 1)}^{2}] + {(d_{G} (v) + d_{G} (u) - 2)}^{2} - {(d_{G} (v) - d_{G} (u))}^{2} \\ = (d_{G} (u) - 1) [{(d_{G} (v) - 1)}^{2} + 2 (d_{G} (u) - 1) (d_{G} (v) - 1)] + 4 [(d_{G} (u) - 1) (d_{G} (v) - 1)] \\ > 0. \end{matrix}$

综上所述，引理2.2证毕。

标注 2.1 设 $G = C_{r} (T_{1}, T_{2}, \dots, T_{r})$ 是一个n阶单圈图。如果 $T_{1}, T_{2}, \dots, T_{r}$ 中至少存在两个树不是星图，则引理2.2的结论不一定成立。例如图3所示的图 $G_{1}$ 和 $G_{2}$ ，其中 $G_{1}$ 通过引理2.2得到 $G_{2}$ 。然而，通过计算表明： $σ (G_{2}) - σ (G_{1}) = - 18$ 。

Figure 3. The graphs of G₁ and G₂ in Remark 2.1

图3. 标注2.1中图G₁和图G₂

由引理2.1和2.2可得到如下结果：

推论 2.2 设 $G = C_{r} (T_{1}, T_{2}, \dots, T_{r})$ 是一个n阶单圈图，则有 $σ (G) \leq σ (S_{n, r} (t_{1}, t_{2}, \dots, t_{r}))$ ，等号成立当且仅当 $G ≅ S_{n, r} (t_{1}, t_{2}, \dots, t_{r})$ 。

引理 2.3 假设 $t_{1} = \max {t_{1}, t_{2}, t_{3}, \dots, t_{r}}$ ，那么 $σ (S_{n, r} (t_{1}, t_{2}, \dots, t_{r})) \leq σ (S_{n, r})$ ，等号成立当且仅当 $t_{1} = n - r$ 且 $t_{2} = \dots = t_{r} = 0$ 。

证明：记 $G = S_{n, r} (t_{1}, t_{2}, \dots, t_{r})$ 。若 $t_{2} \geq 1$ ，则令 $G_{1} = S_{n, r} (t_{1} + t_{2}, 0, \dots, t_{r - 1}, t_{r})$ 。通过计算有：

$\begin{matrix} σ (G_{1}) - σ (G) = (t_{1} + t_{2}) {(t_{1} + t_{2} + 1)}^{2} + {(t_{1} + t_{2})}^{2} + {(t_{1} + t_{2} - t_{r})}^{2} + t_{3}^{2} \\ - t_{1} {(t_{1} + 1)}^{2} - t_{2} {(t_{2} + 1)}^{2} - {(t_{1} - t_{2})}^{2} - {(t_{1} - t_{r})}^{2} - {(t_{2} - t_{3})}^{2} \\ > (t_{1} + t_{2}) {(t_{1} + t_{2} + 1)}^{2} - t_{1} {(t_{1} + 1)}^{2} - t_{2} {(t_{2} + 1)}^{2} + t_{3}^{2} - {(t_{2} - t_{3})}^{2} \\ = t_{1} [t_{2}^{2} + 2 t_{2} (t_{1} + 1)] + t_{2} [t_{1}^{2} + 2 t_{1} (t_{2} + 1)] - t_{2}^{2} + 2 t_{2} t_{3} \\ > 0. \end{matrix}$

同理可得，若 $t_{r} \geq 1$ ，则 $σ (S_{n, r} (t_{1} + t_{r}, t_{2}, \dots, t_{r - 1}, 0)) > σ (G)$ 。

现设存在整数k ( $3 \leq k \leq r - 1$ )满足 $t_{k} \geq 1$ ，令 $G_{2} = S_{n, r} (t_{1} + t_{k}, t_{2}, \dots, t_{k - 1}, 0, t_{k + 1}, \dots, t_{r})$ ，则有

$\begin{matrix} σ (G_{2}) - σ (G) = (t_{1} + t_{k}) {(t_{1} + t_{k} + 1)}^{2} + {(t_{1} + t_{k} - t_{2})}^{2} + {(t_{1} + t_{k} - t_{r})}^{2} + t_{k - 1}^{2} + t_{k + 1}^{2} \\ - t_{1} {(t_{1} + 1)}^{2} - t_{k} {(t_{k} + 1)}^{2} - {(t_{1} - t_{2})}^{2} - {(t_{1} - t_{r})}^{2} - {(t_{k - 1} - t_{k})}^{2} - {(t_{k + 1} - t_{k})}^{2} \\ > (t_{1} + t_{k}) {(t_{1} + t_{k} + 1)}^{2} - t_{1} {(t_{1} + 1)}^{2} - t_{k} {(t_{k} + 1)}^{2} + t_{k - 1}^{2} - {(t_{k - 1} - t_{k})}^{2} + t_{k + 1}^{2} - {(t_{k + 1} - t_{k})}^{2} \\ > t_{1} [t_{k}^{2} + 2 t_{k} (t_{1} + 1)] + t_{k} [t_{1}^{2} + 2 t_{1} (t_{k} + 1)] - 2 t_{k}^{2} \\ > 0. \end{matrix}$

因此， $σ (S_{n, r} (t_{1}, t_{2}, \dots, t_{r})) \leq σ (S_{n, r})$ ，等号成立当且仅当 $t_{1} = n - r$ 且 $t_{2} = \dots = t_{r} = 0$ 。

注意到，函数 $f (r) = σ (S_{n, r}) = (n - r) {(n - r + 1)}^{2} + 2 {(n - r)}^{2}$ 在区间 $r \in [3, n - 1]$ 上单调递减，因此有：

推论 2.3 $σ (S_{n, n - 1}) < σ (S_{n, n - 2}) < \dots < σ (S_{n, 4}) < σ (S_{n, 3})$ 。

$S_{n, 3}$ 、 $S_{n, 4}$ 如图4所示。

Figure 4. The graphs of $S_{n, 3}$ and $S_{n, 4}$

图4. 图 $S_{n, 3}$ 和图 $S_{n, 4}$

用 $U_{n, r}$ 表示所有圈长度为r的n阶单圈图集合，其中 $3 \leq r \leq n$ 。用 $U_{n}$ 表示所有n阶单圈图的集合。结合引理2.1、引理2.2和引理2.3，我们可以得到如下的定理：

定理 2.1 [4] 在 $U_{n}$ 中， $S_{n, 3}$ 是具有最大Sigma指数的唯一图。

设 $n \geq 5$ ，连接圈 $C_{3}$ 的一个顶点和星图 $S_{a + 1}$ 的中心点，并在 $C_{3}$ 的这个顶点上连接 $n - 4 - a$ 个悬挂顶点得到的图记为 ${S^{'}}_{n, 3} (a)$ 。在圈 $C_{3}$ 的一个顶点上连接a个悬挂顶点，再在它的另一个顶点上连接 $n - 3 - a$ 个悬挂顶点所得到的图记为 ${S^{″}}_{n, 3} (a)$ ，如图5所示。

Figure 5. The graphs of ${S^{'}}_{n, 3} (a)$ and ${S^{″}}_{n, 3} (a)$

图5. 图 ${S^{'}}_{n, 3} (a)$ 和图 ${S^{″}}_{n, 3} (a)$

通过计算推导可以得到以下公式：

$σ ({S^{'}}_{n, 3} (a)) = (3 n - 2) a^{2} + (- 3 n^{2} + 8 n) a + n^{3} - 5 n^{2} + 4 n + 6$ ,

$σ ({S^{″}}_{n, 3} (a)) = (3 n + 1) a^{2} + (- 3 n^{2} + 8 n + 3) a + n^{3} - 5 n^{2} + 4 n + 6$ .

令函数 $f_{1} (a) = σ ({S^{'}}_{n, 3} (a))$ ，其中 $1 \leq a \leq n - 4$ ，函数 $f_{2} (a) = σ ({S^{″}}_{n, 3} (a))$ ，其中 $1 \leq a \leq ⌊ \frac{n - 3}{2} ⌋$ 。

当 $n \geq 6$ 时，我们对 $f_{1} (a)$ 求导得到： ${f^{'}}_{1} (a) = 2 (3 n - 2) a - 3 n^{2} + 8 n$ ， $1 \leq a < \frac{3 n^{2} - 8 n}{2 (3 n - 2)}$ 时 ${f^{'}}_{1} (a) < 0$ ， $\frac{3 n^{2} - 8 n}{2 (3 n - 2)} < a \leq n - 4$ 时 ${f^{'}}_{1} (a) > 0$ 。

同样地，我们对 $f_{2} (a)$ 求导可得： ${f^{'}}_{2} (a) = 2 (3 n + 1) (a - \frac{n - 3}{2})$ ，当 $1 \leq a \leq ⌊ \frac{n - 3}{2} ⌋$ 时 ${f^{'}}_{2} (a) \leq 0$ 。

综上，我们可以得到函数 $f_{1} (a)$ 和 $f_{2} (a)$ 的最大值：

$\begin{matrix} f_{1} (a) \leq \max {f_{1} (1), f_{1} (n - 4)} \\ = \max {n^{3} - 8 n^{2} + 15 n + 4, n^{3} - 11 n^{2} + 36 n - 26} \\ = n^{3} - 8 n^{2} + 15 n + 4 \end{matrix}$

$f_{2} (a) \leq f_{2} (1) = n^{3} - 8 n^{2} + 15 n + 10$ 。

引理 2.4 设 $G ≅ C_{3} (T_{1}, T_{2}, T_{3})$ 是一个n阶单圈图且 $G ≅ S_{n, 3}$ ，则 $σ (G) \leq n^{3} - 8 n^{2} + 15 n + 10$ ，等号成立当且仅当 $G ≅ {S^{″}}_{n, 3} (1)$ 。

证明：不失一般性设 $t_{1} \geq t_{2} \geq t_{3}$ 。若 $t_{2} \geq 1$ ，则由引理2.1、2.2和2.3可以得到

$σ (C_{3} (T_{1}, T_{2}, T_{3})) \leq σ (S_{n} (t_{1}, t_{2}, t_{3})) \leq σ (S_{n} (t_{1} + t_{3}, t_{2}, 0)) = σ ({S^{″}}_{n, 3} (t_{2})) .$

若 $t_{2} = 0$ 且 $G ≅ S_{n, 3}$ ，则 $T_{3} ≅ S_{t_{3} + 1}$ 。由引理2.1和引理2.2可知 $σ (C_{3} (T_{1}, T_{2}, T_{3})) \leq σ ({S^{'}}_{n, 3} (a))$ ，其中 $a \in [1, n - 4]$ 。

又由前面的推导可得： $σ ({S^{″}}_{n, 3} (t_{2})) \leq σ ({S^{″}}_{n, 3} (1))$ ，且 $σ ({S^{'}}_{n, 3} (a)) \leq σ ({S^{'}}_{n, 3} (1)) < σ ({S^{″}}_{n, 3} (1))$ 。注意到第一个等号成立当且仅当 $t_{2} = 1$ 。

定理 2.2 设 $n \geq 6$ ，在 $U_{n}$ 中，

(i) ${S^{″}}_{6, 3} (1)$ 是 $U_{6}$ 中具有第二大Sigma指数的唯一图，其Sigma指数为28；

(ii) ${S^{″}}_{7, 3} (1)$ 和 $S_{7, 4}$ 是 $U_{7}$ 中具有第二大Sigma指数的图，其Sigma指数为66；

(iii) 若 $n \geq 8$ ，则 $S_{n, 4}$ 是 $U_{n}$ 中具有第二大Sigma指数的唯一图，其Sigma指数为 $n^{3} - 8 n^{2} + 17 n - 4$ 。

证明：若 $G \in U_{n, 3} \ {S_{n, 3}}$ ，由引理2.4可得 $σ (G) \leq σ ({S^{″}}_{n, 3} (1)) = n^{3} - 8 n^{2} + 15 n + 10$ ，等号成立当且仅当 $G ≅ {S^{″}}_{n, 3} (1)$ 。

若 $G \in \cup_{r = 4}^{n} U_{n, r}$ ，则由推论2.2和推论2.3可得 $σ (G) \leq σ (S_{n, 4}) = n^{3} - 8 n^{2} + 17 n - 4$ ，等号成立当且仅当 $G ≅ S_{n, 4}$ 。

综上，通过直接计算比较 $σ (S_{n, 4})$ 和 $σ ({S^{″}}_{n, 3} (1))$ 可得单圈图第二大Sigma指数。 $n = 6$ 时 $σ ({S^{″}}_{6, 3} (1)) = 28 > 26 = σ (S_{6, 4})$ ， $n = 7$ 时 $σ ({S^{″}}_{7, 3} (1)) = σ (S_{7, 4}) = 66$ ， $n \geq 8$ 时 $σ (S_{n, 4}) > σ ({S^{″}}_{n, 3} (1))$ 。因此定理2.2成立。

参考文献

[1]	Abdo, H. and Dimitrov, D. (2014) The Total Irregularity of Graphs under Graph Operations. Miskolc Mathematical Notes, 15, 3-17. https://doi.org/10.18514/mmn.2014.593
[2]	Criado, R., Flores, J., García del Amo, A. and Romance, M. (2013) Centralities of a Network and Its Line Graph: An Analytical Comparison by Means of Their Irregularity. International Journal of Computer Mathematics, 91, 304-314. https://doi.org/10.1080/00207160.2013.793316
[3]	Estrada, E. (2010) Randic Index, Irregularity and Complex Biomolecular Networks. Acta Chimica Slovenica, 57, 597-603.
[4]	Gutman, I., Hansen, P. and Mélot, H. (2005) Variable Neighborhood Search for Extremal Graphs. Comparison of Irregularity Indices for Chemical Trees. Journal of Chemical Information and Modeling, 45, 222-230. https://doi.org/10.1021/ci0342775
[5]	Reti, T., Sharafdini, R., Dregelyi-Kiss, A. and Haghbin, H. (2018) Graph Irregularity Indices used as Molecular Descriptors in QSPR Studies. MATCH Communications in Mathematical and in Computer Chemistry, 79, 509-524.
[6]	Safaei, F., Tabrizchi, S., Hadian Rasanan, A.H. and Zare, M. (2019) An Energy-Based Heterogeneity Measure for Quantifying Structural Irregularity in Complex Networks. Journal of Computational Science, 36, Article 101011. https://doi.org/10.1016/j.jocs.2019.06.008
[7]	Albertson, M.O. (1997) The Irregularity of a Graph. ARS Combinatoria, 46, 219-225.
[8]	Bell, F.K. (1992) A Note on the Irregularity of Graphs. Linear Algebra and its Applications, 161, 45-54. https://doi.org/10.1016/0024-3795(92)90004-t
[9]	Gutman, I., Togan, M., Yurttas, A., Cevik, A.S. and Cangul, I.N. (2018) Inverse Problem for Sigma Index. MATCH Communications in Mathematical and in Computer Chemistry, 79, 491-508.
[10]	Abdo, H., Dimitrov, D. and Gutman, I. (2018) Graphs with Maximal σ Irregularity. Discrete Applied Mathematics, 250, 57-64. https://doi.org/10.1016/j.dam.2018.05.013
[11]	Réti, T. (2019) On Some Properties of Graph Irregularity Indices with a Particular Regard to the Σ-Index. Applied Mathematics and Computation, 344, 107-115. https://doi.org/10.1016/j.amc.2018.10.010
[12]	Ali, A., Albalahi, A.M., Alanazi, A.M., Bhatti, A.A. and Hamza, A.E. (2023) On the Maximum Sigma Index of k-Cyclic Graphs. Discrete Applied Mathematics, 325, 58-62. https://doi.org/10.1016/j.dam.2022.10.009
[13]	Kovijanić Vukićević, Ž., Popivoda, G., Vujošević, S., Škrekovski, R. and Dimitrov, D. (2023) The Σ-Irregularity of Chemical Trees. MATCH Communications in Mathematical and in Computer Chemistry, 91, 267-282. https://doi.org/10.46793/match.91-1.267k

为你推荐

友情链接