一类连图的Yamada多项式的性质

doi:10.12677/AAM.2021.108290

期刊菜单

一类连图的Yamada多项式的性质
The Properties of Yamada Polynomials of a Class of Connected Graphs

DOI: 10.12677/AAM.2021.108290, PDF, HTML, XML, 下载: 298 浏览: 436
作者: 王璐：辽宁师范大学，辽宁大连
关键词: Yamada多项式；不变量；连图；Yamada Polynomial； Invariant； Connected Graph

摘要: Yamada多项式是图论中重要的不变量之一。本文主要研究了一类特殊空间图的多项式不变量的性质，在两点连图性质的基础上，通过利用Yamada多项式非环边的性质，给出了特殊的两点连图(l,n)与图(m,n)的Yamada多项式，进一步推广到一类特殊的三点连图的情形，研究了这类连图的Yamada多项式并给出了其推导公式。

Abstract: Yamada polynomial is one of the important invariants in graph theory. This paper mainly studies the properties of the polynomial invariants of a special type of space graph. Based on the properties of the two-point connected graph, by using the non-circular edge property of the Yamada polynomial, the Yamada polynomial of special two-point connected graph (l,n) and (m,n) is given. Yamada polynomials are further extended to a special type of three-point connected graphs. The Yamada polynomials of this type of connected graphs are studied and their derivation formulas are given.

文章引用：王璐. 一类连图的Yamada多项式的性质[J]. 应用数学进展, 2021, 10(8): 2784-2793. https://doi.org/10.12677/AAM.2021.108290

1. 引言

图论可以看作是对纽结理论的一种推广，它也是拓扑学领域中的重要组成部分，图的等价分类问题在图论中具有十分重要的地位与作用，而图的多项式作为图的不变量已经被国内外许多专家学者在各方面进行了深入的研究，这为图论奠定了坚实的基础。Yamada多项式作为图论中重要的多项式不变量，与chromatic多项式 [1] 之间有着紧密的联系。

本文主要研究一类特殊连图的Yamada多项式。在预备知识部分我们将介绍图论及图的Yamada多项式的一些基本概念；在第二部分我们将主要介绍图的Yamada多项式的性质；第三部分根据两点连图的性质，计算出了特殊连图(1, n)与图(m, n)的Yamada多项式，最后，通过研究计算得到了一类特殊的三点连图Yamada多项式的具体表达式。

2. 预备知识

2.1. 图的基本概念

定义2.1 [2] 图G是指一个有序三元组 $(V (G), E (G), ψ (G))$ ，其中 $V (G)$ 是图G的顶点集， $E (G)$ 是图G的边集且 $E (G) \cap V (G) = ϕ$ ， $ψ_{G}$ 是关联函数，它将G的每条边对应于G的无序顶点对(可以是相同顶点)。若边e和两个顶点u和v满足 $ψ_{G} (e) = u v$ ，则称边e联结顶点u和v，顶点u和v称为边e的端点。

注释2.1 以后为了方便，分别用V和E表示图G的边集和顶点集。

注释2.2 如果有一条边连接相同的顶点，那么我们称这样的边为环(loop)。

2.2. 洛朗多项式的定义

定义2.2 [3] 图 $G = (V, E)$ ，V是G的顶点集，E是G的边集。 $μ (G)$ 和 $β (G)$ 分别表示图的连通分支数和一维Betti数。且 $f (G) = x^{μ (G)} y^{β (G)}$ ， $h (G)$ 是一个2-洛朗多项式：

$h (G) = h (G) (x, y) = \sum_{F \subset E} {(- x)}^{- | F |} f (G - F)$

注释2.3 F是E的子集， $| F |$ 是F包含元素的数目， $G - F = (V, E - F)$ 且x和y是不定元，定义 $h (ϕ) = 1$ 。且 $G - F = (V, G - F)$ 。

2.3. Yamada多项式的定义

定义2.3 [3] 将 $x = - 1$ 和 $y = - A - 2 - A^{- 1}$ 代入到多项式 $h (G) (x, y)$ 中，我们就得到一个多项式 $H (G) (A)$ ：

$H (G) (A) = h (G) (- 1, - A - 2 - A^{- 1})$

称 $H (G) (A)$ 为图G的Yamada多项式。

2.4. 两点连图的定义

定义2.4 [4] 若 $u_{1}, v_{1}$ 为图G中的两个点， $u_{2}, v_{2}$ 为图H中的两个点，将 $u_{1}$ 和 $u_{2}$ 粘合成一个新的顶点u，再将 $v_{1}$ 和 $v_{2}$ 粘合成一个新的顶点v，得到一个新图 $G : H$ ，称图 $G : H$ 为G和H的两点连图。

3. Yamada多项式的性质

$G / e$ 为收缩边e得到的图， $G - e$ 为删除边e得到的图。

给定两个图 $G_{1}$ 和 $G_{2}$ ， $G_{1} \cup G_{2}$ 表示图 $G_{1}$ 和 $G_{2}$ 的不交并， $G_{1} \cdot G_{2}$ 表示图 $G_{1}$ 和 $G_{2}$ 的一点并。我们称G有一割边e，如果 $G - e$ 比G有更多的连通分支数。

性质3.1 [1] $H (\cdot) = - 1$ 。

证明：由于 $h (\cdot) = {(- x)}^{0} x y^{0} = x$ ，

因此 $H (\cdot) = h (\cdot) (- 1, - A - 2 - A^{- 1}) = - 1$ 。

性质3.2 [1] 如果图G有一条割边，则 $H (G) = 0$ 。

证明：设e是G的割边，则 $G - e = G_{1} \cup G_{2}$ ， $G / e = G_{1} \cdot G_{2}$ ，由 $h (G)$ 的性质得，

$\begin{matrix} h (G) = h (G / e) - \frac{1}{x} h (G - e) \\ = h (G_{1} \cdot G_{2}) - \frac{1}{x} h (G_{1} \cup G_{2}) \\ = \frac{1}{x} h (G_{1}) h (G_{2}) - \frac{1}{x} h (G_{1}) h (G_{2}) \\ = 0 \end{matrix}$

因此 $H (G) = 0$ 。

性质3.3 [1] $H (G) = - (A + 1 + A^{- 1}) H (G - e)$ ，e是环边。

证明：记 $G - e = G^{'}$ ， $F - e = F^{'}$ ，那么 $| F | = | F^{'} | + 1$ ， $μ (G^{'} - F) = μ (G - F)$ ， $1 + β (G^{'} - F) = β (G - F)$ ，则

$\begin{matrix} h (G) = \sum_{e \notin F \subset E} {(- x)}^{- | F |} x^{μ (G - F)} y^{β (G - F)} + \sum_{e \in F \subset E} {(- x)}^{- | F |} x^{μ (G - F)} y^{β (G - F)} \\ = \sum_{F \subset E - e} {(- x)}^{- | F |} x^{μ (G^{'} - F)} y^{β (G^{'} - F) + 1} + \sum_{F^{'} \subset E - e} {(- x)}^{- | F^{'} | - 1} x^{μ (G^{'} - F^{'})} y^{β (G^{'} - F^{'})} \\ = y \sum_{F \subset E - e} {(- x)}^{- | F |} x^{μ (G^{'} - F)} y^{β (G^{'} - F)} - \frac{1}{x} \sum_{F^{'} \subset E - e} {(- x)}^{- | F^{'} |} x^{μ (G^{'} - F^{'})} y^{β (G^{'} - F^{'})} \\ = y h (G - e) - \frac{1}{x} h (G - e) \end{matrix}$

因此 $H (G) = (- A - 2 - A^{- 1}) H (G - e) + H (G - e) = - (A + 1 + A^{- 1}) H (G - e)$ 。

性质3.4 [1] $H (G) = H (G / e) + H (G - e)$ ，e是非环边。

证明：记 $G - e = G^{'}$ ， $F - e = F^{'}$ ，那么 $| F | = | F^{'} | + 1$ ，则

$\begin{matrix} h (G) = \sum_{e \notin F \subset E} {(- x)}^{- | F |} x^{μ (G - F)} y^{β (G - F)} + \sum_{e \in F \subset E} {(- x)}^{- | F |} x^{μ (G - F)} y^{β (G - F)} \\ = \sum_{F \subset E - e} {(- x)}^{- | F |} x^{μ (G / e - F)} y^{β (G / e - F)} + \sum_{F^{'} \subset E - e} {(- x)}^{- | F^{'} | - 1} x^{μ (G^{'} - F^{'})} y^{β (G^{'} - F^{'})} \\ = \sum_{F \subset E - e} {(- x)}^{- | F |} x^{μ (G / e - F)} y^{β (G / e - F)} - \frac{1}{x} \sum_{F^{'} \subset E - e} {(- x)}^{- | F^{'} |} x^{μ (G^{'} - F^{'})} y^{β (G^{'} - F^{'})} \\ = h (G / e) - \frac{1}{x} h (G - e) \end{matrix}$

因此 $H (G) = H (G / e) + H (G - e)$ 。

性质3.5 [1] $H (G_{1} \cup G_{2}) = H (G_{1}) H (G_{2})$ 。

证明：记 $F = F_{1} \cup F_{2}$ ， $E = E_{1} \cup E_{2}$ ，且 $F_{1} \subset E_{1} \subset G_{1}$ ， $F_{2} \subset E_{2} \subset G_{2}$ ，那么 $μ (G_{1} \cup G_{2}) = μ (G_{1}) + μ (G_{2})$ ， $β (G_{1} \cup G_{2}) = β (G_{1}) + β (G_{2})$ ，则

$\begin{matrix} h (G_{1}) h (G_{2}) = \sum_{F_{1} \subset E_{1} \subset E} {(- x)}^{- | F_{1} |} x^{μ (G_{1} - F_{1})} y^{β (G_{1} - F_{1})} \cdot \sum_{F_{2} \subset E_{2} \subset E} {(- x)}^{- | F_{2} |} x^{μ (G_{2} - F_{2})} y^{β (G_{2} - F_{2})} \\ = \sum_{F_{1} 、 F_{2} \subset E} {(- x)}^{- | F_{1} | - | F_{2} |} x^{μ (G_{1} - F_{1}) + μ (G_{2} - F_{2})} y^{β (G_{1} - F_{1}) + β (G_{2} - F_{2})} \\ = \sum_{F_{1} 、 F_{2} \subset E} {(- x)}^{- | F_{1} | - | F_{2} |} x^{μ (G_{1} \cup G_{2} - F_{1} \cup F_{2})} y^{β (G_{1} \cup G_{2} - F_{1} \cup F_{2})} \\ = h (G_{1} \cup G_{2}) \end{matrix}$

因此 $H (G_{1} \cup G_{2}) = H (G_{1}) H (G_{2})$ 。

性质3.6 [1] $H (G_{1} \cdot G_{2}) = - H (G_{1}) H (G_{2})$ 。

证明：记 $F = F_{1} \cup F_{2}$ ， $E = E_{1} \cup E_{2}$ ，且 $F_{1} \subset E_{1} \subset G_{1}$ ， $F_{2} \subset E_{2} \subset G_{2}$ ，那么 $μ (G_{1} \cup G_{2} - F) - 1 = μ (G_{1} \cdot G_{2} - F)$ ， $β (G_{1} \cup G_{2} - F) = β (G_{1} \cdot G_{2} - F)$ ，则

$\begin{matrix} h (G_{1} \cdot G_{2}) = \sum_{F \subset E} {(- x)}^{- | F |} x^{μ (G_{1} \cdot G_{2} - F)} y^{β (G_{1} \cdot G_{2} - F)} \\ = \sum_{F \subset E} {(- x)}^{- | F |} x^{μ (G_{1} \cup G_{2} - F) - 1} y^{β (G_{1} \cup G_{2} - F)} \\ = \sum_{F_{1} \subset E_{1}} \sum_{F_{2} \subset E_{2}} {(- x)}^{- | F_{1} | - | F_{2} |} x^{μ (G_{1} - F_{1}) + μ (G_{2} - F_{2}) - 1} y^{β (G_{1} - F_{1}) + β (G_{2} - F_{2})} \\ = \frac{1}{x} \sum_{F_{1} \subset E_{1}} {(- x)}^{- | F_{1} |} x^{μ (G_{1} - F_{1})} y^{β (G_{1} - F_{1})} \cdot \sum_{F_{2} \subset E_{2}} {(- x)}^{- | F_{2} |} x^{μ (G_{2} - F_{2})} y^{β (G_{2} - F_{2})} \\ = \frac{1}{x} h (G_{1}) \cdot h ( G 2 ) \end{matrix}$

因此 $H (G_{1} \cdot G_{2}) = - H (G_{1}) H (G_{2})$ 。

4. 一类连图的Yamada多项式的性质

4.1. 两点连图Yamada多项式的性质

定理4.1 [1] 图 $G_{1}$ 和 $G_{2}$ 有两个公共顶点u和v， $G_{1} : G_{2}$ 表示图 $G_{1}$ 和 $G_{2}$ 的两点并， $K_{1}$ 和 $K_{2}$ 分别是粘接图 $G_{1}$ 和 $G_{2}$ 的顶点u和v得到的图，则

$H (G_{1} : G_{2}) = \frac{1}{σ} [H (K_{1}) H (K_{2}) + (σ + 1) H (G_{1}) H (G_{2}) + H (K_{1}) H (G_{2}) + H (K_{2}) H (G_{1})]$

4.2. 图 $(1, n)$ 的Yamada多项式的性质

定义4.1 [5] 给定两个图G，K， $u_{1}$ ， $v_{1}$ 是图G的任意两个顶点， $u_{2}$ ， $v_{2}$ 是图K的任意两个顶点，将顶点 $u_{1}$ ， $u_{2}$ 用一条边连接起来， $v_{1}$ ， $v_{2}$ 用n条边连接起来，如图1所示，所得到的图记作 $(1, n)$ ， $n \geq 1$ 。

定理4.2 对于图 $(1, n)$ ， $n \geq 1$ ，有

$H ((1, n)) = - (\frac{1 - {(- σ)}^{n}}{1 + σ}) H_{G} H_{K} + (\frac{1 - {(- σ)}^{n}}{1 + σ}) H (G : K)$

Figure 1. Figure $(1, n)$

图1. 图 $(1, n)$

其中： $H_{G}$ ， $H_{K}$ 分别为图G，K的Yamada多项式； $H (G : K)$ 为图G，K的两点并的Yamada多项式， $σ = A + 1 + A^{- 1}$ 。

证明：利用性质3.4，对图 $(1, n)$ 的n条边中的一条边进行缩边减边的运算，再对 $n - 1$ 条边进行缩边减边的运算，以此类推，那么有等式

$H ((1, n)) = H ((1, n - 1)) + H (K_{n - 1})$

成立，其中 $H (K_{n - 1}) = {(- σ)}^{n - 1} H (F)$ ，则

$H ((1, n)) = H ((1, n - 1)) + {(- σ)}^{n - 1} H (F)$ (1)

由(1)式可知，

$H ((1, n)) = H ((1, n - 1)) + {(- σ)}^{n - 1} H ( F )$

$H ((1, n - 1)) = H ((1, n - 2)) + {(- σ)}^{n - 2} H ( F )$

$H ((1, n - 2)) = H ((1, n - 3)) + {(- σ)}^{n - 3} H ( F )$

$⋮$

$H ((1, 2)) = H ((1, 1)) + {(- σ)}^{1} H ( F )$

$H ((1, 1)) = H ((1, 0)) + {(- σ)}^{0} H ( F )$

所以

$H ((1, n)) = H ((1, 0)) + (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) H (F)$ (2)

另外 $H (F) = - H_{G} H_{K} + H (G : K)$ ，将其代入到(2)中，得

$H ((1, n)) = - (\frac{1 - {(- σ)}^{n}}{1 + σ}) H_{G} H_{K} + (\frac{1 - {(- σ)}^{n}}{1 + σ}) H (G : K)$

其中图 $K_{n - 1}$ ，F如图2所示。

4.3. 图 $(m, n)$ 的Yamada多项式的性质

定义4.2 [5] 给定两个图G，K， $u_{1}$ ， $v_{1}$ 是图G的任意两个顶点， $u_{2}$ ， $v_{2}$ 是图K的任意两个顶点，若顶点 $u_{1}$ ， $u_{2}$ 用m条边连接起来， $v_{1}$ ， $v_{2}$ 用n条边连接起来，如图3所示，所得到的图记作 $(m, n)$ ，且 $m, n \geq 1$ 。

$K_{n - 1}$ $F$

Figure 2. $K_{n - 1}$ , F

图2. $K_{n - 1}$ ，F

Figure 3. $(m, n)$

图3. $(m, n)$

定理4.3 对于图 $(m, n)$ ， $m, n \geq 1$ ，有

$H ((m, n)) = - (\frac{1 - {(- σ)}^{n} + (- σ) (1 - {(- σ)}^{m - 1})}{1 + σ}) H_{G} H_{K} + \frac{(1 - {(- σ)}^{n}) (1 - {(- σ)}^{m})}{{(1 + σ)}^{2}} H (G : K)$

其中： $H_{G}$ ， $H_{K}$ 分别为图G，K的Yamada多项式； $H (G : K)$ 为图G，K的两点并的Yamada多项式， $σ = A + 1 + A^{- 1}$ 。

证明：首先利用性质3.4，对图 $(m, n)$ 的m条边其中的一条边进行缩边减边运算，得到图 $(G \cup_{n} K)$ ，再对图 $(G \cup_{n} K)$ 的n条边进行运算，其次对 $m - 1$ 条边进行缩边减边运算，以此类推，那么有等式

$H ((m, n)) = H ((m - 1, n)) + H (E_{m - 1})$

成立，其中 $H (E_{m - 1}) = {(- σ)}^{m - 1} H (G \cup_{n} K)$ ，则

$\begin{matrix} H ((m, n)) = H ((m - 1, n)) + {(- σ)}^{m - 1} H (G \cup_{n} K) \\ = H ((m - 1, n)) + {(- σ)}^{m - 1} H (G \cup_{n - 1} K) + {(- σ)}^{m - 1} H (F_{n - 1}) \end{matrix}$

且 $H (F_{n - 1}) = {(- σ)}^{n - 1} H (G : K)$ ，代入上式中得

$H ((m, n)) = H ((m - 1, n)) + {(- σ)}^{m - 1} H (G \cup_{n - 1} K) + {(- σ)}^{m - 1} {(- σ)}^{n - 1} H (G : K)$ (3)

另外有

$H (G \cup_{n - 1} K) = H (G \cup_{n - 2} K) + {(- σ)}^{n - 2} H (G : K)$

$H (G \cup_{n - 2} K) = H (G \cup_{n - 3} K) + {(- σ)}^{n - 3} H (G : K)$

$H (G \cup_{n - 3} K) = H (G \cup_{n - 4} K) + {(- σ)}^{n - 4} H (G : K)$

$⋮$

$H (G \cup_{2} K) = H (G \cup_{1} K) + {(- σ)}^{1} H (G : K)$

$H (G \cup_{1} K) = - H_{G} H_{K} + H (G : K)$

综上所述我们得到

$H (G \cup_{n - 1} K) = - H_{G} H_{K} + (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 2}) H (G : K)$

将其代入(3)式可得

$H ((m, n)) = H ((m - 1, n)) - {(- σ)}^{m - 1} H_{G} H_{K} + {(- σ)}^{m - 1} (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) H (G : K)$

$H ((m - 1, n)) = H ((m - 2, n)) - {(- σ)}^{m - 2} H_{G} H_{K} + {(- σ)}^{m - 2} (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) H (G : K)$

$⋮$

$H ((2, n)) = H ((1, n)) - {(- σ)}^{1} H_{G} H_{K} + {(- σ)}^{1} (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) H (G : K)$

$H ((1, n)) = - (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) H_{G} H_{K} + (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) H (G : K)$

由此我们可以得到

$\begin{matrix} H ((m, n)) = - (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1} + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{m - 1}) H_{G} H_{K} \\ + (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{n - 1}) (1 + {(- σ)}^{1} + {(- σ)}^{2} + \dots + {(- σ)}^{m - 1}) H (G : K) \\ = - (\frac{1 - {(- σ)}^{n} + (- σ) (1 - {(- σ)}^{m - 1})}{1 + σ}) H_{G} H_{K} + \frac{(1 - {(- σ)}^{n}) (1 - {(- σ)}^{m})}{{(1 + σ)}^{2}} H (G : K) \end{matrix}$

其中图 $E_{m - 1}$ ， $G \cup_{n} K$ ， $F_{n - 1}$ 如图4所示。

$E_{m - 1}$ $G \cup_{n} K$ $F_{n - 1}$

Figure 4. $E_{m - 1}$ , $G \cup_{n} K$ , $F_{n - 1}$

图4. $E_{m - 1}$ ， $G \cup_{n} K$ ， $F_{n - 1}$

4.4. 一类三点连图Yamada多项式的性质

定理4.4 给定两个图 $G_{1}$ 和 $G_{2}$ ， $G_{1} ⋮ G_{2}$ 表示图 $G_{1}$ 和 $G_{2}$ 的三点连图，其中顶点 $u, v, w \subseteq G_{1}$ ， $u^{'}, v^{'}, w^{'} \subseteq G_{2}$ ，设图 $G_{1}$ 中的顶点u与w，v与w之间无边且无环边，图 $G_{2}$ 中的顶点 $u^{'}$ 与 $w^{'}$ ， $v^{'}$ 与 $w^{'}$ 之间无边且无环边。 $k_{1}, k_{2}, k_{3}, k_{0}$ 及 ${k^{'}}_{1}, {k^{'}}_{2}, {k^{'}}_{3}, {k^{'}}_{0}$ 分别为粘接图 $G_{1}$ 和 $G_{2}$ 的顶点u与v，u与w，v与w， $u, v, w$ 及 $u^{'}$ 与 $v^{'}$ ， $u^{'}$ 与 $w^{'}$ ， $v^{'}$ 与 $w^{'}$ ， $u^{'}, v^{'}, w^{'}$ 得到的图，则

$\begin{matrix} H (G_{1} ⋮ G_{2}) = - \frac{1}{σ^{2}} [H (k_{0}) H ({k^{'}}_{0}) + (σ + 1) H (k_{1}) H ({k^{'}}_{1}) + H (k_{0}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1}) \\ + H (k_{2}) H ({k^{'}}_{0}) + (σ + 1) H (G_{1}) H ({k^{'}}_{1}) + H (k_{2}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1}) \\ + σ (σ + 1) H (G_{1}) H (G_{2}) + σ H (k_{1}) H (G_{2})] \end{matrix}$ (4)

证明：令 $G = G_{1} ⋮ G_{2}$ ， $p (G)$ ， $q (G)$ 分别表示图G的顶点个数与边的个数，下面通过对图G的边数 $q (G)$ 用归纳法来证明这一定理。

若 $q (G) = 0$ ，那么 $G_{1}$ 和 $G_{2}$ 都是由孤立顶点组成。假设 $p (G_{1}) = p_{1} \geq 3$ ， $p (G_{2}) = p_{2} \geq 3$ ，则G是由 $p_{1} + p_{1} - 3$ 个孤立点组成的图。由性质3.1和性质3.5，得 $H (G) = {(- 1)}^{p_{1} + p_{2} - 3}$ 。

又因为 $p (k_{1}) = p_{1} - 1$ ， $p (k_{2}) = p_{1} - 1$ ， $p (k_{3}) = p_{1} - 1$ ， $p (k_{0}) = p_{1} - 2$ ， $p ({k^{'}}_{1}) = p_{2} - 1$ ， $p ({k^{'}}_{2}) = p_{2} - 1$ ， $p ({k^{'}}_{3}) = p_{2} - 1$ ， $p ({k^{'}}_{0}) = p_{2} - 2$ ，将其带入等式(4)的右边有：

$\begin{matrix} H (G_{1} ⋮ G_{2}) = - \frac{1}{σ^{2}} [{(- 1)}^{p_{1} - 2} {(- 1)}^{p_{2} - 2} + (σ + 1) {(- 1)}^{p_{1} - 1} {(- 1)}^{p_{2} - 1} + {(- 1)}^{p_{1} - 2} {(- 1)}^{p_{2} - 1} + {(- 1)}^{p_{2} - 2} {(- 1)}^{p_{1} - 1} \\ + {(- 1)}^{p_{1} - 1} {(- 1)}^{p_{2} - 2} + (σ + 1) {(- 1)}^{p_{1}} {(- 1)}^{p_{2} - 1} + {(- 1)}^{p_{1} - 1} {(- 1)}^{p_{2} - 1} + {(- 1)}^{p_{2} - 2} {(- 1)}^{p_{1}} \\ + σ (σ + 1) {(- 1)}^{p_{1}} {(- 1)}^{p_{2}} + σ {(- 1)}^{p_{1} - 1} {(- 1)}^{p_{2}}] \\ = {(- 1)}^{p_{1} + p_{2} - 3} \end{matrix}$

因此等式(4)成立。

现在假设当 $q (G) < k$ 时，定理4.4成立，其中 $k \geq 1$ 。那么我们不妨设 $q (G) = k$ ，图 $G = G_{1} ⋮ G_{2}$ ，e为图G的一条边，我们不妨假设 $e \in E (G_{1})$ 。我们分两种情况进行讨论：

情况1. e是不连接顶点 $u, v$ 的边，那么e为 $k_{1}$ 的一条非环边。因此，

$\begin{matrix} H (G / e) = H ((G_{1} / e) ⋮ G_{2}) \\ = - \frac{1}{σ^{2}} [H (k_{0} / e) H ({k^{'}}_{0}) + (σ + 1) H (k_{1} / e) H ({k^{'}}_{1}) + H (k_{0} / e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1} / e) \\ + H (k_{2} / e) H ({k^{'}}_{0}) + (σ + 1) H (G_{1} / e) H ({k^{'}}_{1}) + H (k_{2} / e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1} / e) \\ + σ (σ + 1) H (G_{1} / e) H (G_{2}) + σ H (k_{1} / e) H (G_{2})] \end{matrix}$

且

$\begin{matrix} H (G - e) = H ((G_{1} - e) ⋮ G_{2}) \\ = - \frac{1}{σ^{2}} [H (k_{0} - e) H ({k^{'}}_{0}) + (σ + 1) H (k_{1} - e) H ({k^{'}}_{1}) + H (k_{0} - e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1} - e) \\ + H (k_{2} - e) H ({k^{'}}_{0}) + (σ + 1) H (G_{1} - e) H ({k^{'}}_{1}) + H (k_{2} - e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1} - e) \\ + σ (σ + 1) H (G_{1} - e) H (G_{2}) + σ H (k_{1} - e) H (G_{2})] \end{matrix}$

因此，

$\begin{matrix} H (G) = H (G / e) + H (G - e) \\ = - \frac{1}{σ^{2}} [H (k_{0} / e) H ({k^{'}}_{0}) + (σ + 1) H (k_{1} / e) H ({k^{'}}_{1}) + H (k_{0} / e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1} / e) \\ + H (k_{2} / e) H ({k^{'}}_{0}) + (σ + 1) H (G_{1} / e) H ({k^{'}}_{1}) + H (k_{2} / e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1} / e) \\ + σ (σ + 1) H (G_{1} / e) H (G_{2}) + σ H (k_{1} / e) H (G_{2}) \\ + H (k_{0} - e) H ({k^{'}}_{0}) + (σ + 1) H (k_{1} - e) H ({k^{'}}_{1}) + H (k_{0} - e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1} - e) \end{matrix}$

$\begin{array}{l} + H (k_{2} - e) H ({k^{'}}_{0}) + (σ + 1) H (G_{1} - e) H ({k^{'}}_{1}) + H (k_{2} - e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1} - e) \\ + σ (σ + 1) H (G_{1} - e) H (G_{2}) + σ H (k_{1} - e) H (G_{2})] \\ = - \frac{1}{σ^{2}} [H (k_{0}) H ({k^{'}}_{0}) + (σ + 1) H (k_{1}) H ({k^{'}}_{1}) + H (k_{0}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1}) \\ + H (k_{2}) H ({k^{'}}_{0}) + (σ + 1) H (G_{1}) H ({k^{'}}_{1}) + H (k_{2}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1}) \\ + σ (σ + 1) H (G_{1}) H (G_{2}) + σ H (k_{1}) H (G_{2})] \end{array}$

情况2. e是连接顶点 $u, v$ 的边，那么e为 $k_{1}$ 的一条环边。由性质3.3及定理4.1得

$\begin{matrix} H (G / e) = H ((k_{1} - e) : {k^{'}}_{1}) \\ = \frac{1}{σ} [H (k_{0} - e) H ({k^{'}}_{0}) + (σ + 1) H (k_{1} - e) H ({k^{'}}_{1}) + H (k_{0} - e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1} - e)] \\ = - \frac{1}{σ^{2}} [H (k_{0}) H ({k^{'}}_{0}) + (σ + 1) H (k_{1}) H ({k^{'}}_{1}) + H (k_{0}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1})] \end{matrix}$

且

$\begin{array}{l} + H (k_{2} - e) H ({k^{'}}_{0}) + (σ + 1) H (G_{1} - e) H ({k^{'}}_{1}) + H (k_{2} - e) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1} - e) \\ + σ (σ + 1) H (G_{1} - e) H (G_{2}) + σ H (k_{1} - e) H (G_{2}) + σ (σ + 1) H (G_{1} / e) H (G_{2}) \\ - σ (σ + 1) H (G_{1} / e) H (G_{2})] \\ = - \frac{1}{σ^{2}} [H (k_{2}) H ({k^{'}}_{0}) + (σ + 1) H (G_{1}) H ({k^{'}}_{1}) + H (k_{2}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1}) \\ + σ (σ + 1) H (G_{1}) H (G_{2}) + σ H (k_{1}) H (G_{2})] \end{array}$

因此，

$\begin{matrix} H (G) = H (G / e) + H (G - e) \\ = - \frac{1}{σ^{2}} [H (k_{0}) H ({k^{'}}_{0}) + (σ + 1) H (k_{1}) H ({k^{'}}_{1}) + H (k_{0}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (k_{1}) \\ + H (k_{2}) H ({k^{'}}_{0}) + (σ + 1) H (G_{1}) H ({k^{'}}_{1}) + H (k_{2}) H ({k^{'}}_{1}) + H ({k^{'}}_{0}) H (G_{1}) \\ + σ (σ + 1) H (G_{1}) H (G_{2}) + σ H (k_{1}) H (G_{2})] \end{matrix}$

定理4.4得证。

5. 结语

本文主要研究了一类特殊空间图的Yamada多项式的性质，通过利用Yamada多项式的性质，在两点连图的基础上，构造出了一类特殊的连图并给出了其具体表达式。未来还可以对空间图Yamada多项式的性质做进一步的研究。

参考文献

[1]	Li, M., Lei, F., Li, F. and Vesnin, A. (2018) The Yamada Polynomial of Spatial Graphs Obtained by Edge Replacements. Journal of Knot Theory and Its Ramifications, 27, Article ID: 1842004. https://doi.org/10.1142/S021821651842004X
[2]	Negami, S. (1987) Polynomial Invariants of Graphs. Transactions of the American Mathematical Society, 299, 601-622. https://doi.org/10.1090/S0002-9947-1987-0869224-1
[3]	Yamada, S. (1989) An Invariant of Spatial Graphs. Journal of Graph Theory, 13, 537-551. https://doi.org/10.1002/jgt.3190130503
[4]	廖云华, 谢小良. 两点连图的Tutte多项式及其应用[J]. 应用数学学报, 2016, 39(3): 393-401.
[5]	庚东雨. 一类空间图多项式的性质[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2021.

为你推荐

友情链接