一些可交换图的刻画

doi:10.12677/ORF.2024.141094

期刊菜单

一些可交换图的刻画
Characterization of Some Commutative Graphs

DOI: 10.12677/ORF.2024.141094, PDF, HTML, XML,
作者: 申悦, 苏柯：长安大学理学院，陕西西安
关键词: 图；邻接矩阵；克罗内克积；可交换；Graph； Adjacency Matrix； Kronecker Product； Commutativity

摘要: 两个图称为可交换的，如果存在一种顶点标号使得它们在该顶点标号下的邻接矩阵可交换。本文通过利用已知可交换图的性质及矩阵克罗内克积积运算、图联运算的性质，从已知可交换图出发构造出新的可交换图，对研究可交换图问题有重要促进作用。

Abstract: Two graphs are called commuting if there exists a labelling of the vertices such that their adjacency matrix commute. In this paper, new commuting graphs are constructed from the known ones by using the properties of the commuting matrices, the Kronecker product operation of matrix and the joint operation of a graph, which promotes the study of commuting graphs.

文章引用：申悦, 苏柯. 一些可交换图的刻画[J]. 运筹与模糊学, 2024, 14(1): 1015-1020. https://doi.org/10.12677/ORF.2024.141094

1. 引言

设 $n$ 阶无向简单图 $G$ 的顶点集为 $V (G) = {v_{1}, \dots, v_{n}}$ ，边集为 $E (G)$ 。其邻接矩阵定义为 $A = {(a_{i j})}_{n \times n}$ ，

其中 $a_{i j} = {\begin{matrix} \begin{matrix} 1, & 若 v_{i} 和 v_{j} 相邻 \end{matrix} \\ \begin{matrix} 0, & 其它 \end{matrix} \end{matrix}$ 。顶点的邻点个数记为顶点的度，若 $G$ 每个顶点的度均为 $k$ ，则称 $G$ 是 $k$ -正

则图。设 $G_{1}$ ， $G_{2}$ 是两个图，并设 $G_{1} = (V_{1}, E_{1})$ ， $G_{2} = (V_{2}, E_{2})$ ，则 $G_{1}$ 与 $G_{2}$ 的并是指图 $(V_{1} \cup V_{2}, E_{1} \cup E_{2})$ ，记为 $G_{1} \cup G_{2}$ 。特别的，若 $V_{1} \cap V_{2}$ 为空集，则 $G_{1} \cup G_{2}$ 称为 $G_{1}$ 与 $G_{2}$ 的不交并，不交并有时也称为和，记为 $G_{1} + G_{2}$ 。两个无公共顶点的图 $G_{1}$ ， $G_{2}$ 的不交并 $G_{1} + G_{2}$ 再添加边集 ${(x, y) | x \in V (G_{1}), y \in V (G_{2})}$ 后得到的图称为 $G_{1}$ 与 $G_{2}$ 的联，记为 $G_{1} \nabla G_{2}$ 。图 $G$ 的分裂图 $S' (G)$ 是通过在 $G$ 的每个顶点 $v$ 上添加一个新的顶点 $v'$ 得到的， $v'$ 与 $G$ 中 $v$ 的每一个邻点相连。连通图 $G$ 的阴影图 $D_{2} (G)$ 是通过 $G$ 的两个复制 $G'$ 和 $G''$ 得到的， $G'$ 中的顶点 $v'$ 需与其 $G''$ 中对应点 $v''$ 的邻点连接。图 $G$ 的CDC图是 $G$ 与 $K_{2}$ 的直积，即 $C D C (G) = G \times K_{2}$ [1] 。矩阵的可交换性问题是Cayley首先在文献 [2] 中讨论的一个经典问题。我们研究图的可交换性即为讨论它们的邻接矩阵的可交换。两个图称为可交换的，如果存在一种顶点标号使得它们的邻接矩阵可交换。然而，关于图邻接矩阵的可交换性问题研究结果并不多。对于距离正则图 $G$ 来说，其邻接矩阵 $A (G)$ 与其距离图 $G_{i}$ 的邻接矩阵 $A (G_{i})$ 可交换 [3] ；Beezer [4] 刻画了所有与路 $P_{n}$ 可交换的图的性质；Akbari [5] 找到了所有使得完全二部图 $K_{n, n}$ 可以分解成可交换的完美匹配或哈密顿圈的整数。

2. 预备知识

定义2.1 [6] 矩阵的克罗内克积定义如下：设 $A$ 是一个 $m \times n$ 的矩阵，而 $B$ 是一个 $p \times q$ 的矩阵，则矩阵 $A, B$ 的克罗内克积 $A \otimes B$ 则是如下的一个 $m p \times n q$ 的分块矩阵：

$A \otimes B = [\begin{matrix} a_{11} B & \dots & a_{1 n} B \\ ⋮ & ⋱ & ⋮ \\ a_{m 1} B & \dots & a_{m n} B \end{matrix}]$ 。

定理2.1 [7] 设 $A$ ， $C$ 均为 $m$ 阶方阵； $B$ ， $D$ 均为 $n$ 阶方阵。若 $A C = C A$ ， $B D = D B$ 则 $(A \otimes B) (C \otimes D) = (C \otimes D) (A \otimes B)$ 。

定理2.2 [8] 正则图的邻接矩阵与 $J$ 可交换。

3. 从可交换图出发构造新的可交换图

定理3.1图 $G_{1}$ 与图 $G_{2}$ 可交换，即 $A (G_{1}) A (G_{2}) = A (G_{2}) A (G_{1})$ 。则有：

1) 图 $G_{1}$ 的分裂图与图 $G_{2}$ 的分裂图可交换；

2) 图 $G_{1}$ 的阴影图与图 $G_{2}$ 的阴影图可交换；

3) 图 $G_{1}$ 的CDC图与图 $G_{2}$ 的CDC图可交换。

证明：

1) 由分裂图的定义知，图 $G_{1}$ 的分裂图与图 $G_{2}$ 的分裂图的邻接矩阵分别为

$A (S' (G_{1})) = (\begin{matrix} A (G_{1}) & A (G_{1}) \\ A (G_{1}) & 0 \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \otimes A ( G 1 )$

$A (S' (G_{2})) = (\begin{matrix} A (G_{2}) & A (G_{2}) \\ A (G_{2}) & 0 \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \otimes A ( G 2 )$

因为，图 $G_{1}$ 与图 $G_{2}$ 可交换，即 $A (G_{1}) A (G_{2}) = A (G_{2}) A (G_{1})$ ，所以由定理2.1易得

$A (S' (G_{1})) A (S' (G_{2})) = A (S' (G_{2})) A (S' (G_{1}))$ 。

2) 由阴影图的定义知，图 $G_{1}$ 的阴影图与图 $G_{2}$ 的阴影图的邻接矩阵分别为

$A (D_{2} (G_{1})) = (\begin{matrix} A (G_{1}) & A (G_{1}) \\ A (G_{1}) & A (G_{1}) \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) \otimes A ( G 1 )$

$A (D_{2} (G_{2})) = (\begin{matrix} A (G_{2}) & A (G_{2}) \\ A (G_{2}) & A (G_{2}) \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) \otimes A ( G 2 )$

因为图 $G_{1}$ 与图 $G_{2}$ 可交换，即 $A (G_{1}) A (G_{2}) = A (G_{2}) A (G_{1})$ ，所以由定理2.1易得

$A (D_{2} (G_{1})) A (D_{2} (G_{2})) = A (D_{2} (G_{2})) A (D_{2} (G_{1}))$ 。

3) 由CDC图的定义知，图 $G_{1}$ 的CDC图与图 $G_{2}$ 的CDC图的邻接矩阵分别为

$A (C D C (G_{1})) = (\begin{matrix} 0 & A (G_{1}) \\ A (G_{1}) & 0 \end{matrix}) = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) \otimes A ( G 1 )$

$A (C D C (G_{2})) = (\begin{matrix} 0 & A (G_{2}) \\ A (G_{2}) & 0 \end{matrix}) = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) \otimes A ( G 2 )$

因为图 $G_{1}$ 与图 $G_{2}$ 可交换，即 $A (G_{1}) A (G_{2}) = A (G_{2}) A (G_{1})$ ，所以由定理2.1易得

$A (C D C (G_{1})) A (C D C (G_{2})) = A (C D C (G_{2})) A (C D C (G_{1}))$

定理3.2图 $G_{1}$ 与图 $G_{2}$ 均为 $n$ 阶正则图，且图 $G_{1}$ 与图 $G_{2}$ 可交换，即 $A (G_{1}) A (G_{2}) = A (G_{2}) A (G_{1})$ 。则 $G_{1} \nabla G_{1}$ 与 $G_{2} \nabla G_{2}$ 可交换。

证明：由联图的定义知，图 $G_{1} \nabla G_{1}$ 与图 $G_{2} \nabla G_{2}$ 的邻接矩阵分别为

， $A (G_{2} \nabla G_{2}) = (\begin{matrix} A (G_{2}) & J \\ J & A (G_{2}) \end{matrix})$

所以有

$\begin{array}{l} A (G_{1} \nabla G_{1}) A (G_{2} \nabla G_{2}) = (\begin{matrix} A (G_{1}) & J \\ J & A (G_{1}) \end{matrix}) (\begin{matrix} A (G_{2}) & J \\ J & A (G_{2}) \end{matrix}) \\ = (\begin{matrix} A (G_{1}) A (G_{2}) + J^{2} & A (G_{1}) J + J A (G_{2}) \\ J A (G_{2}) + A (G_{1}) J & J^{2} + A (G_{1}) A (G_{2}) \end{matrix}) \end{array}$ ，

$\begin{array}{l} A (G_{2} \nabla G_{2}) A (G_{1} \nabla G_{1}) = (\begin{matrix} A (G_{2}) & J \\ J & A (G_{2}) \end{matrix}) (\begin{matrix} A (G_{1}) & J \\ J & A (G_{1}) \end{matrix}) \\ = (\begin{matrix} A (G_{2}) A (G_{1}) + J^{2} & A (G_{2}) J + J A (G_{1}) \\ J A (G_{1}) + A (G_{2}) J & J^{2} + A (G_{2}) A (G_{1}) \end{matrix}) \end{array}$ 。

因为图 $G_{1}$ 与图 $G_{2}$ 可交换，即 $A (G_{1}) A (G_{2}) = A (G_{2}) A (G_{1})$ ，又因为图 $G_{1}$ 与图 $G_{2}$ 均为 $n$ 阶正则图，由定理2.2，所以 $J A (G_{1}) = A (G_{1}) J, J A (G_{2}) = A (G_{2}) J$ 。易得

$A (G_{1} \nabla G_{1}) A (G_{2} \nabla G_{2}) = A (G_{2} \nabla G_{2}) A (G_{1} \nabla G_{1})$ 。

为了说明定理3.1和定理3.2，我们给出以下例子。

例3.1设图与图 $G_{2}$ 均为4阶正则图，且图 $G_{1}$ 与图 $G_{2}$ 可交换(见图1)。我们可以根据定义得到 $S' (G_{1}) 、 S' (G_{2}) 、 D_{2} (G_{1}) 、 D_{2} (G_{2}) 、 C D C (G_{1}) 、 C D C (G_{2})$ 以及 $G_{1} \nabla G_{1}$ 、 $G_{2} \nabla G_{2}$ 的图(见图2~5)及其所对应的邻接矩阵(见表1)。容易验证其中的可交换性与上述定理符合。

Figure 1. A pair of regular commutative graphs $G_{1}$ and $G_{2}$

图1. 一对正则可交换图 $G_{1}$ 与 $G_{2}$

Figure 2. The splitting graphs $S' (G_{1})$ and $S' (G_{2})$ of commutative graphs $G_{1}$ and $G_{2}$

图2. 可交换图 $G_{1}$ 与 $G_{2}$ 的分裂图 $S' (G_{1})$ 和 $S' ( G 2 )$

Figure 3. The shadow graphs $D_{2} (G_{1})$ and $D_{2} (G_{2})$ of commutative graphs $G_{1}$ and $G_{2}$

图3. 可交换图 $G_{1}$ 与 $G_{2}$ 的阴影图 $D_{2} (G_{1})$ 和 $D_{2} ( G 2 )$

Figure 4. The CDC graphs $C D C (G_{1})$ and $C D C (G_{2})$ of commutative graphs $G_{1}$ and $G_{2}$

图4. 可交换图 $G_{1}$ 与 $G_{2}$ 的CDC图 $C D C (G_{1})$ 和 $C D C ( G 2 )$

Figure 5. The joint graphs $G_{1} \nabla G_{1}$ and $G_{2} \nabla G_{2}$ of commutative graphs $G_{1}$ and $G_{2}$

图5. 可交换图 $G_{1}$ 与 $G_{2}$ 的联图 $G_{1} \nabla G_{1}$ 和 $G_{2} \nabla G_{2}$

Table 1. The adjacency matrix of graphs

表1. 图的邻接矩阵

4. 结语

可交换图的构造的刻画及性质研究对于可交换图问题的推进具有重要意义，我们利用图的克罗内克积和图的联运算，给出一些构造新的可交换图的方法，并给出了具体的实例。后续将利用此方法，研究构造可交换图的充分条件。

参考文献

[1]	Sciriha, I. and Collins, L. (2020) The Walks and CDC of Graphs with the Same Main Eigenspace. Discussiones Mathematicae Graph Theory, 44, 1-3.
[2]	Cayley, A. (1858) A Memoir on the Theory of Matrices. Philosophical Transactions of the Royal Society of London, 148, 17-37.
[3]	Biggs, N.L. (1974) Algebraic Graph Theory. Cambridge U.P., Cambridge. https://doi.org/10.1017/CBO9780511608704
[4]	Beezer, R.A. (1984) On the Polynomial of a Path. Linear Algebra and Its Applications, 63, 221-225. https://doi.org/10.1016/0024-3795(84)90144-7
[5]	Akbari, S., Moazami, F. and Mohammadian, A. (2009) Commutativity of the Adjacency Matrices of Graphs. Discrete Mathematics, 309, 595-600. https://doi.org/10.1016/j.disc.2008.09.006
[6]	Graham, A. (2018) Kronecker Products and Matrix Calculus with Applications. Courier Dover Publications, Chichester.
[7]	吴寒, 刘奋进, 等. 可交换图的一些注记[J]. 浙江大学学报(理学版), 2024, 51(2): 3-4.
[8]	Cvetković, D.M., Rowlinson, P. and Simić, S. (2010) An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511801518

为你推荐

友情链接