非二部图的最小特征值

设G是一个简单图,其特征值定义为它的邻接矩阵的特征值。在给定阶数的非二部图中,本文确定了最小特征值达到极小的图,并在文末提出一个问题及相关的猜想。

Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为l(g(G)≤l≤c(G))的圈,其中g(G),c(G)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[(n^2)/4]-n+5的n阶非二部图为弱泛圈图.1999年Bollobás和Thomason证明了边数不小于[(n^2)/4]-n+59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[(n^2)/4]-n+12,则G为弱泛圈图.

不含P_t的非二部连通图的最小Q-特征值

对于一个连通图而言,它的最小Q-特征值为零当且仅当它是二部图.图的最小Q-特征值常被用来衡量一个图的非二部程度,因而受到研究者的广泛关注.文中研究了图中存在长路的最小Q-特征值条件,分别确定了最小Q-特征值最小的不含路Pt的非二部单圈图和非二部连通图.

图的最小Q-特征值

证明了,若连通图G不是二部图,则其最小Q-特征值q(G)≥1/n(D+1),其中D是G的直径.另外,还给出了图G的最小Q-特征值与其子图的最小Q-特征值之间的关系.

第二大特征值小于1的一类图

设G是简单连通图,λ_2(G)为G的第二大特征值.本文给出了所有使λ_2(G)<1且含有唯一三角形的图.