一些互补等能量强正则图的刻画 Characterization of Some Complementary Equienergetic Strongly Regular Graphs

doi:10.12677/ORF.2023.131022

Operations Research and Fuzziology
Vol. 13 No. 01 ( 2023 ), Article ID: 61359 , 6 pages
10.12677/ORF.2023.131022

一些互补等能量强正则图的刻画

姜艺淼，梁超凡

●How to Cite this Article

长安大学理学院，陕西西安

收稿日期：2023年1月18日；录用日期：2023年2月7日；发布日期：2023年2月15日

摘要

图G的能量 $E (G)$ 是其邻接矩阵的所有特征值绝对值的和。如果一个图和它的补图不同构且具有相同的能量，则称此图是互补等能量的。本文利用强正则图的参数给出了其能量表达式，并借助此公式给出了两类(无穷)互补等能量的强正则图的参数。

关键词

互补等能量，强正则图，特征值

Characterization of Some Complementary Equienergetic Strongly Regular Graphs

Yimiao Jiang, Chaofan Liang

School of Science, Chang’an University, Xi’an Shannxi

Received: Jan. 18^th, 2023; accepted: Feb. 7^th, 2023; published: Feb. 15^th, 2023

ABSTRACT

The energy $E (G)$ of a graph G is the sum of the absolute values of all eigenvalues of its adjacency matrix. Graph energy comes from quantum chemistry. If a graph and its complement graph are not isomorphic and have the same energy, then the graph is said to be complementary equienergetic. In this paper, the energy expression of the strongly regular graph is given by the parameters of that, and the parameters of two types(infinite) of complementary equaenergetic strongly regular graph are given with the help of this formula.

Keywords:Complementary Equienergetic, Strongly Regular Graphs, Eigenvalues

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

设有n个顶点的无向简单图G的顶点集为 $V (G) = {v_{1}, \dots, v_{n}}$ ，边集为 $E (G)$ 。其邻接矩阵定义为 $A = {(a_{i j})}_{n \times n}$ ，其中 $a_{i j} = {\begin{cases} 1, 若 v_{i} 和 v_{j} 相邻 \\ 0, 其它 \end{cases}$ (邻接矩阵为实对称矩阵且主对角元素为0)。若G每个顶点都具有k个相邻顶点，则称若G是k-正则图，参数为 $(v, k, λ, μ)$ 的强正则图就是有v个顶点的k-正则图，且其中任意两个相邻顶点恰好有 $λ$ 个公共相邻顶点，任意两个非相邻顶点恰好有 $μ$ 个公共相邻顶点。图G的能量E定义为 $E = \sum_{i = 1}^{n} | λ_{i} |$ ，其中 $λ_{i}$ 是其邻接矩阵A的特征值，如果两个图有相同的能量，则称它们是等能量的，如果一个图和它的补图不同构且具有相同的能量，则称图是互补等能量的。1978年Gutman首先在 [1] 中定义了图能量，在过去的四十年中引起了研究者的广泛关注。图能的概念源于量子化学，与分子图 [2] 的总 $π$ -电子能有关。等能图的构造有许多论文，例如：Hou和Xu [3] 构造了无穷多个等能二部图。Vinagre [4] 等人给出了一种利用图积从起始图中获得新等能图对的方法。关于等能量的强正则图的研究，近几年，Ramane等人在 [5] [6] 构造了几类互补等能图以及与强正则图相关的等能图。本文通过观察互补等能量图的参数规律构造出了一些互补等能量的强正则图，强正则图在图论和编码理论之间架起了桥梁，因此对于代数图论是至关重要的。

2. 预备知识

定理2.1给出了强正则图的特征值以及特征值重数的计算方法。

定理2.1 [7] 如果G是带有参数 $(v, k, λ, μ)$ 的强正则图，则G的谱是 $k, r, s$ ，且

$r, s = \frac{λ - μ \pm \sqrt{Δ}}{2}, Δ = {(λ - μ)}^{2} + 4 (k - μ)$ (1)

它们的重数分别为 $1, f, g$ ，其中

$f, g = \frac{v - 1 \mp \frac{2 k + (v - 1) (λ - μ)}{\sqrt{Δ}}}{2}$

定理2.1给出了强正则图补图的参数以及强正则图存在的必要条件。

定理2.2 [8] 若G是带有参数 $(v, k, λ, μ)$ 的强正则图，则其补图 $\bar{G}$ 是带有参数 $(\bar{v}, \bar{k}, \bar{λ}, \bar{μ})$ ，其中 $\bar{v} = v$ ， $\bar{k} = v - k - 1$ ， $\bar{λ} = v - 2 - 2 k + μ$ ， $\bar{μ} = v - 2 k + λ$ 。若考虑一个固定顶点u，用两种方法计算边vw，使得u与v相邻，但不与w相邻，则

$k (k - λ - 1) = (v - k - 1) μ$ 。

3. 一些自补等能量的强正则图

下面我们给出了强正则图能量的表达式，并可以根据表达式判断两个图能量是否相等。

定理3.1 若G是带有参数 $(v, k, λ, μ)$ 的强正则图且谱为 ${k^{(1)}, r^{(f)}, s^{(g)}}$ ，则图G的能量为

$E (G) = k + \frac{(k + 2 - 2 v) μ + k (2 v - λ - 2)}{\sqrt{4 k + {(λ - μ)}^{2} - 4 μ}}$ 。

证明：根据定理2.2，图G的谱为 ${k^{(1)}, r^{(f)}, s^{(g)}}$ ，则

$r, s = \frac{λ - μ \pm \sqrt{Δ}}{2}, Δ = {(λ - μ)}^{2} + 4 (k - μ), f, g = \frac{v - 1 \mp \frac{2 k + (v - 1) (λ - μ)}{\sqrt{Δ}}}{2}$ 。

因为 $k \geq μ, Δ \geq {(λ - μ)}^{2}$ ，可得 $r \geq 0, s \leq 0$ 。且 $k + f r + g s = t r (A (G)) = 0$ ，所以 $s < 0$ 。

根据能量的定义可得

$\begin{matrix} E (G) = | k | \times 1 + | r | \times \frac{v - 1 - \frac{2 k + (v - 1) (λ - μ)}{\sqrt{Δ}}}{2} + | s | \times \frac{v - 1 + \frac{2 k + (v - 1) (λ - μ)}{\sqrt{Δ}}}{2} \\ = k + \frac{λ - μ + \sqrt{{(λ - μ)}^{2} + 4 (k - μ)}}{2} \times \frac{v - 1 - \frac{2 k + (v - 1) (λ - μ)}{\sqrt{Δ}}}{2} \\ - \frac{λ - μ - \sqrt{{(λ - μ)}^{2} + 4 (k - μ)}}{2} \times \frac{v - 1 + \frac{2 k + (v - 1) (λ - μ)}{\sqrt{Δ}}}{2} \\ = k + \frac{(k + 2 - 2 v) μ + k (2 v - λ - 2)}{\sqrt{4 k + {(λ - μ)}^{2} - 4 μ}} \end{matrix}$ (2)

根据定理2.3， $\bar{G}$ 是带有参数 $(\bar{v}, \bar{k}, \bar{λ}, \bar{μ})$ 的强正则图，将 $\bar{v} = v$ ， $\bar{k} = v - k - 1$ ， $\bar{λ} = v - 2 - 2 k + μ$ ， $\bar{μ} = v - 2 k + λ$ 代入(4)得

$E (\bar{G}) = v - k - 1 + \frac{(1 - v) (λ + μ) + k (2 v + μ - λ - 4)}{\sqrt{4 k + {(λ - μ)}^{2} - 4 μ}}$ (3)

定理3.2和定理3.3给出了本文构造的不同构且互补等能量的强正则图。

定理3.2 G是一个带参数 $({(2 n + t)}^{2}, 2 n^{2} + (t - 1) n, n^{2} - n + t, n^{2} - n) (n > 1, t \in Z^{+})$ 的强正则图，则 $E (G) = E (\bar{G})$ 。

证明：将G的参数代入公式(2)，利用mathematica计算可得

$E (G) = \frac{n (- 1 + 2 n + t) (4 n^{2} + 2 t^{2} + 6 n t + 4 n + 2 t)}{2 n + t}$ ，

将 $\bar{G}$ 的参数代入公式(3)， $\bar{G}$ 的能量计算为

$E (\bar{G}) = \frac{(- 1 + n + 2 n^{2} + 3 n t + t^{2}) (4 n^{2} + 2 n t)}{2 n + t}$ ，

化简得 $E (G) = E (\bar{G})$ 。

在得出G与 $\bar{G}$ 等能量之后，再判断是否同构，若其特征值不相等，则G与 $\bar{G}$ 不同构。将G与 $\bar{G}$ 的参数代入公式(1)，则可得到G与 $\bar{G}$ 的特征值，见表1：

Table 1. Eigenvalues of G and G ¯

表1. G与 $\bar{G}$ 的特征值

由此可见，G与 $\bar{G}$ 不同构且等能量，则称强正则图G是互补等能量的。

另外我们利用编程搜索得到了存在的 $n > 1, t = 3$ 时互补等能量的强正则图的参数 [9] ，见表2：

Table 2. Parameters of complementaryequienergetic strongly regular graph (t = 3)

表2. 互补等能量的强正则图的参数(t = 3)

定理3.3 G是一个带参数

$({(2 n + t)}^{2}, (n + t) (2 n + t - 1), (n + t) (n + t - 1) - t, (n + t) (n + t - 1)) (n > 1, t > 1, t \in Z^{+})$ 的强正则图，则 $E (G) = E (\bar{G})$ 。

证明：将G的参数代入公式(2)，同样利用mathematica计算可得

$E (G) = \frac{(4 n^{2} + 2 n t + 4 n + 2 t) (2 n^{2} + (- 1 + t) t + n (- 1 + 3 t))}{2 n + t}$ ，

将 $\bar{G}$ 的参数代入公式(3)， $\bar{G}$ 的能量计算为

$E (\bar{G}) = \frac{(1 + n) (- 1 + 2 n + t) (4 n^{2} + 2 t^{2} + 6 n t)}{2 n + t}$ ，

化简得 $E (G) = E (\bar{G})$ 。

同样判断G与 $\bar{G}$ 是否同构，将G与 $\bar{G}$ 的参数代入公式(1)，则可得到G与 $\bar{G}$ 的特征值，见表3：

Table 3. Eigenvalues of G and G ¯

表3. G与 $\bar{G}$ 的特征值

由此可见，G与 $\bar{G}$ 不同构且等能量，则称强正则图G是互补等能量的。

表4给出了编程搜索到的存在的 $n > 1, t = 3$ 时互补等能量的强正则图的参数 [9] ，见表4：

Table 4. Parameters of complementary equienergetic strongly regular graph (t = 3)

表4. 互补等能量的强正则图的参数(t = 3)

文章引用

姜艺淼,梁超凡. 一些互补等能量强正则图的刻画
Characterization of Some Complementary Equienergetic Strongly Regular Graphs[J]. 运筹与模糊学, 2023, 13(01): 204-209. https://doi.org/10.12677/ORF.2023.131022

参考文献

1. Gutman, I. (1978) The Energy of a Graph, Berichte Math. Berichte der Mathematisch-Statistischen Sektion im Forschungszentrum Graz, 103, 1-22.

2. Li, X., Shi, Y. and Gutman, I. (2012) Graph Energy. Springer, New York. https://doi.org/10.1007/978-1-4614-4220-2

3. Hou, Y. and Xu, L. (2007) Equienergetic Bipartite Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 57, 363-370.

4. Bonifácio, A.S., et al. (2008) Constructing Pairs of Equienergetic and Noncospectral Graphs. Applied Mathematics Letters, 21, 338-341. https://doi.org/10.1016/j.aml.2007.04.002

5. Ramane, H.S., et al. (2019) Graphs Equienergetic with Their Complements. MATCH Communications in Mathematical and in Computer Chemistry, 82, 471-480.

6. Ramane, H.S., et al. (2020) On Complementary Equienergetic Strongly Regulargraphs. Discrete Mathematics Letters, 4, 50-55.

7. Cvetkovi´c, D.M., Doob, M. and Sachs, H. (1980) Spectra of Graphs: Theory and Application. Deutscher Verlag der Wissenschaften, Berlin.

8. Cvetkovi’c, D.M., Rowlinson, P. and Simi’c, S. (2010) An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge.

9. Brouwer, A.E. and Van Maldeghem, H. (2022) Strongly Regular Graphs. Cambridge University Press, Cambridge. https://doi.org/10.1017/9781009057226

期刊菜单