给定点的局部平均控制集的研究

The Local Average Order of Dominating Sets Containing a Fixed Vertex

摘要: 图$G$ 的平均控制集$avd\left(G\right)$ 是其所有控制集的顶点数的平均值。类似地，局部平均控制集$av{d}_v\left(G\right)$ 是所有含给定点$v$ 的控制集的顶点数的平均值。$G$ 的控制多项式$D\left(G,x\right)$ 是其控制集的生成函数，由于平均控制集是控制多项式的对数导数在1处的取值，在本文中，我们利用平均控制集和控制多项式之间的关系给出了$n\left(n\ge 3\right)$ 阶连通图中度为$n-2$ 的给定点的局部平均控制集的公式。

Abstract: The global average order of dominating sets of a graph $avd\left(G\right)$ is the average number of vertices of its dominating sets. Analogously, the local average order of dominating sets $av{d}_v\left(G\right)$ is the average number of vertices of its dominating sets containing a fixed vertex $v$ . The domination polynomial $D\left(G,x\right)$ of a graph $G$ is the generating function of its dominating sets. The global average order of dominating sets is the value of the logarithmic derivative of the domination polynomial at $x=1$ . In this paper, we derive a formula for the local average order of dominating sets in the case where the degree of the fixed vertex is $n-2$ .

1. 引言

图的平均参数相关研究有着较长的发展历程且涵盖多个方面。1971年，Doyle和Graver [1]给出了计算树平均距离的公式，并确定了$n$ 阶连通图中在路上取得最大平均距离为$\left(n+1\right)/3$ ，在完全图上取得最小平均距离为1。

随后，许多图平均参数被陆续引入。1983年，Jamison [2]引入了树的子树平均阶数。众多研究者对其进行了更深入的探究，主要关注平均子树阶的极值情况[3]-[5]，以及边的改变对子树平均阶数的影响[6]-[10]。

此外，像图的平均独立集[11] [12]、平均匹配[13]、平均连通度[14]和平均离心率[15]-[17]等不同的图平均参数已相继被提出并得到了不同程度的研究。

图的平均控制集是由Beaton和Brown [18]最近引入的一个新的图平均参数。设$S$ 为图$G$ 的控制集，$\mathcal{D}\left(G\right)$ 为$G$ 中所有控制集的集合。他们将$G$ 的平均控制集记为$avd\left(G\right)$ ，并定义为

$avd\left(G\right)=\frac{{{\displaystyle \sum }}_{S\in \mathcal{D}\left(G\right)}\left|S\right|}{\left|\mathcal{D}\left(G\right)\right|}$

Beaton和Brown证明了对于所有$n$ 阶图，完全图使平均控制集达到最小，此时$avd\left(K_n\right)=\frac{n{2}^{n-1}}{2^n-1}$ ，而空图使其达到最大。此外，对于不含孤立点的$n$ 阶图，他们给出了$avd\left(G\right)$ 的一个上界为$3n/4$ ，但该界并非最优，他们猜想$n\ge 2$ 的$n$ 阶连通图的平均控制集可以取到更紧的上界为$2n/3$ 。随后Erey [19]利用控制多项式证明了在不含孤立点的$n$ 阶森林中，平均控制集的上界为$2n/3$ ，并刻画了极图。设度为1的顶点为叶子，与$l\left(l\ge 1\right)$ 个叶子相邻的顶点叫做$l$ -茎，则相应的极图具有以下结构：图中每个顶点要么是叶子，要么是至多连接2个叶子的茎。最近，Beaton与Cameron [20]将这一结论推广至所有不含孤立点的$n$ 阶图，刻画的极图与Erey在[19]中刻画的极图一致，并称之为似星图(star-like graphs)。

图的平均控制集是其所有控制集的顶点数的平均值。类似地，局部平均控制集是所有含给定点的控制集的顶点数的平均值，这一概念通过给定点在所有相关控制集中的参与性，量化了该点在平均控制集中的贡献。现在我们给出局部平均控制集的定义。对于给定点$v$ ，设$S_v\left(G\right)=\left\{S\in \mathcal{D}\left(G\right):v\in S\right\}$ 为图$G$ 中包含$v$ 的控制集。类似地，设${\mathcal{D}}_v\left(G\right)$ 表示$G$ 中所有包含$v$ 的控制集的集合。因此，我们可以定义含$v$ 的局部平均控制集为

$av{d}_v\left(G\right)=\frac{{{\displaystyle \sum }}_{S_v\in {\mathcal{D}}_v\left(G\right)}\left|S_v\left(G\right)\right|}{\left|{\mathcal{D}}_v\left(G\right)\right|}$

根据这个定义，我们可以简单推导出几类特殊图中含特定顶点的局部平均控制集，如$n$ 阶空图和$n$ 阶完全图中含任意一个顶点的局部平均控制集，这将在下一节给出具体结果。对于一般图而言，给定点$v$ 不同，对应的$av{d}_v\left(G\right)$ 也不同，而完全图中的每个顶点都等价，具体的结果也能够直接计算得出，因此本文将进一步聚焦于一般连通图中含给定点的度为$n-2$ 的情况，其中给定点的度表示与该顶点相连的边数，我们将顶点$v$ 的度记作$\mathrm{deg}\left(v\right)$ 。

定理1. 设$G$ 是一个$n\left(n\ge 3\right)$ 阶连通图，$v$ 是其中满足$\text{deg}\left(v\right)=n-2$ 的顶点。假设$u$ 是不与$v$ 相邻的顶点，则

$av{d}_v\left(G\right)=\frac{\left(n+1\right)2^{n-2}-\left(n-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}}{2^{n-1}-2^{n-2-\mathrm{deg}\left(u\right)}}$

本文的结构如下：在第二部分，我们将给出一些图的基本概念，以及完全图、空图和星图中含特定顶点的局部平均控制集，并介绍控制多项式与平均控制集的关系。在第三部分，我们给出了主要证明结果。

2. 预备知识

给定一个简单有限无向图$G$ ，设$V\left(G\right)$ 和$E\left(G\right)$ 分别为顶点集和边集。对于顶点$v\in V\left(G\right)$ ，在$G$ 中与$v$ 相邻的顶点$u$ 称为$v$ 的邻点。$v$ 的所有邻点的集合称为$v$ 的开邻域，记为$N_G\left(v\right)$ 。同时我们用$N_G\left[v\right]$ 表示$v$ 的闭邻域，即$N_G\left[v\right]=N_G\left(v\right)\cup \left\{v\right\}$ 。当只涉及一个图时，可以简记为$N\left(v\right)$ 和$N\left[v\right]$ 。特别地，如果$N\left(v\right)=\varnothing$ ，则顶点$v$ 称为孤立点。如果$N\left[S\right]=V\left(G\right)$ ，这意味着$V\left(G\right)-S$ 中的每个顶点都与$S$ 中的至少一个顶点相邻，那么我们称$S$ 为$G$ 的控制集。控制数$\gamma \left(G\right)$ 是$G$ 的最小控制集的阶数。对于给定点$v$ ，含给定点的控制集为$S_v\left(G\right)=\left\{S\in \mathcal{D}\left(G\right):v\in S\right\}$ ，含给定点的局部平均控制集$av{d}_v\left(G\right)$ 如第一部分所示。

对于$n$ 阶图中度为$n-1$ 的给定点，其局部平局控制集可以根据其性质直接计算得出。

引理2. 若$v$ 为$n$ 阶图$G$ 中的一个顶点，且满足$\mathrm{deg}\left(v\right)=n-1$ ，则

$av{d}_v\left(G\right)=\frac{n+1}{2}$

证明：在$G$ 中，顶点$v$ 满足$\mathrm{deg}\left(v\right)=n-1$ 意味着$v$ 与其余所有顶点相邻，说明包含$v$ 的顶点集子集都为$G$ 的控制集，那么可以分别计算出$\left|{\mathcal{D}}_v\left(G\right)\right|$ 与${\displaystyle \sum }_{S_v\in {\mathcal{D}}_v\left(G\right)}\left|S_v\left(G\right)\right|$ 的结果如下。

$\left|{\mathcal{D}}_v\left(G\right)\right|={\displaystyle \sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)=2^{n-1}$

${\displaystyle \sum }_{S_v\left(G\right)\in {\mathcal{D}}_v\left(G\right)}\left|S_v\left(G\right)\right|={\displaystyle \sum }_{i=0}^{n-1}\left(\begin{array}{c}n-1\\ i\end{array}\right)\left(i+1\right)=\left(n+1\right)2^{n-2}$

因此，由局部平均控制集的一般定义可得：

$av{d}_v\left(G\right)=\frac{{{\displaystyle \sum }}_{S_v\in {\mathcal{D}}_v\left(G\right)}\left|S_v\left(G\right)\right|}{\left|{\mathcal{D}}_v\left(G\right)\right|}=\frac{\left(n+1\right)2^{n-2}}{2^{n-1}}=\frac{n+1}{2}$

对于某些特殊图，其顶点之间有一定等价性，因此含特定顶点的局部平均控制集可以直接计算得出。在具有$n$ 个顶点的完全图$K_n$ 中，对于任意顶点$v$ 都满足$\mathrm{deg}\left(v\right)=n-1$ ，由引理2可得，

$av{d}_v\left(K_n\right)=\frac{n+1}{2}$

在具有$n$ 个顶点的空图$\overline{K_n}$ 中，对于任意顶点$v$ ，

$av{d}_v\left(\overline{K_n}\right)=n$

在具有$n$ 个顶点的星图$K_{1,n-1}$ 中，有两种不同类型的顶点。当$\mathrm{deg}\left(v\right)=n-1$ 时，由引理2可得，

$av{d}_v\left(K_{1,n-1}\right)=\frac{n+1}{2}$

当$\mathrm{deg}\left(v\right)=1$ 时，

$av{d}_v\left(K_{1,n-1}\right)=\frac{\left(n+2\right)2^{n-3}+n-1}{2^{n-2}+1}$

实际上，我们更关注一般图中含不同给定点的局部平均控制集的情况。引理2已经给出了$n$ 阶图中给定点的度为$n-1$ 时的局部平均控制集，接下来我们将研究一般连通图中含给定点$v$ 的度为$n-2$ 的$av{d}_v\left(G\right)$ 。Beaton和Brown在[18]中说明了平均控制集与控制多项式之间紧密的联系，即平均控制集是控制多项式的对数导数在1处的取值，因此我们可以通过控制多项式进一步研究含给定点的局部平均控制集。下面将给出控制多项式的定义。

令$d_k\left(G\right)=\left|\left\{S\in \mathcal{D}\left(G\right):\left|S\right|=k\right\}\right|$ 。$G$ 的控制多项式定义为

$D\left(G,x\right)={\displaystyle \sum _{k=\gamma \left(G\right)}^{\left|V\left(G\right)\right|}{d}_k\left(G\right)x^k}$

由于$avd\left(G\right)$ 等于$D\left(G,x\right)$ 在$x=1$ 处的对数导数，平均控制集也可表示为

$avd\left(G\right)=\frac{D^{\prime }\left(G,1\right)}{D\left(G,1\right)}=\frac{{\displaystyle \sum _{k=\gamma \left(G\right)}^{\left|V\left(G\right)\right|}k{d}_k\left(G\right)}}{{\displaystyle \sum _{k=\gamma \left(G\right)}^{\left|V\left(G\right)\right|}{d}_k\left(G\right)}}$

现在我们考虑含给定点的局部平均控制集与局部控制多项式之间的关系。我们将含给定点$v$ 的局部控制多项式记作$D_{v\in S}\left(G,x\right)$ ，定义为

$D_{v\in S}\left(G,x\right)={\displaystyle \sum _{k=\gamma \left(G\right)}^{\left|V\left(G\right)\right|}{d}_k\left(G,v\right)x^k}$

其中$d_k\left(G,v\right)=\left|\left\{S_v\in \mathcal{D}\left(G\right):\left|S_v\right|=k\right\}\right|$ 。默认$v\in S$ 时可简记为$D_v\left(G,x\right)$ 。类似地，含$v$ 的局部平均控制集也可表示为

$av{d}_v\left(G\right)=\frac{{D^{\prime }}_v\left(G,1\right)}{D_v\left(G,1\right)}=\frac{{\displaystyle \sum _{k=\gamma \left(G\right)}^{\left|V\left(G\right)\right|}k{d}_k\left(G,v\right)}}{{\displaystyle \sum _{k=\gamma \left(G\right)}^{\left|V\left(G\right)\right|}{d}_k\left(G,v\right)}}$

下面我们将介绍一些基本的操作，$G-v$ 表示表示从$G$ 中删除$v$ 以及与$v$ 相连的边得到的图，$G/v$ 表示从$G$ 中删除$v$ 以及与$v$ 相连的边，并在$v$ 的任意一对非相邻邻点之间添加边所得到的图，以$K_{1,3}$ 与$K_{1,3}/v$ 为例子，见图1。

Figure 1. $K_{1,3}$ and $K_{1,3}/v$

图1. $K_{1,3}$ 与$K_{1,3}/v$

Kotek等人在[21]定义了一种生成函数$p_v\left(G,x\right)$ ，它负责计数在$G-N\left[v\right]$ 中那些也控制着$N_G\left(v\right)$ 顶点的控制集，又或者说，$p_v\left(G,x\right)$ 是负责计数$G-v$ 中不包含任何$N_G\left(v\right)$ 中的顶点的控制集。为了进一步探究一般连通图中含给定点$v$ 的度为$n-2$ 的$av{d}_v\left(G\right)$ ，我们需要用到如下引理。

引理3. ([21]，定理2.1) 对于图$G$ 中的任意顶点$v$ ，我们有

$D\left(G,x\right)=xD\left(G/v,x\right)+D\left(G-v,x\right)+xD\left(G-N\left[v\right],x\right)-\left(1+x\right)p_v\left(G,x\right)$

此外，我们有

$D_{v\notin S}\left(G,x\right)=D\left(G-v,x\right)-p_v\left(G,x\right)$

$D_{v\in S}\left(G,x\right)=xD\left(G-N\left[v\right],x\right)+x\left(D\left(G/v,x\right)-p_v\left(G,x\right)\right)$

3. 主要证明结果

现在我们可以确定一般连通图中含给定点$v$ 的度为$n-2$ 时的局部平均控制集$av{d}_v\left(G\right)$ ，下面将具体证明定理1。

根据$N_G\left(u\right)$ 和$N_G\left(v\right)$ 之间的关系，我们可以分成两种情况来考虑。

情形1. $N_G\left(u\right)=N_G\left(v\right)$ ，由于$u$ 与$v$ 不相邻，这意味着剩下的$n-2$ 个点也同样是$u$ 的邻点，即有$\text{deg}\left(u\right)=n-2$ 。显然$G-N_G\left[v\right]\cong \left\{u\right\}$ 。由引理3，我们可以得到

$\begin{array}{c}{D}_v\left(G,x\right)=xD\left(G-N\left[v\right],x\right)+x\left(D\left(G/v,x\right)-p_v\left(G,x\right)\right)\\ =x^2+x\left(D\left(K_{n-1},x\right)-x\right)\\ =xD\left(K_{n-1},x\right)\end{array}$ (1)

对等式(1)关于$x$ 求导则有

${D^{\prime }}_v\left(G,x\right)=D\left(K_{n-1},x\right)+x{D}^{\prime }\left(K_{n-1},x\right)$ (2)

由于$avd\left(K_{n-1}\right)=\frac{\left(n-1\right)2^{n-2}}{2^{n-1}-1}$ ，令等式(1)和(2)中的$x=1$ 就能得到

$av{d}_v\left(G\right)=\frac{D^{\prime }\left(G,1\right)}{D\left(G,1\right)}=1+av{d}_v\left(K_{n-1}\right)=1+\frac{\left(n-1\right)2^{n-2}}{2^{n-1}-1}=\frac{\left(n+1\right)2^{n-2}-1}{2^{n-1}-1}$ (3)

情形 2. $N_G\left(u\right)⊊N_G\left(v\right)$ ，即$N_G\left(v\right)$ 中至少存在一个顶点不与$u$ 相邻，又因为图$G$ 为连通图，这意味着$1\le \text{deg}\left(u\right)\le n-3$ 。同样地，$G-N_G\left[v\right]\cong \left\{u\right\}$ ，但是$u$ 显然不能控制$N_G\left(v\right)$ 中所有的顶点，所以$p_v\left(G,x\right)=0$ 。由引理3，我们能够得到

$D_v\left(G,x\right)=xD\left(G-N_G\left[v\right],x\right)+xD\left(G/v,x\right)=x^2+xD\left(G/v,x\right)$ (4)

对等式(4)关于$x$ 求导则有

${D^{\prime }}_v\left(G,x\right)=2x+D\left(G/v,x\right)+x{D}^{\prime }\left(G/v,x\right)$ (5)

令等式(4)和(5)中的$x=1$ ，就能得到

$av{d}_v\left(G\right)=1+\frac{1+D^{\prime }\left(G/v,1\right)}{1+D\left(G/v,1\right)}$

现在设$H$ 是由$G/v$ 得到的图。接下来我们计算$D\left(H,1\right)$ 和$D^{\prime }\left(H,1\right)$ ，并分别记为$\Gamma \left(H\right)$ 和${\Gamma }^{\prime }\left(H\right)$ 。

首先，考虑$H$ 中包含$u$ 的控制集$S_u$ 。由于$N_G\left(u\right)⊊N_G\left(v\right)$ ，这表明$H-\left\{u\right\}$ 中至少存在一个顶点也在控制集$S_u$ 中。而且因为$H-\left\{u\right\}\cong K_{n-2}$ ，所以$\left|{\mathcal{D}}_u\left(H\right)\right|=\left|\mathcal{D}\left(H-u\right)\right|=\left|\mathcal{D}\left(K_{n-2}\right)\right|$ 。因此，我们有

$D_u\left(H,x\right)=xD\left(K_{n-2},x\right)$

以及

${D^{\prime }}_u\left(H,x\right)=D\left(K_{n-2},x\right)+x{D}^{\prime }\left(K_{n-2},x\right)$ 。

通过计算可以得到$D\left(K_{n-2},1\right)=2^{n-2}-1$ ，以及$D^{\prime }\left(K_{n-2},1\right)=\left(n-2\right)2^{n-3}$ 。在$D_u\left(H,x\right)$ 和${D^{\prime }}_u\left(H,x\right)$ 中取$x=1$ ，即有

${\Gamma }_u\left(H\right)=D_u\left(H,1\right)=2^{n-2}-1$ (6)

${{\Gamma }^{\prime }}_u\left(H\right)={D^{\prime }}_u\left(H,1\right)=2^{n-2}-1+\left(n-2\right)2^{n-3}=n{2}^{n-3}-1$ (7)

接下来，我们考虑$H$ 中不包含$u$ 的控制集$S_{-u}$ 。显然，$N_H\left(u\right)$ 中至少存在一个顶点属于控制集$S_{-u}$ ，否则无法控制$u$ 。它与$H$ 中所有其他顶点相邻。为了统一记号，我们将$D_{u\notin S}\left(H,1\right)$ 记作${\Gamma }_{-u}\left(H\right)$ ，将${D^{\prime }}_{u\notin S}\left(H,1\right)$ 记作${{\Gamma }^{\prime }}_{-u}\left(H\right)$ 。因此，我们可以利用二项式定理直接计算${\Gamma }_{-u}\left(H\right)$ 和${{\Gamma }^{\prime }}_{-u}\left(H\right)$ 。具体计算如下所示，

$\begin{array}{c}{\Gamma }_{-u}\left(H\right)={\displaystyle \sum _{j=0}^{n-2-\mathrm{deg}\left(u\right)}\left(\begin{array}{c}n-2-\mathrm{deg}\left(u\right)\\ j\end{array}\right)}{\displaystyle \sum _{i=1}^{\mathrm{deg}\left(u\right)}\left(\begin{array}{c}\mathrm{deg}\left(u\right)\\ i\end{array}\right)}\\ =2^{n-2-\mathrm{deg}\left(u\right)}\cdot \left(2^{\mathrm{deg}\left(u\right)}-1\right)\\ =2^{n-2}-2^{n-2-\mathrm{deg}\left(u\right)}\end{array}$ (8)

同理，

$\begin{array}{c}{{\Gamma }^{\prime }}_{-u}\left(H\right)={\displaystyle \sum _{j=0}^{n-2-\mathrm{deg}\left(u\right)}\left(\begin{array}{c}n-2-\mathrm{deg}\left(u\right)\\ j\end{array}\right)}{\displaystyle \sum _{i=1}^{\mathrm{deg}\left(u\right)}\left(\begin{array}{c}\mathrm{deg}\left(u\right)\\ i\end{array}\right)\left(i+j\right)}\\ ={\displaystyle \sum _{j=0}^{n-2-\mathrm{deg}\left(u\right)}\left(\begin{array}{c}n-2-\mathrm{deg}\left(u\right)\\ j\end{array}\right)}{\displaystyle \sum _{i=1}^{\mathrm{deg}\left(u\right)}\left(\begin{array}{c}\mathrm{deg}\left(u\right)\\ i\end{array}\right)i}+{\displaystyle \sum _{j=0}^{n-2-\mathrm{deg}\left(u\right)}\left(\begin{array}{c}n-2-\mathrm{deg}\left(u\right)\\ j\end{array}\right)}{\displaystyle \sum _{i=1}^{\mathrm{deg}\left(u\right)}\left(\begin{array}{c}\mathrm{deg}\left(u\right)\\ i\end{array}\right)j}\\ =\mathrm{deg}\left(u\right)\cdot 2^{\mathrm{deg}\left(u\right)-1}\cdot 2^{n-2-\mathrm{deg}\left(u\right)}+\left(n-2-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}\\ =\left(n-2\right)2^{n-3}-\left(n-2-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}\end{array}$ (9)

根据等式(6)~(9)，我们可以得到

$\begin{array}{c}\Gamma \left(H\right)={\Gamma }_u\left(H\right)+{\Gamma }_{-u}\left(H\right)\\ =\left(2^{n-2}-1\right)+\left(2^{n-2}-2^{n-2-\mathrm{deg}\left(u\right)}\right)\\ =2^{n-1}-2^{n-2-\mathrm{deg}\left(u\right)}-1\end{array}$

以及

$\begin{array}{c}{\Gamma }^{\prime }\left(H\right)={{\Gamma }^{\prime }}_u\left(H\right)+{{\Gamma }^{\prime }}_{-u}\left(H\right)\\ =\left(n{2}^{n-3}-1\right)+\left(n-2\right)2^{n-3}-\left(n-2-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}\\ =\left(n-1\right)2^{n-2}-\left(n-2-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}-1\end{array}$

由上述结果可得

$\begin{array}{c}av{d}_v\left(G\right)=1+\frac{1+{\Gamma }^{\prime }\left(H\right)}{1+\Gamma \left(H\right)}\\ =1+\frac{\left(n-1\right)2^{n-2}-\left(n-2-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}}{2^{n-1}-2^{n-2-\mathrm{deg}\left(u\right)}}\\ =\frac{\left(n+1\right)2^{n-2}-\left(n-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}}{2^{n-1}-2^{n-2-\mathrm{deg}\left(u\right)}}\end{array}$ (10)

注意到当$\mathrm{deg}\left(u\right)=n-2$ 时，等式(10)仍然成立，且结果与等式(3)一致，说明该公式同样满足情形1。综上所述，

$av{d}_v\left(G\right)=\frac{\left(n+1\right)2^{n-2}-\left(n-\mathrm{deg}\left(u\right)\right)2^{n-3-\mathrm{deg}\left(u\right)}}{2^{n-1}-2^{n-2-\mathrm{deg}\left(u\right)}}$

4. 结论

本文通过平均控制集是控制多项式的对数导数在1处取值的这一关系，从度的角度探究了给定点的局部平均控制集。确定了$n$ 阶图中含度为$n-1$ 的给定点$v$ 的局部平均控制集为$\left(n+1\right)/2$ ，并详细探讨了$n\left(n\ge 3\right)$ 阶连通图$G$ 中含度为$n-2$ 的给定点$v$ 的局部平均控制集$av{d}_v\left(G\right)$ 。根据$N_G\left(v\right)$ 和与其不相邻的顶点$u$ 的开邻域$N_G\left(u\right)$ 的关系，分情况讨论了$av{d}_v\left(G\right)$ 的计算结果，最终发现$av{d}_v\left(G\right)$ 与$u$ 的度$\mathrm{deg}\left(u\right)$ 紧密相关，并得到相应的计算公式。

我们可以继续考虑给定点的度为$n-3$ 甚至更一般的情形。当给定点的度为$n-3$ 时会产生两个与给定点$v$ 不相邻的顶点，需要进一步探讨两点之间以及各自分别与$N\left(v\right)$ 之间的关系。由于这直接关系到$G/v$ 的刻画，使得$D\left(G/v,x\right)$ 和$p_v\left(G,x\right)$ 的值难以确定，未必有通式表示其局部平均控制集，因此直接利用控制多项式去计算相应结果的方法存在一定的局限性。

另外，对于图平均参数，研究者们往往关注它们在不同图类中的求值结果，以及相应的极值问题。本文的结果刻画了含某种性质的给定点的局部平均控制集。当给定点的性质不同时，对应的局部平均控制集也会呈现不同的性质，在未来的研究中，我们还可以根据给定点的性质分类研究局部平均控制集的极值问题。

NOTES

^*通讯作者。