完全多部图的无符号Laplacian特征多项式(英文)

For a simple graph G,let matrix Q（G）=D（G） + A（G） be it’s signless Laplacian matrix and Q G （λ）=det（λI Q） it’s signless Laplacian characteristic polynomial,where D（G） denotes the diagonal matrix of vertex degrees of G,A（G） denotes its adjacency matrix of G.If all eigenvalues of Q G （λ） are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K（n₁,n₂,···,n_t）.We prove that the complete t-partite graphs K（n,n,···,n）t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K（m,···,m）s（n,···,n）t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K（m,···,m,）s1（n,···,n,）s2（l,···,l）s3.     

图类■中的整谱图

设图G是一个简单图,图G的补图记为-G,如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Ka都是整谱图[1].本文确定了图类■中的所有整谱图.     

图Gn的优美表示

将给出三个结果：（i）如果图G是SZ（｜S｜=n≥2）上的整数和图,那么0∈S当且仅当图G至少有一个（n-1）度顶点;（ii）图G（G≠K2）是至少有两个零点的整数和图当且仅当G■K2·Gn;（iii）设图G（G≠K2）是SZ上的整数和图,｜S｜=n＋2,n∈N＋.若图G至少有两个零点,则S={mx｜m=-1,0,1,2,…,n;x∈Z且x≠0}.     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).     

双圈图的距离无符号拉普拉斯谱半径

连通图$G$的距离无符号拉普拉斯矩阵定义为$\mathcal{Q}(G)=Tr(G)+D(G)$, 其中$Tr(G)$和$D(G)$分别为连通图$G$的点传输矩阵和距离矩阵. 图$G$的距离无符号拉普拉斯矩阵的最大特征值称为$G$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

图类αK_a∪βCP(b)中的一类特殊整谱图

图G是一个简单图,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图.鸡尾酒会图CP(n)=K_(2n)-nK2(K_(2n是完全图)和完全图K_a都是整谱图.μ_1表示图类αK_a∪βCP(b)的一个主特征值,确定了当μ_1=2a并且a-1>2b-2时,图类αK_a∪βCP(b)中的所有的整谱图.     

图G_n的优美表示

将给出三个结果:(i)如果图G是SZ(|S|=n≥2)上的整数和图,那么0∈S当且仅当图G至少有一个(n-1)度顶点;(ii)图G(G≠K2)是至少有两个零点的整数和图当且仅当G■K2·Gn;(iii)设图G(G≠K2)是SZ上的整数和图,|S|=n+2,n∈N+.若图G至少有两个零点,则S={mx|m=-1,0,1,2,…,n;x∈Z且x≠0}.     

图类^-αKα∪βCP（b）中的整谱图

设图G是一个简单图,图G的补图记为^-G,如果G的谱都是整数,就称G是整谱图．鸡尾酒会图CP（n）=K2n-nK2（K2n是2n阶完全图）和完全图Kα都是整谱图．本文确定了图类^-αKα∪βCP（b）中的所有整谱图．     

几类多圈图的拉普拉斯谱刻画

设图G是一个简单连通图. 如果任何一个与图G同拉普拉斯谱的图都与图G同构,则称图G是由其拉普拉斯谱确定的. 定义了双圈图\theta_{n}(p_1,p_2,\cdots,p_t) 和m 圈图H_n(m\cdot C_3;p_1,p_2,\cdots,p_t). 证明了双圈图\theta_{n}(p)和\theta_{n}(p,q),三圈图H_n(3\cdot C_3;p)和H_n(3\cdot C_3;p,q)分别是由它们的拉普拉斯谱确定的.     

关于图的L(2,1)标号核图

图的L(2,1)标号核图来自频率分配问题而导致的图论问题.在本文中,我们证得(i)对任意简单图G,存在G的一个标号核图Gcore,使得L(G)=L(Gcore)和L(G)≥|V(Gcore)|-1;(ii)设图G有p个顶点且边集|E(G)|≠φ,存在路 Pi G(1≤i≤m)和路Hs G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.     

关于图的上可嵌入性的一个注记

任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs" [J East China NormUniv Natur Sci, Sep. 2010, No. 5, 1-13] 中,全面地阐述了近30 年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:
猜想1 设G 为简单连通图, 且G 的每条边含在一个三角形K₃ 中, 则G 是上可嵌入的.
猜想2 设c 为任意的正数, 则存在一个自然数N(c), 使得对每一个图G, 若G 的点数n ≥ N(c), 且最小度δ(G) ≥ cn, 则G 是上可嵌入的.
本文的主要工作是否定上述两个猜想, 同时探讨上述猜想成立的条件且得了一些新结果, 并提出有关进一步研究的问题.     

On mixed block graphs

A mixed complete graph is obtained from a directed cycle of length at least three by adding all the possible arcs between any non-adjacent vertices of the underlying cycle. A mixed block graph is a strongly connected directed graph whose blocks are mixed complete graphs. In this paper, we give the inverse of the distance matrix of the mixed block graph.     

给定顶点数和边数的连通图的Q-谱半径的界

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q1≥q2≥…≥qn.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤(n2).如果对于任意的G∈C(n,m)都有q1(G*)≥q1(G)成立,图G*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n...     

网络结构的边毁裂度

在毁裂度的基础上,研究图的边的毁裂度.通过优化组合、归纳假设的方法界定了图的边毁裂度的值,如笛卡尔积图:Pm×Pn,Pm×Cn,Cm×Cn,Km×Kn,并界定了G=G1×G2的边毁裂度的界.最后给出了一些基本图,如路、圈、星图、完全二部图Km,n的线图边毁裂度.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

关于有限群的强幂图的谱

令$G$是一个阶为$n$的有限群, $G$上的强幂图定义为: 以$G$为顶点集, 对于两个不同的元素$x$和$y$, 如果存在两个不超过$n$的正整数$n_1, n_2$使得$x^{n_1}=y^{n_2}$, 则$x$和$y$ 之间连一条边. 本文给出了$G$上强幂图的距离矩阵和邻接矩阵的特征多项式, 并且计算了其距离谱和邻接谱.     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题，并确定了该序的前两个图及其相应的度距离，其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．     

Graham’s pebbling conjecture on product of complete bipartite graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are complete bipartite graphs.     

变换图的直径及Brualdi猜想

设Ｒ＝（ｒ１，ｒ２…ｒｍ）及 Ｓ＝（Ｓ１，Ｓ２，…，Ｓｎ）为两个正整数向量，满足Σｍｉ＝１ｒｉ＝Σｎｊ＝１ｓｊ＝ Ｋ．记Ｇ（Ｒ，Ｓ）为（０，１）－矩阵类 Ｕ（Ｒ，Ｓ）的变换图．Ｂｒｕａｌｄｉ在文山中给出了 Ｇ（Ｒ，Ｓ）的直径厂（Ｇ（Ｒ，Ｓ））的一个上界：ｍｎ／２－１，并猜想Ｄ（Ｇ（Ｒ，Ｓ））≤ｍｎ／４．本文通过对有向图围长的研究得到了Ｄ（Ｇ（Ｒ，Ｓ））的一个新的上界：１／２ｍｎ－１／６ｔ（ｔ－１）（４ｔ＋１），其中Ｔ＝　　．