直径为d的一些树的排序

Sorting of Some Trees with Diameter of d

摘要: 本文主要是对有n个点直径为d的树T_n,d(i)，以及前棵这样的树做了排序的成果(具体内容见序言部分)基础上重新讨论了上述树的另一种排序方法，并更进一步确定了它们的上界。

Abstract: Based on the results of sorting trees T_n,d(i) with n-point diameter d and the previous trees with n-point diameter d (see the preface for details), this paper rediscusses another sorting method of the above-mentioned trees, and their upper bounds are further determined.

1. 序言

设 $X=\left(V,E\right)$ 是一个简单图。我们用 $A\left(X\right)$ 表示X的矩阵。称 $\Phi \left(X,\lambda \right)=\det \left(\lambda I-A\left(X\right)\right)$ 为X的特征多项式，可简单记为 $\Phi \left(X\right)$ 。因为 $A\left(X\right)$ 是对称矩阵，则它的特征值是实数。我们可以把这些特征值记作 ${\lambda }_1\left(X\right)\ge {\lambda }_2\left(X\right)\ge {\lambda }_3\left(X\right)\ge \cdots \ge {\lambda }_n\left(X\right)$ ，并且把它们称为X的谱。显然， ${\lambda }_1$ 是图G的邻接矩阵 $A\left(G\right)$ 的最大特征值，(有时也被称为指数)，并且我们将它称为图G的谱半径。

无圈的连通图称为树。如果在G中存在 $\left(u,v\right)$ 路，称u和v是连通的。若在G中顶点u和v是连通的，则u和v之间的距离是指G中u和v之间最短路的长度。G的直径是指G中最远的两个顶点之间的距离。自1981年Cvetkovic在 [1] 提出，根据图的最大特征值给树分类和排序这个问题以来，人们用固定某个常量的方法研究树的谱半径，对于n个点的树，Hofmeister在 [2] 中已经确定了它的谱半径的前五大特征值以及这些特征值所对应的树。在 [3] 中Chang和huang将这个顺序增加到了第八棵树。

设 $T_{\left(n,d\right)}$ 是有n个点的直径为d的树集( $3\le d\le n-4$ )，Ji-Ming Guo和Jia-Yu Shao在 [1] 中给出了 $T_{\left(n,d\right)}$ 的四个子集，它们分别是 $T_{\left(n,d\right)}\left(i\right)$ ， $T_{\left(n,d\right)}^{*}\left(i\right)$ ， ${\bar{T}}_{\left(n,d\right)}\left(i\right)$ ， $T_{\left(n,d\right)}\left(i,j\right)$ 。(它们都是n个点的直径为d的树。)并且讨论了当 $n\ge d+4,d\ge 4$ ， $i=\lfloor \frac{d}{2}\rfloor +1,j=\lfloor \frac{d}{2}\rfloor +2$ 时它们的谱半径的排序问题，在这里我们介绍一下它们的定义，并给出对应的图形，如图1所示。树图 $T_{\left(n,d\right)}\left(i\right)$ 是通过一个d长路在第i个顶点处增加 $n-d-1$ 个新的悬挂边 $v_i{v}_{d+2},v_i{v}_{d+3},\cdots ,v_i{v}_n$ 所形成的。 $T_{\left(n,d\right)}^{*}\left(i\right)$ 是通过一个d长路在第i个顶点处分别增加一个长为2的路 $v_i{v}_{d+2}{v}_{d+3}$ 和 $n-d-3$ 个新的悬挂边 $v_i{v}_{d+4},v_i{v}_{d+5},\cdots ,v_i{v}_n$ 所形成的。 ${\bar{T}}_{\left(n,d\right)}\left(i\right)$ 是通过一个d长路在第i个顶点处增加一个星图 $K_{1,n-d-2}$ (其中顶点 $v_{d+2}$ 是星图 $K_{1,n-d-2}$ 的中心点)所形成的。 $T_{\left(n,d\right)}\left(i,j\right)$ 是通过一个d长路在第i个顶点处增加 $n-d-2$ 个新的悬挂边 $v_i{v}_{d+2},v_i{v}_{d+3},\cdots ,v_i{v}_{n-1}$ ，在第j个顶点处增加一个悬挂边 $v_j{v}_n$ 所形成的。在这篇文章里，我们重新讨论了这四棵树在当 $n\ge d+4,d\ge 4$ ， $i=\lfloor \frac{d}{2}\rfloor +1,j=\lfloor \frac{d}{2}\rfloor +2$ 时的排序问题。

$T_{(n,d)}(\; i\; )$

$T_{(n,d)}^{*}(\; i\; )$

${\bar{T}}_{(n,d)}(\; i\; )$ $T_{(n,d)}(i,j)$

Figure 1. Tree graph

图1. 树图

Ji-Ming Guo和Jia-Yu Shao在 [4] 中对有n个点直径为d的树 $T_{n,d}\left(i\right)$ 也进行了研究，并对前 $\lfloor \frac{d}{2}\rfloor$ 棵这样的树做了排序，即

${\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor \right)\right)>\cdots >{\lambda }_1\left(T_{\left(n,d\right)}\left(3\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(2\right)\right)$ ，其中 $n\ge d+4$ ， $d\ge 3$ ， $i=\lfloor \frac{d}{2}\rfloor +1,\lfloor \frac{d}{2}\rfloor ,\lfloor \frac{d}{2}\rfloor -1,\cdots ,3,2$ 。 $\lfloor \frac{d}{2}\rfloor$ 表示不超过 $\frac{d}{2}$ 的最大整数，但是他们没有讨论这些树的上界。在这篇文章里，我们重新讨论了上述树的另一种排序方法，并且确定了它们的上界。

2. 主要结果

在这一节里我们先给出一些引理；之后，通过它们得出我们的主要结果。

引理1 [4] 当 $n\ge d+3\ge 7$ 时，有 ${\lambda }_1\left(T^{″}\right)>{\lambda }_1\left(T^{*}\right)$ 成立，其中 $T^{″}$ 是树 $T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1,\lfloor \frac{d}{2}\rfloor +2\right)$ ， $T^{*}$ 是树 $T_{\left(n,d\right)}^{*}\left(\lfloor \frac{d}{2}\rfloor +1\right)$ 。

引理2 [4] 当 $n\ge d+4,d\ge 3$ 时，有

${\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor \right)\right)>\cdots >{\lambda }_1\left(T_{\left(n,d\right)}\left(3\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(2\right)\right)>{\lambda }_1\left(T^{″}\right).$

其中 $T^{″}$ 是树 $T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1,\lfloor \frac{d}{2}\rfloor +2\right)$ 。

引理3 [4] 设 $P_n$ 是 $n-1$ 长的路，则 $\Phi \left(P_n,\lambda \right)=\frac{1}{\sqrt{{\lambda }^2-4}}\left(a^{n+1}-b^{n+1}\right)$ ，其中

$a=\frac{1}{2}\left(\lambda +\sqrt{{\lambda }^2-4}\right),b=\frac{1}{2}\left(\lambda -\sqrt{{\lambda }^2-4}\right).$

其中 $T^{″}$ 是树 $T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1,\lfloor \frac{d}{2}\rfloor +2\right)$ 。

引理4 [5] 若 $G_1,G_2,\cdots ,G_t$ 是图G的t个分支，则 $\Phi \left(G,\lambda \right)=\Phi \left(G_1,\lambda \right)\Phi \left(G_2,\lambda \right)\cdots \Phi \left(G_t,\lambda \right)={\displaystyle \prod \Phi \left(G_i,\lambda \right)}$

引理5 [6] 设u是非平凡图G的一个顶点， $G_{k,l}^0$ 是G通过在顶点u处增加两条长分别为k和l的路所得到的图。若 $k\ge l\ge 1$ ，则有 ${\lambda }_1\left(G_{k,l}^0\right)>{\lambda }_1\left(G_{k+1,l-1}^0\right)$ 。

引理6 [7] 设 $T_1,T_2$ 是有n个点的树集 $G_n$ 中的两棵树( $n\ge 4$ )，若 $\Delta \left(T_1\right)\ge \lceil \frac{2n}{3}\rceil -1$ ，并且 $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ ，则 ${\lambda }_1\left(T_1\right)>{\lambda }_1\left(T_2\right)$ 。

引理7 [8] 设u是G的一个顶点，v表示G中所有与u相邻的顶点， $C\left(u\right)$ 是包含顶点u的所有圈集，设 $V\left(Z\right)$ 是圈Z的顶点集，则 $\Phi \left(G\right)$ 的特征多项式满足

$\Phi \left(G,\lambda \right)=\lambda \Phi \left(G-u\right)-{\displaystyle \underset{v}{\sum }\Phi \left(G-u-v\right)}-2{\displaystyle \underset{Z}{\sum }\Phi (G-V(\; Z\; ))}$

定理8 当 $4\le d\le n-4$ 时，按谱半径的大小给 $T_{\left(n,d\right)}\left(i\right)$ 的排序如下：

${\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor \right)\right)>\cdots >{\lambda }_1\left(T_{\left(n,d\right)}\left(3\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(2\right)\right)$ ，其中 $\lfloor \frac{d}{2}\rfloor$ 表示不超过 $\frac{d}{2}$ 的最大整数。

证明：首先根据引理1,6，我们有 ${\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1,\lfloor \frac{d}{2}\rfloor +2\right)\right)>{\lambda }_1\left(T_{\left(n,d\right)}^{*}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)>{\lambda }_1\left({\bar{T}}_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)$ 再由引理2容易得到，在带有n个点且直径为d的树中，谱半径最大的树是 $T_{\left(n,d\right)}\left(i\right)$ 。

因此下面我们仅需对 $T_{\left(n,d\right)}\left(i\right)$ 中的树的谱半径的排序进行讨论。由引理5，我们容易得出结论成立。#

定理9 当 $4\le d\le n-4$ 时, ${\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)<\sqrt{n-d}+1$

证明：由引理3，4，7容易得到 $T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)$ 的特征多项式为

$\begin{array}{l}{\lambda }^{n-d-2}[\left({\lambda }^2-n+d+1\right)\left(a^{d+2}-a^{d-2\lfloor \frac{d}{2}\rfloor }-b^{d-2\lfloor \frac{d}{2}\rfloor }+b^{d+2}\right)\\ -\lambda \left(2a^{d+1}-a^{d-2\lfloor \frac{d}{2}\rfloor +1}-b^{d-2\lfloor \frac{d}{2}\rfloor +1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}+2b^{d+1}\right)]\end{array}$

则 $T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)$ 的最大特征值是方程

$\begin{array}{l}\left({\lambda }^2-n+d+1\right)\left(a^{d+2}-a^{d-2\lfloor \frac{d}{2}\rfloor }-b^{d-2\lfloor \frac{d}{2}\rfloor }+b^{d+2}\right)\\ -\lambda \left(2a^{d+1}-a^{d-2\lfloor \frac{d}{2}\rfloor +1}-b^{d-2\lfloor \frac{d}{2}\rfloor +1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}+2b^{d+1}\right)=0\end{array}$

的最大根。

那么我们就有 $\frac{{\lambda }^2-n+d+1}{\lambda }=\frac{2a^{d+1}-a^{d-2\lfloor \frac{d}{2}\rfloor +1}-b^{d-2\lfloor \frac{d}{2}\rfloor +1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}+2b^{d+1}}{a^{d+2}-a^{d-2\lfloor \frac{d}{2}\rfloor }-b^{d-2\lfloor \frac{d}{2}\rfloor }+b^{d+2}}$

因为 $a=\frac{1}{2}\left(\lambda +\sqrt{{\lambda }^2-4}\right),b=\frac{1}{2}\left(\lambda -\sqrt{{\lambda }^2-4}\right)$ ，是方程 $x^2-\lambda x+1=0$ 的两个根。

设 $h_1\left(\lambda \right)=a=\frac{1}{2}\left(\lambda +\sqrt{{\lambda }^2-4}\right),h_2\left(\lambda \right)=b=\frac{1}{2}\left(\lambda -\sqrt{{\lambda }^2-4}\right)$

${h^{\prime }}_1\left(\lambda \right)=\frac{1}{2}\left(1+\frac{\lambda }{\sqrt{{\lambda }^2-4}}\right)>0$ ，则 $h_1\left(\lambda \right)$ 是增函数。

${h^{\prime }}_2\left(\lambda \right)=\frac{1}{2}\left(1-\frac{\lambda }{\sqrt{{\lambda }^2-4}}\right)<0$ ，则 $h_2\left(\lambda \right)$ 是减函数。

容易得出，当 $4\le d\le n-4$ 时，

$\frac{2a^{d+1}-a^{d-2\lfloor \frac{d}{2}\rfloor +1}-b^{d-2\lfloor \frac{d}{2}\rfloor +1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}-a^{d-2\lfloor \frac{d}{2}\rfloor -1}+2b^{d+1}}{a^{d+2}-a^{d-2\lfloor \frac{d}{2}\rfloor }-b^{d-2\lfloor \frac{d}{2}\rfloor }+b^{d+2}}<\frac{2a^{d+1}+2}{a^{d+1}+1}=2,$

于是 $\frac{{\lambda }^2-n+d+1}{\lambda }<2$ 。我们容易计算出 ${\lambda }_1\left(T_{\left(n,d\right)}\left(\lfloor \frac{d}{2}\rfloor +1\right)\right)<\sqrt{n-d}+1$ . #

3. 结论

本文主要研究了有n个点，直径为d的树其四个子集 $T_{\left(n,d\right)}\left(i\right)$ ， $T_{\left(n,d\right)}^{*}\left(i\right)$ ， ${\bar{T}}_{\left(n,d\right)}\left(i\right)$ ， $T_{\left(n,d\right)}\left(i,j\right)$ 的新的排序方法，并给出了新的研究成果，即：进一步确定了他们的上界。这使得对于满足以上特征的树的排序方面的研究成果更加丰满。这种排序方法所使用方法理论可尝试应用于其他树型，并得到新的成果。

致谢

作者在此感谢一直关心和支持我的领导和同事们，谢谢大家的帮忙与鼓励，感谢我的合作伙伴姜文芳老师给予我的帮助，感谢审稿人在百忙之中能够给予指导。