关于图的升分解的Alavi猜想

Y.Alavi等人在1987年定义了图的一种新分解,即“升分解”(ascebding subgraph decomposition),并提出猜想:设自然数n≥2,G是由k个分离的星S_1,S_2,…,S_k构成的图,S_i含有a_i条边,n≤a_i≤2n-2,,则G可升分解为星的并。本文证明了当n=2k+i(i=0,1,2)时猜想成立。     

混合幂的除数和（英文）

令S_k(x)=∑d(n_1~2+n_2~2+n_3~k),3≤k∈N.1≤n_1,n_2≤x~(1/2)1≤n_3≤x~(1/k)本文得到了渐近公式S_k(x)=A(k)x~(1+1/k)logx+B(k)x~(1+1/k)+O(x~(1+1/k-δ(k)+ε)),这里A(k),B(k)是只与k有关的常数,δ(3)=5/(42),δ(4)=1/(16),δ(5)=1/(40),并且当6≤k≤7时δ(k)=1/(k2~(k-1)),当k≥8时δ(k)=1/(2k~2(k-1)).     

3-正则图的不共边的完美匹配（英文）

研究3-正则图的一个有意义的问题是它是否存在k个没有共边的完美匹配.关于这个问题有一个著名的Fan-Raspaud猜想：每一个无割边的3-正则图都有3个没有共边的完美匹配.但这个猜想至今仍未解决.设dim（P（G））表示图G的完美匹配多面体的维数.本文证明了对于无割边的3-正则图G,如果dim（P（G））≤14,那么k≤4：如果dim（P（G））≤20,那么k≤5.     

循环图C_(2n)(1,(2n+1)/3)的匹配可扩性

称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.根据循环图的性质研究了图C_(2n)(1,(2n+1)/3)的匹配可扩性,证明了对于任意的n(n≥4),C_(2n)(1,(2n+1)/3)是3-偶匹配可扩的.     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).     

图中具有正交（g,f）因子分解的子图

设G是一个 (mg +k ,mf -k) -图 (1≤k 相似文献   

Hadwiger猜想的一个等价命题

Hadwiger 猜想说:如果简单图 G 的色数为 k,那么它就含有能收缩到 k 点完全图 S_k 的子图.当 k=5时,这个猜想等价于平面地图四色定理.本文用满色集概念来给出Hadwiger 猜想的一个等价命题。当 k=5时,它也是平面地图四色定理的一个新的等价命题.     

一类完全三部图的色唯一性

用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.     

图的全控制数和匹配数的可比较性

设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G) 1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较.     

关于代数连通度的一个注记

图G=(V,E)的次小的拉普拉斯特征值称为G的代数连通度,记为α(G).设δ(G)为G的最小度.Fiedler早在1973年便证明了α(G)≤δ(G),但他未能给出等号成立的极图刻划.后来,我们在[6]中确定了当δ(G)≤1/2|V(G)|时α(G)=δ(G)的充要条件.本文中,我们将确定任意情况下α(G)=δ(G)成立的所有极图.     

A formula for the non-integer powers of the laplacian

We provide an elementary formula for the non-integer powers of the Laplace operator in the Euclidean spaces. Such formulas are helpful in establishing the elliptic nature of some pseudo-differential operators arising from the study of energies of knotted loops in space, and possibly of embedded submanifolds in a Riemannian manifold. Supported in part by an NSF grant.     

Several sharp upper bounds for the largest laplacian eigenvalue of a graph

Let K be the quasi-Laplacian matrix of a graph G and B be the adjacency matrix of the line graph of G,respectively.In this paper,we first present two sharp upper bounds for the largest Laplacian eigenvalue of G by applying the non-negative matrix theory to the similar matrix D~(-1/2) KD~(1/2) and U~(-1/2)BU~(1/2),respectively,where D is the degree diagonal matrix of G and U=diag(d_u,d_v,:uv∈E(G)). And then we give another type of the upper bound in terms of the degree of the vertex and the edge number of G.Moreover,we determine all extremal graphs which achieve these upper bounds.Finally, some examples are given to illustrate that our results are better than the earlier and recent ones in some sense.     

完全多部图的无符号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.     

On the number of Laplacian eigenvalues of trees less than the average degree

Laplacian eigenvalues of trees have been studied by many researchers. They are closely related to the diameter, domination number, matching number and Laplacian energy of trees. The goal of this paper is to prove a conjecture on the number of Laplacian eigenvalues of trees that are less than the average degree.     

两类双圈图的Laplacian谱确定问题

设G=(V(G),E(G))是一个简单连通图,V(G),E(G)分别表示图G的顶点集和边集.如果与图G同Laplacian谱的图都与G同构,则称图G由它的Laplacian谱确定.该文定义了两类双圈图Q(n;n_1,n_2,···,nt)和B(n;n_1,n_2),证明了双圈图Q(n;n_1),Q(n;n_1,n_2),Q(n;n_1,n_2,n_3)和双圈图B(n;n_1,n_2)分别由它们的Laplacian谱确定.     

欧氏空间子流形的第一特征值的估计

本文利用浸入在欧氏空间中的子流形的第二基本形式的长度平方估计其Laplace算子的第一特征值的上界,从而建立紧致子流形等距同构于球面的一个特征.