色多项式系数的一点注记

本文将讨论简单图,以n和m分别表示图G的点数和边数。文中不加说明的术语和记号可参阅[1]。G的顶点着色,是对G的顶点分配颜色,使邻接的顶点有不同的颜色。同一种颜色的顶点的全体组成的集合,称为G的一个色类,以m_r(G)表示将G的顶点集分成Υ个色类的不同分划数,定义多项式为图G的色多项式。显然,当m>0时,m_1(G)=0为方便起见,今后讨论的图G均假定m>0。Whitney(1932)得到如下的着名结果(参见[1],P.69)。     

单圈图谱的界

设G是有n个点的连通单圈图(即恰含一个圈的连通图)。λ_1(G)是G的最大特征值。G_n是n个点的圈。S_n~3是由星图K_(1,n-1)连接它的两个度为1的点而得到的图,则下列不等式成立λ_1(C_n)=2≤λ_1(G)≤λ_1(S_n~3)左边等号成立,当且仅当G≌D_n。右边等号成立,当且仅当G≌S_n~3。     

Bounds of Spectral Radii of Weighted Trees

Graphs for the design of networks or electronic circuits are usually weighted and the spectrum of weighted graphs are often analyzed to solve problems. This paper discusses the spectrum and the spectral radii of trees with edge weights. We derive expressions for the spectrum and the spectral radius of a weighted star,together with the boundary limits of the spectral radii for weighted paths and weighted trees. The analysis uses the theory of nonnogative matrices and applies the “moving edge” technique. Some simple examples of weighted paths and trees are presented to explain the results. Then, we propose some open problems in this area.     

具有次大和第三大谱半径的n阶 2-树(英)

利用 Perron 向量的概念, 分别刻画出谱半径达到第二大和第三大的 $n$ 阶 2-树. 特别对于 $n=6$, 给出了谱半径依次减小的 5 个 6 阶 2-树.     

图与其补图谱半径之和的新上界

该文给出了图与其补图谱半径之和ρ(G)+ρ(Gc)的新上界,对任一n阶图G,有:p(G)+p(GC)≤((2-1/t)n(n-1))和p(G)+p(GC)≤((2-1/T)n(n-1))其中t=min{k,(k-)},T=max{k,(k-)},k,(k-)分别为图G和其补图Gc的色数.从而改进了[6],[8],[10]的结果.     

图可重构性的一点注记

设图G的顶点集为{v_1,v_2,…,v_n}.G的途径矩阵D(G)=(d_(ij)是n阶方阵,此处d_(ij)是G中从v_i出发长为j的途径数,D(G)的行向量集X的子集{x_1,x_2,…,x_r}称为X的最小线性相关集,如果{x_1,x_2,…x_r}线性相关且对X的任一(r-1)之子集均是线性无关.称数r为G的最小线性相关数.当X线性无关时,定义G的最小线性相关数r=∞.对1≤i≤n,记d_i为点v_i在G中的次,G_i是图G剔除点v_i以及与v_i关联的边而得到子图.设r_i是G_i的最小线性相关数,我们有下列定理:如果存在某一数i使r_i>2d_i,则G是可重构的.特别,我们重新得到下述结果:如果存在某一子图G_i,使得G_i的所有特征向量均不与C=(1,…,1)_t正交,则G是可重构的.     

图可重构性的一点注记

设图G的顶点集为{u_1,u_2,…,u_n}。G的途径矩阵D(G):(d_(ij)是n阶方阵,此处d_(ij)是G中从u_i出发长为j的途径数,D(G)的行向量集X的子集{x_1,x_2,…,x_r}称为X的最小线性相关集,如果{x_1,x_2,…x_r}线性相关且对x的任一(r-1)之子集均是线性无关。称数r为G的最小线性相关数。当X线性无关时,定义G的最小线性相关数r=∞。对1≤i≤n,记d_i为点u_i在G中的次,G_i是图G剔除点u_i以及与u_i关联的边而得到子图。设r_i是G_i的最小线性相关数,我们有下列定理:如果存在某一数i使r_i>2d_i,则G是可重构的。特别,我们重新得到下述结果:如果存在某一子图G_,使得G_i的所有特征向量均不与C=(1,…,1)~t正交,则G是可重构的。     

单圈图谱的界

设G是有n个点的连通单圈图(即恰含一个圈的连通图)。λ_1(G)是G的最大特征值。C_n是n个点的圈。S_n~3是由星图K_(1,n-1)连接它的两个度为1的点而得到的图,则下列不等式成立左边等号成立,当且仅当G■C_n。右边等号成立,当且仅当G■S_n~3。