一些图的边覆盖多项式的对数凹性研究

Study on Log-Concavity of Edge Covering Polynomials of Some Graphs

摘要: 本文根据不同图形的特点，通过递归的方法研究并给出了它们的边覆盖多项式，并进一步研究了这些多项式的对数凹性，主要包括蜈蚣图，毛虫图，脊椎图，爆竹图等图。

Abstract: According to the characteristics of various graphs, their edge covering polynomials are studied and given by recursive method, we further investigate the log-concavity of the graphs in question, which include centipede graphs, caterpillar graphs, vertebrate graphs and firecracker graphs and so on.

1. 介绍

单峰型问题是组合学中基本的研究课题之一，而对数凹性又是单峰型问题的重要组成部分。1989年，Stanley用多种方法证明了一个序列具有对数凹性或者单峰性，并对于每种方法给出了例子 [1]。1989年，Brenti对组合学中对数凹序列、单峰序列和Pólya频率序列进行了研究 [2]，并在1994年，更新了对代数、组合学和几何中的对数凹序列和单峰序列的研究 [3]。2014年，Brändén研究了组合学中的实根性、对数凹性和单峰性，对已经提出的一些新方法以及已经解决的问题和猜想进行了补充综述 [4]。

目前，有很多学者研究了图多项式的对数凹性。1990年，Hamidoune证明了无爪图的独立k子集数具有对数凹性，从而具有单峰性 [5]。2012年，Bahls证明了路径图的独立多项式具有对数凹性 [6]。2012年，June Huh对Read和Rota-Heron-Welsh关于色多项式系数的绝对值构成对数凹数列的猜想给与肯定答案 [7]。2016年，祝宝宣证明了一些图的团覆盖积的独立多项式具有对称性、单峰性、对数凹性和实根性，并解决了一些单峰型猜想和问题 [8]。

边覆盖多项式的概念是由Akbari和Oboudi首先提出的 [9]，他们证明了这类多项式有一些有趣的性质，发现在某种程度上，边覆盖多项式与其他著名的多项式相关，包括色多项式、匹配多项式、独立多项式、Tutte多项式等。2013年，Akbari和Oboudi刻画了所有边覆盖多项式恰好有一个或两个不同的根的图，并证明了这些多项式的根包含在{−3, 2, 1, 0}中 [9]。2011年，Csikvári和Oboudi指出，边覆盖多项式的根有一个常数界，进一步证明了如果图G的每个块是K2或一个圈，则E(G, x)的所有实根都在区间(4, 0]中 [10]。

目前，已经有学者给出了一些图的独立多项式，并进一步研究了这些多项式的单峰性 [11] [12] [13] [14]。本文我们给出一些图的边覆盖多项式并研究其对数凹性，包括蜈蚣图，毛虫图，脊椎图，爆竹图及其变化图等。下面介绍一些基本概念。

设 ${\mathcal{G}}_n$ 表示在 $\left\{1,2,\cdots ,n\right\}$ 上的所有简单标记图的集合。对于 $G\in {\mathcal{G}}_n$，图G有m条边，图G的一个边覆盖是能够使得图G的每个顶点都至少与集合中一条边相连的一组边。图G的边覆盖多项式定义为

$E\left(G,x\right)={\displaystyle {\sum }_{i=\rho \left(G\right)}^{m}e\left(G,i\right)x^i}$，

其中， $e\left(G,i\right)$ 表示边数为i的图G的边覆盖数， $\rho \left(G\right)$ 表示图G的边覆盖的最小可能数。如果图G有一个孤立的顶点，那么它的边覆盖多项式为0 [9]。

一个系数为正的多项式 ${\displaystyle {\sum }_{k=0}^n{a}_k{x}^k}$，如果存在 $m\ge 0$，使得 $a_0\le a_1\le \cdots \le a_{m-1}\le a_m\ge a_{m+1}\ge \cdots \ge a_n$，则称这个多项式具有单峰性。如果对于任意 $1\le k\le n-1$，都有 $a_k^2\ge a_{k-1}{a}_{k+1}$，则称这个多项式具有对数凹性 [15]。

2. 一些图的边覆盖多项式及其对数凹性

定义2.1 蜈蚣图 $W_n$ (见图1)是一个树图，定义为 $W_n=\left(A,B,E\right),n\ge 1$，它的顶点集是 $A\cup B$，边集是 $E=\left\{v_i{w}_i:1\le i\le n\right\}\cup \left\{v_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_i:1\le i\le n\right\}$， $A\cap B=\varnothing$。

定理2.2 蜈蚣图 $W_n$ 的边覆盖多项式为 $E\left(W_n,x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{n+i}}$。蜈蚣图 $W_n$ 的边覆盖多项式具有对

数凹性。

Figure 1. Centipede graph W_n

图1. 蜈蚣图W_n

证明：蜈蚣图 $W_n$ 共有 $\left(2n-1\right)$ 条边。点 $w_1,w_2,\cdots ,w_n$ 分别只能与点 $v_1,v_2,\cdots ,v_n$ 有边相连，显然，边 $v_1{w}_1,v_2{w}_2,\cdots ,v_n{w}_n$ 是蜈蚣图 $W_n$ 的最小边覆盖，即蜈蚣图 $W_n$ 最少被n条边覆盖。可再从剩下的 $\left(n-1\right)$ 条边中选出i条边，与这n条边形成新的边覆盖，其中， $i=0,1,\cdots ,n-1$。

因此，蜈蚣图 $W_n$ 的边覆盖多项式为 $E\left(W_n,x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{n+i}}$。

要证明蜈蚣图 $W_n$ 的边覆盖多项式的对数凹性，即证 $e_k^2\ge e_{k-1}{e}_{k+1}$，

其中， $e_k=\left(\begin{array}{c}n-1\\ k\end{array}\right),k=1,2,\cdots ,n-2$。

根据蜈蚣图 $W_n$ 的边覆盖多项式，

$e_k=\left(\begin{array}{c}n-1\\ k\end{array}\right)$, $e_{k-1}=\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$, $e_{k+1}=\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

要证 $e_k^2\ge e_{k-1}{e}_{k+1}$，

即证 ${\left(\begin{array}{c}n-1\\ k\end{array}\right)}^2\ge \left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$，

化简，得到 $\left(k+1\right)\left(n-k\right)=k\left(n-k-1\right)$，

显然得证。 □

定义2.3 由蜈蚣图 $W_n$ 定义一个毛虫图 $H_n$ (见图2)，定义为 $H_n=\left(A,B,E\right),n\ge 1$，它的顶点集是 $A\cup B$，边集是 $E=\left\{v_i{w}_{ij}:1\le i\le n,j=1,2\right\}\cup \left\{v_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,j=1,2\right\}$， $A\cap B=\varnothing$。

Figure 2. Caterpillar graph H_n

图2. 毛虫图H_n

定理2.4毛虫图 $H_n$ 的边覆盖多项式为 $E\left(H_n,x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{2n+i}}$。毛虫图 $H_n$ 的边覆盖多项式具有

对数凹性。

证明：毛虫图 $H_n$ 共有 $\left(3n-1\right)$ 条边。点 $w_{11},w_{12}$ 只能与点 $v_1$ 有边相连，点 $w_{21},w_{22}$ 只能与点 $v_2$ 有边相连， $\cdots$，点 $w_{n,1},w_{n,2}$ 只能与点 $v_n$ 有边相连，显然，边 $v_i{w}_{ij}$ 是毛虫图 $H_n$ 的最小边覆盖，其中， $1\le i\le n,j=1,2$，即毛虫图 $H_n$ 最少被2n条边覆盖。可再从剩下的 $\left(n-1\right)$ 条边中选出i条边，与这n条边形成新的边覆盖，其中， $i=0,1,\cdots ,n-1$。

因此，毛虫图 $H_n$ 的边覆盖多项式为 $E\left(H_n,x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{2n+i}}$。

由此，同定理2.2，很容易得到 $E\left(H_n,x\right)$ 的对数凹性。 □

定义2.5 由蜈蚣图 $W_n$ 定义一个脊椎图 $V_n^{\left(3\right)}$ (见图3)，定义为 $V_n^{\left(3\right)}=\left(A,B,E\right),n\ge 1$，它的顶点集是 $A\cup B$，边集是 $E=\left\{v_i{w}_{ij}:1\le i\le n,j=1,2,3\right\}\cup \left\{v_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,j=1,2,3\right\}$， $A\cap B=\varnothing$。

Figure 3. Vertebrate graph $V_n^{(\; 3\; )}$

图3. 脊椎图 $V_n^{(\; 3\; )}$

定理2.6 脊椎图 $V_n^{\left(3\right)}$ 的边覆盖多项式为 $E\left(V_n^{\left(3\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{3n+i}}$。毛虫图 $H_n$ 的边覆盖多项式具有

对数凹性。

证明：脊椎图 $V_n^{\left(3\right)}$ 共有 $\left(4n-1\right)$ 条边。点 $w_{11},w_{12},w_{13}$ 只能与点 $v_1$ 有边相连，点 $w_{21},w_{22},w_{23}$ 只能与点 $v_2$ 有边相连， $\cdots$，点 $w_{n,1},w_{n,2},w_{n,3}$ 只能与点 $v_n$ 有边相连，显然，边 $v_i{w}_{ij}$ 是脊椎图 $V_n^{\left(3\right)}$ 的最小边覆盖，其中， $1\le i\le n,j=1,2,3$，即脊椎图 $V_n^{\left(3\right)}$ 最少被3n条边覆盖。可再从剩下的 $\left(n-1\right)$ 条边中选出i条边，与这n条边形成新的边覆盖，其中， $i=0,1,\cdots ,n-1$。

因此，脊椎图 $V_n^{\left(3\right)}$ 的边覆盖多项式为 $E\left(V_n^{\left(3\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{3n+i}}$。

由此，同定理2.2，很容易得到 $E\left(V_n^{\left(3\right)},x\right)$ 的对数凹性。 □

定义2.7 由蜈蚣图 $W_n$ 定义一个脊椎图 $V_n^{\left(t\right)}$ (见图4)，定义为 $V_n^{\left(t\right)}=\left(A,B,E\right),n\ge 1$，它的顶点集是 $A\cup B$，边集是 $E=\left\{v_i{w}_{ij}:1\le i\le n,1\le j\le t\right\}\cup \left\{v_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,1\le j\le t\right\}$， $A\cap B=\varnothing$。

Figure 4. Vertebrate graph $V_n^{(\; t\; )}$

图4. 脊椎图 $V_n^{(\; t\; )}$

定理2.8 脊椎图 $V_n^{\left(t\right)}$ 的边覆盖多项式为 $E\left(V_n^{\left(t\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{tn+i}}$。脊椎图 $V_n^{\left(t\right)}$ 的边覆盖多项式具有

对数凹性。

证明：脊椎图 $V_n^{\left(t\right)}$ 共有 $\left(tn+n-1\right)$ 条边。点 $w_{11},w_{12},\cdots ,w_{1,t}$ 只能与点 $v_1$ 有边相连，点 $w_{21},w_{22},\cdots ,w_{2,t}$ 只能与点 $v_2$ 有边相连， $\cdots$，点 $w_{n,1},w_{n,2},\cdots ,w_{n,t}$ 只能与点 $v_n$ 有边相连，显然，边 $v_i{w}_{ij}$ 是是脊椎图 $V_n^{\left(t\right)}$ 的最小边覆盖，其中， $1\le i\le n,1\le j\le t$，即脊椎图 $V_n^{\left(t\right)}$ 最少被tn条边覆盖。可再从剩下的 $\left(n-1\right)$ 条边中选出i条边，与这n条边形成新的边覆盖，其中， $i=0,1,\cdots ,n-1$。

因此，脊椎图 $V_n^{\left(t\right)}$ 的边覆盖多项式为 $E\left(V_n^{\left(t\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{tn+i}}$。

由此，同定理2.2，很容易得到 $E\left(V_n^{\left(t\right)},x\right)$ 的对数凹性。 □

定义2.9 在蜈蚣图 $W_n$ 的每条边 $v_i{v}_{i+1}$ 中插入一个顶点 $u_i$，其中， $1\le i\le n-1$，得到图 $A_n^{\left(1\right)}$ (见图5)。 $A_n^{\left(1\right)}=\left(A,B,C,E\right),n\ge 1$，它的顶点集是 $A\cup B\cup C$，边集是 $E=\left\{v_i{w}_i:1\le i\le n\right\}\cup \left\{v_i{u}_i:1\le i\le n-1\right\}\cup \left\{u_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_i:1\le i\le n\right\}$， $C=\left\{u_i:1\le i\le n-1\right\}$， $A\cap B=\varnothing$， $A\cap C=\varnothing$， $B\cap C=\varnothing$。

Figure 5. Graph $A_n^{(\; 1\; )}$

图5. 图 $A_n^{(\; 1\; )}$

定理2.10 图 $A_n^{\left(1\right)}$ 的边覆盖多项式为 $E\left(A_n^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{2n-1+i}}$。图 $A_n^{\left(1\right)}$ 的边覆盖多项式具有

对数凹性。

证明：图 $A_n^{\left(1\right)}$ 共有 $\left(3n-2\right)$ 条边。点 $w_1,w_2,\cdots ,w_n$ 分别只能与点 $v_1,v_2,\cdots ,v_n$ 有边相连，显然，图 $A_n^{\left(1\right)}$ 的边覆盖一定包括边 $v_1{w}_1,v_2{w}_2,\cdots ,v_n{w}_n$。要符合边覆盖，就要再从边 $v_1{u}_1,v_2{u}_1$ 中选出 $m_1$ 条边，从边 $v_2{u}_2,v_3{u}_2$ 中选出 $m_2$ 条边， $\cdots$，从边 $v_{n-1}{u}_{n-1},v_n{u}_{n-1}$ 中选出 $m_{n-1}$ 条边，其中， $m_j=1,2$，并且， ${\displaystyle {\sum }_{j=1}^{n-1}{m}_j}=n-1+i$， $i=0,1,\cdots ,n-1$。对于每个 $m_j=1$，有两种边的选取，对于每个 $m_j=2$，只有一种边的选取，其中， $j=0,1,\cdots ,n$。因此，当 $m_1=m_2=\cdots =m_{n-1}=1$ 时，图 $A_n^{\left(1\right)}$ 有最小的边覆盖，即被 $\left(2n-1\right)$ 条边覆盖，共有 $2^{n-1}$ 种边的选取可能。再从剩下的 $\left(n-1\right)$ 条边中选出i条边，其中， $i=0,1,\cdots ,n-1$，与这n条边形成新的边覆盖，每多加一条边，边覆盖的选取可能数就要除以2。

因此，图 $A_n^{\left(1\right)}$ 的边覆盖多项式为 $E\left(A_n^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{2n-1+i}}$。

要证明图 $A_n^{\left(1\right)}$ 的边覆盖多项式的对数凹性，即证 $e_k^2\ge e_{k-1}{e}_{k+1}$，

其中， $e_k=2^{n-1-k}\left(\begin{array}{c}n-1\\ k\end{array}\right),k=1,2,\cdots ,n-2$。

根据图 $A_n^{\left(1\right)}$ 的边覆盖多项式，

$e_k=2^{n-1-k}\left(\begin{array}{c}n-1\\ k\end{array}\right)$, $e_{k-1}=2^{n-k}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$, $e_{k+1}=2^{n-2-k}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

要证 $e_k^2\ge e_{k-1}{e}_{k+1}$，

即证 $2^{2n-2-2k}\left(\begin{array}{c}n-1\\ k\end{array}\right)\left(\begin{array}{c}n-1\\ k\end{array}\right)\ge 2^{2n-2-2k}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$，

化简，得到 $\left(k+1\right)\left(n-k\right)=k\left(n-k-1\right)$，

显然得证。 □

定义2.11 在毛虫图 $H_n$ 的每条边 $v_i{v}_{i+1}$ 中插入一个顶点 ，其中， $1\le i\le n-1$，得到图 $D_{n,2}^{\left(1\right)}$ (见图6)。 $D_{n,2}^{\left(1\right)}=\left(A,B,C,E\right),n\ge 1$，它的顶点集是 $A\cup B\cup C$，边集是 $E=\left\{v_i{w}_{ij}:1\le i\le n,j=1,2\right\}\cup \left\{v_i{u}_i:1\le i\le n-1\right\}\cup \left\{u_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,j=1,2\right\}$， $C=\left\{u_i:1\le i\le n-1\right\}$， $A\cap B=\varnothing$， $A\cap C=\varnothing$， $B\cap C=\varnothing$。

Figure 6. Graph $D_{n,2}^{(\; 1\; )}$

图6. 图 $D_{n,2}^{(\; 1\; )}$

定理2.12 图 $D_{n,2}^{\left(1\right)}$ 的边覆盖多项式为 $E\left(D_{n,2}^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{3n-1+i}}$。图 $D_{n,2}^{\left(1\right)}$ 的边覆盖多项式具有

对数凹性。

证明：图 $D_{n,2}^{\left(1\right)}$ 共有 $\left(4n-2\right)$ 条边。点 $w_{11},w_{12}$ 只能与点 $v_1$ 有边相连，点 $w_{21},w_{22}$ 只能与点 $v_2$ 有边相连， $\cdots$，点 $w_{n,1},w_{n,2}$ 只能与点 $v_n$ 有边相连，显然，图 $D_{n,2}^{\left(1\right)}$ 的边覆盖一定包括边 $v_i{w}_{ij}$，其中， $1\le i\le n,j=1,2$。要符合边覆盖，就要再从边 $v_1{u}_1,v_2{u}_1$ 中选出 $m_1$ 条边，从边 $v_2{u}_2,v_3{u}_2$ 中选出 $m_2$ 条边， $\cdots$，从边 $v_{n-1}{u}_{n-1},v_n{u}_{n-1}$ 中选出 $m_{n-1}$ 条边，其中， $m_j=1,2$，并且， ${\displaystyle {\sum }_{j=1}^{n-1}{m}_j}=n-1+i$， $i=0,1,\cdots ,n-1$。对于每个 $m_j=1$，有两种边的选取，对于每个 $m_j=2$，只有一种边的选取，其中， $j=0,1,\cdots ,n$。因此，当 $m_1=m_2=\cdots =m_{n-1}=1$ 时，图 $D_{n,2}^{\left(1\right)}$ 有最小的边覆盖，即被 $\left(3n-1\right)$ 条边覆盖，共有 $2^{n-1}$ 种边的选取可能。再从剩下的 $\left(n-1\right)$ 条边中选出 条边，其中， $i=0,1,\cdots ,n-1$，与这n条边形成新的边覆盖，每多加一条边，边覆盖的选取可能数就要除以2。

因此，图 $D_{n,2}^{\left(1\right)}$ 的边覆盖多项式为 $E\left(D_{n,2}^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{3n-1+i}}$。

由此，同定理2.10，很容易得到 $E\left(D_{n,2}^{\left(1\right)},x\right)$ 的对数凹性。 □

定义2.13 在脊椎图 $V_n^{\left(t\right)}$ 的每条边 $v_i{v}_{i+1}$ 中插入一个顶点 $u_i$，其中， $1\le i\le n-1$，得到图 $D_{n,3}^{\left(1\right)}$ (见图7)。 $D_{n,3}^{\left(1\right)}=\left(A,B,C,E\right),n\ge 1$，它的顶点集是 $A\cup B\cup C$，边集是 $E=\left\{v_i{w}_{ij}:1\le i\le n,j=1,2,3\right\}\cup \left\{v_i{u}_i:1\le i\le n-1\right\}\cup \left\{u_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,j=1,2,3\right\}$， $C=\left\{u_i:1\le i\le n-1\right\}$， $A\cap B=\varnothing$， $A\cap C=\varnothing$， $B\cap C=\varnothing$。

Figure 7. Graph $D_{n,3}^{(\; 1\; )}$

图7. 图 $D_{n,3}^{(\; 1\; )}$

定理2.14 图 $D_{n,3}^{\left(1\right)}$ 的边覆盖多项式为 $E\left(D_{n,3}^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{4n-1+i}}$。图 $D_{n,3}^{\left(1\right)}$ 的边覆盖多项式具有

对数凹性。

证明：图 $D_{n,3}^{\left(1\right)}$ 共有 $\left(5n-2\right)$ 条边。点 $w_{11},w_{12},w_{13}$ 只能与点 $v_1$ 有边相连，点 $w_{21},w_{22},w_{23}$ 只能与点 $v_2$ 有边相连， $\cdots$，点 $w_{n,1},w_{n,2},w_{n,3}$ 只能与点 $v_n$ 有边相连，显然，图 $D_{n,3}^{\left(1\right)}$ 的边覆盖一定包括边 $v_i{w}_{ij}$，其中， $1\le i\le n,j=1,2,3$。要符合边覆盖，就要再从边 $v_1{u}_1,v_2{u}_1$ 中选出 $m_1$ 条边，从边 $v_2{u}_2,v_3{u}_2$ 中选出 $m_2$ 条边， $\cdots$，从边 $v_{n-1}{u}_{n-1},v_n{u}_{n-1}$ 中选出 $m_{n-1}$ 条边，其中， $m_j=1,2$，并且， ${\displaystyle {\sum }_{j=1}^{n-1}{m}_j}=n-1+i$， $i=0,1,\cdots ,n-1$。对于每个 $m_j=1$，有两种边的选取，对于每个 $m_j=2$，只有一种边的选取，其中， $j=0,1,\cdots ,n$。因此，当 $m_1=m_2=\cdots =m_{n-1}=1$ 时，图 $D_{n,3}^{\left(1\right)}$ 有最小的边覆盖，即被 $\left(4n-1\right)$ 条边覆盖，共有 $2^{n-1}$ 种边的选取可能。再从剩下的 $\left(n-1\right)$ 条边中选出i条边，其中， $i=0,1,\cdots ,n-1$，与这n条边形成新的边覆盖，每多加一条边，边覆盖的选取可能数就要除以2。

因此，图 $D_{n,3}^{\left(1\right)}$ 的边覆盖多项式为 $E\left(D_{n,3}^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{4n-1+i}}$。

由此，同定理2.10，很容易得到 $E\left(D_{n,3}^{\left(1\right)},x\right)$ 的对数凹性。 □

定义2.15 在脊椎图 $V_n^{\left(t\right)}$ 的每条边 $v_i{v}_{i+1}$ 中插入一个顶点 $u_i$，其中， $1\le i\le n-1$，得到图 $D_{n,t}^{\left(1\right)}$ (见图8)。 $D_{n,t}^{\left(1\right)}=\left(A,B,C,E\right),n\ge 1$，它的顶点集是 $A\cup B\cup C$，边集是 $E=\left\{v_i{w}_{ij}:1\le i\le n,1\le j\le t\right\}\cup \left\{v_i{u}_i:1\le i\le n-1\right\}\cup \left\{u_i{v}_{i+1}:1\le i\le n-1\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,1\le j\le t\right\}$， $C=\left\{u_i:1\le i\le n-1\right\}$， $A\cap B=\varnothing$， $A\cap C=\varnothing$， $B\cap C=\varnothing$。

Figure 8. Graph $D_{n,t}^{(\; 1\; )}$

图8. 图 $D_{n,t}^{(\; 1\; )}$

定理2.16 图 $D_{n,t}^{\left(1\right)}$ 的边覆盖多项式为 $E\left(D_{n,t}^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{tn+n-1+i}}$。图 $D_{n,t}^{\left(1\right)}$ 的边覆盖多项式具

有对数凹性。

证明：图 $D_{n,t}^{\left(1\right)}$ 共有 $\left(tn+2t-2\right)$ 条边。点 $w_{11},w_{12},\cdots ,w_{1,t}$ 只能与点 $v_1$ 有边相连，点 $w_{21},w_{22},\cdots ,w_{2,t}$ 只能与点 $v_2$ 有边相连， $\cdots$，点 $w_{n,1},w_{n,2},\cdots ,w_{n,t}$ 只能与点 $v_n$ 有边相连，显然，图 $D_{n,t}^{\left(1\right)}$ 的边覆盖一定包括边 $v_i{w}_{ij}$，其中， $1\le i\le n,1\le j\le t$。要符合边覆盖，就要再从边 $v_1{u}_1,v_2{u}_1$ 中选出 $m_1$ 条边，从边 $v_2{u}_2,v_3{u}_2$ 中选出 $m_2$ 条边， $\cdots$，从边 $v_{n-1}{u}_{n-1},v_n{u}_{n-1}$ 中选出 $m_{n-1}$ 条边，其中， $m_j=1,2$，并且， ${\displaystyle {\sum }_{j=1}^{n-1}{m}_j}=n-1+i$， $i=0,1,\cdots ,n-1$。对于每个 $m_j=1$，有两种边的选取，对于每个 $m_j=2$，只有一种边的选取，其中， $j=0,1,\cdots ,n$。因此，当 $m_1=m_2=\cdots =m_{n-1}=1$ 时，图 $D_{n,t}^{\left(1\right)}$ 有最小的边覆盖，即被 $\left(tn+n-1\right)$ 条边覆盖，共有 $2^{n-1}$ 种边的选取可能。再从剩下的 $\left(n-1\right)$ 条边中选出i条边，其中， $i=0,1,\cdots ,n-1$，与这n条边形成新的边覆盖，每多加一条边，边覆盖的选取可能数就要除以2。

因此，图 $D_{n,t}^{\left(1\right)}$ 的边覆盖多项式为 $E\left(D_{n,t}^{\left(1\right)},x\right)={\displaystyle {\sum }_{i=0}^{n-1}{2}^{n-1-i}\left(\begin{array}{c}n-1\\ i\end{array}\right)x^{tn+n-1+i}}$。

由此，同定理2.10，很容易得到 $E\left(D_{n,t}^{\left(1\right)},x\right)$ 的对数凹性。 □

定义2.17 爆竹图 $F_n^{\left(3\right)}$ (见图9)，定义为 $F_n^{\left(3\right)}=\left(A,B,C,E\right),n\ge 1$，它的顶点集是 $A\cup B\cup C$，边集是 $E=\left\{u_i{w}_{ij}:1\le i\le n,j=1,2\right\}\cup \left\{v_i{v}_{i+1}:1\le i\le n-1\right\}\cup \left\{v_i{u}_i:1\le i\le n\right\}$，其中， $A=\left\{v_i:1\le i\le n\right\}$， $B=\left\{w_{ij}:1\le i\le n,j=1,2\right\}$， $C=\left\{u_i:1\le i\le n\right\}$， $A\cap B=\varnothing$， $A\cap C=\varnothing$， $B\cap C=\varnothing$。

Figure 9. Firecracker graph $F_n^{(\; 3\; )}$

图9. 爆竹图 $F_n^{(\; 3\; )}$

定理2.18 爆竹图 $F_n^{\left(3\right)}$ 的边覆盖多项式为 $E\left(F_n^{\left(3\right)},x\right)=\left(2x^3+x^4\right)E\left(F_{n-1}^{\left(3\right)},x\right)+\left(x^5+x^6\right)E\left(F_{n-2}^{\left(3\right)},x\right)$。

证明：显然，爆竹图 $F_1^{\left(3\right)}$ 的边覆盖多项式为

$E\left(F_1^{\left(3\right)},x\right)=x^3$。

分两种情况计算爆竹图 $F_n^{\left(3\right)}$ 的边覆盖多项式：

(1) 爆竹图 $F_n^{\left(3\right)}$ 的边覆盖不包括边 $v_{n-1}{u}_n$，爆竹图 $F_n^{\left(3\right)}$ 的边覆盖多项式为

$E\left(F_1^{\left(3\right)},x\right)E\left(F_{n-1}^{\left(3\right)},x\right)=x^{3}E\left(F_{n-1}^{\left(3\right)},x\right)$，

(2) 爆竹图 $F_n^{\left(3\right)}$ 的边覆盖包括边 $v_{n-1}{u}_n$，

① 包括边 $v_{n-2}{v}_{n-1}$ 或边 $v_{n-1}{u}_{n-1}$，爆竹图 $F_n^{\left(3\right)}$ 的边覆盖多项式为

$x^{3}E\left(F_{n-1}^{\left(3\right)},x\right)\left(1+x\right)=\left(x^3+x^4\right)E\left(F_{n-1}^{\left(3\right)},x\right)$，

② 不包括边 $v_{n-2}{v}_{n-1}$ 和边 $v_{n-1}{u}_{n-1}$，爆竹图 $F_n^{\left(3\right)}$ 的边覆盖多项式为

$xE\left(F_{n-2}^{\left(3\right)},x\right)x^2{x}^2\left(1+x\right)=\left(x^5+x^6\right)E\left(F_{n-2}^{\left(3\right)},x\right)$，

综上，爆竹图 $F_n^{\left(3\right)}$ 的边覆盖多项式为

$\begin{array}{c}E\left(F_n^{\left(3\right)},x\right)=x^{3}E\left(F_{n-1}^{\left(3\right)},x\right)+\left(x^3+x^4\right)E\left(F_{n-1}^{\left(3\right)},x\right)+\left(x^5+x^6\right)E\left(F_{n-2}^{\left(3\right)},x\right)\\ =\left(2x^3+x^4\right)E\left(F_{n-1}^{\left(3\right)},x\right)+\left(x^5+x^6\right)E\left(F_{n-2}^{\left(3\right)},x\right)\end{array}$ □

定义2.19 图 $H_{2m+1}$ (见图10)定义为 $H_{2m+1}=\left(A,B,E\right),n\ge 1$，它的顶点集是 $A\cup B$，边集是

$\begin{array}{l}E=\left\{v_i{v}_{i+1}:1\le i\le 2m\right\}\cup \left\{v_i{u}_i:1\le i\le 2m+1\right\}\cup \left\{v_i{u}_{i+1}:1\le i\le 2m+1\right\}\\ \cup \left\{u_i{v}_{i+1}:1\le i\le 2m-1\right\}\cup \left\{u_i{v}_i:2\le i\le 2m\right\}\end{array}$，其中， $A=\left\{v_i:1\le i\le 2m+1\right\}$，

$B=\left\{u_i:1\le i\le 2m+2\right\}$， $A\cap B=\varnothing$。

Figure 10. Graph $H_{2m+1}$

图10. 图 $H_{2m+1}$

图 $H_{2m}$ (见图11)定义为 $H_{2m}=\left(A,B,E\right),n\ge 1$，它的顶点集是 $A\cup B$，边集是

$\begin{array}{l}E=\left\{v_i{v}_{i+1}:1\le i\le 2m-1\right\}\cup \left\{v_i{u}_i:1\le i\le 2m-1\right\}\cup \left\{v_i{u}_{i+1}:1\le i\le 2m-1\right\}\\ \cup \left\{u_i{v}_{i+1}:1\le i\le 2m-1\right\}\cup \left\{u_i{v}_i:2\le i\le 2m\right\}\end{array}$，其中， $A=\left\{v_i:1\le i\le 2m\right\}$，

$B=\left\{u_i:1\le i\le 2m\right\}$， $A\cap B=\varnothing$。

Figure 11. Graph $H_{2m}$

图11. 图 $H_{2m}$

定理2.20 图 $H_{2m+1}$ 的边覆盖多项式为 $E\left(H_{2m+1},x\right)=\left(x^2+x^3\right)E\left(H_{2m},x\right)+x^{3}E\left(H_{2m-1},x\right)$，图 $H_{2m}$ 的边覆盖多项式为 $E\left(H_{2m},x\right)=2x^2+11x^3+13x^4+6x^5+x^{6}E\left(H_{2m-2},x\right)+\left(3x^3+8x^4+5x^5+x^6\right)E\left(H_{2m-3},x\right)$。

证明：很容易能写出， $E\left(H_1,x\right)=x^2$， $E\left(H_2,x\right)=2x^2+8x^3+5x^4+x^5$。

分两种情况计算图 $H_{2m+1}$ 的边覆盖多项式：

(1) 图 $H_{2m+1}$ 的边覆盖不包括边 $v_{2m}{v}_{2m+1}$，图 $H_{2m+1}$ 的边覆盖多项式为

$E\left(H_1,x\right)E\left(H_{2m},x\right)=x^{2}E\left(H_{2m},x\right)$，

(2) 图 $H_{2m+1}$ 的边覆盖包括边 $v_{2m}{v}_{2m+1}$，

① 包括边 $u_{2m-1}{v}_{2m}$ 或边 $v_{2m-1}{v}_{2m}$ 或边 $u_{2m}{v}_{2m}$，图 $H_{2m+1}$ 的边覆盖多项式为

$xE\left(H_{2m},x\right)E\left(H_1,x\right)=x^{3}E\left(H_{2m},x\right)$，

② 不包括边 $u_{2m-1}{v}_{2m}$， $v_{2m-1}{v}_{2m}$， $u_{2m}{v}_{2m}$，图 $H_{2m+1}$ 的边覆盖多项式为

$xE\left(H_1,x\right)E\left(H_{2m-1},x\right)=x^{3}E\left(H_{2m-1},x\right)$，

综上，图 $H_{2m+1}$ 的边覆盖多项式为

$\begin{array}{c}E\left(H_{2m+1},x\right)=x^{2}E\left(H_{2m},x\right)+x^{3}E\left(H_{2m},x\right)+x^{3}E\left(H_{2m-1},x\right)\\ =\left(x^2+x^3\right)E\left(H_{2m},x\right)+x^{3}E\left(H_{2m-1},x\right)\end{array}$。

分两种情况计算图 $H_{2m}$ 的边覆盖多项式：

(1) 图 $H_{2m}$ 的边覆盖不包括边 $v_{2m-2}{v}_{2m-1}$，图 $H_{2m}$ 的边覆盖多项式为

$E\left(H_{2m},x\right)=E\left(H_2,x\right)E\left(H_{2m-2},x\right)=\left(2x^2+8x^3+5x^4+x^5\right)E\left(H_{2m-2},x\right)$，

(2) 图 $H_{2m}$ 的边覆盖包括边 $v_{2m-2}{v}_{2m-1}$，

① 包括边 $v_{2m-2}{u}_{2m-3}$ 或边 $v_{2m-3}{v}_{2m-2}$ 或边 $v_{2m-2}{u}_{2m-2}$，

(i) 包括边 $v_{2m-1}{u}_{2m-1}$ 或边 $v_{2m-1}{v}_{2m}$ 或边 $v_{2m-1}{u}_{2m}$，图 $H_{2m}$ 的边覆盖多项式为

$E\left(H_{2m},x\right)=xE\left(H_2,x\right)E\left(H_{2m-2},x\right)=\left(2x^3+8x^4+5x^5+x^6\right)E\left(H_{2m-2},x\right)$，

(ii) 不包括边 $v_{2m-1}{u}_{2m-1}$，边 $v_{2m-1}{v}_{2m}$，边 $v_{2m-1}{u}_{2m}$，图 $H_{2m}$ 的边覆盖多项式为

$E\left(H_{2m},x\right)=xE\left(H_1,x\right)E\left(H_{2m-2},x\right)=x^{3}E\left(H_{2m-2},x\right)$，

② 不包括边 $v_{2m-2}{u}_{2m-3}$，边 $v_{2m-3}{v}_{2m-2}$，边 $v_{2m-2}{u}_{2m-2}$，

(i) 包括边 $v_{2m-1}{u}_{2m-1}$ 或边 $v_{2m-1}{v}_{2m}$ 或边 $v_{2m-1}{u}_{2m}$，图 $H_{2m}$ 的边覆盖多项式为

$E\left(H_{2m},x\right)=xE\left(H_2,x\right)E\left(H_{2m-3},x\right)=\left(2x^3+8x^4+5x^5+x^6\right)E\left(H_{2m-3},x\right)$，

(ii) 不包括边 $v_{2m-1}{u}_{2m-1}$，边 $v_{2m-1}{v}_{2m}$，边 $v_{2m-1}{u}_{2m}$，图 $H_{2m}$ 的边覆盖多项式为

$E\left(H_{2m},x\right)=xE\left(H_1,x\right)E\left(H_{2m-3},x\right)=x^{3}E\left(H_{2m-3},x\right)$，

综上，图 $H_{2m}$ 的边覆盖多项式为

$E\left(H_{2m},x\right)=2x^2+11x^3+13x^4+6x^5+x^{6}E\left(H_{2m-2},x\right)+\left(3x^3+8x^4+5x^5+x^6\right)E\left(H_{2m-3},x\right)$。 □

3. 结论

本文应用Akbari和Oboudi给出的边覆盖多项式的定义，归纳写出以上几个图的边覆盖多项式，并研究其对数凹性，证明了图1~8的边覆盖多项式具有对数凹性。