完全等部二分图kn,n的迭线图Lm(kn,n)的谱特征

研究了完全等部二分图Ｋｎ,ｎ的迭线图Ｌ＾ｍ（Ｋｎ,ｎ）的谱特征,证明了当ｎ≥７时,Ｌ＾ｍ（Ｋｎ,ｎ）以谱为特征。     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

变换图的正则性和谱半径

在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计．     

完全二部图的Kp,p-分解大集的存在谱北大核心CSCD

令H,G是两个简单图,G是H的一个子图.H的G-分解,记为（λH,G）-GD,是指将图λH的所有边分拆为若干个与G同构的子图（称为G-区组）.H的G-分解的大集,记为（λH,G）-LGD,是指图H的所有与G同构的子图的一个分拆Β1,Β2,…,Βm,使得每个Bj（1≤j≤m）为一个（λH,G）-GD （称为小集）.本文中,我们对完全二部图的K（p,p）-分解的大集进行了研究,利用Kv的λ重Kκ-因子大集的存在性结果,采用直接构造的方法,得到了大集（λK（m,n）,K（p,p））-LGD的存在谱,其中p为任意素数.     

强正则图的一些性质

文[3]给出了强正则图的概念及有关性质,本文在此基地上利用图的谱性质,得到了强正则图的又一些性质。     

近完全二部图的交叉数

图G的交叉数是刻画图的非平面性的一个重要参数.它是指图G在平面上的所有画法中边与边之间交叉数目的最小值.确定具体图类的交叉数是图的交叉数问题中一个经典的研究方向.Zarankiewicz于1954年提出了完全二部图交叉数的猜想:■.1971年,Kleitman证明了当min{m,n}≤6时,上式成立.由于其难度,完全二部图交叉数的研究进展是较缓慢的.至今,完全二部图K_7,n(n≥11)的交叉数都还未确定.然而,我们发现研究近完全二部图的交叉数可了解在完全二部图中加边与完全二部图交叉数的增长程度之间的关系.因此,为了促进完全二部图交叉数的研究,本文借助旋系与交叉数之间的关系、图的结构性质以及图的顶点度局部修改法确定了五个近完全二部图的交叉数.     

二部图平衡二部划分的上界

设G(V,E)是一个图,V_1,V_2是V的一个二部划分,当||V_1|-|V_2||≤1时,称V_1,V_2是V的一个平衡二部划分,用e(V_1,V_2)表示一条边的两个端点在不同划分里边的总数目.最小平衡二部划分是指寻找G(V,E)的一个平衡二部划分使得e(V_1,V_2)最小.研究了二部图和哈密尔顿二部图,得到它们的最小平衡二部划分的上界分别为[m/2]和(n+2)/2.     

二部多重图路因子分解的存在谱

若二部多重图λK_m,n的边集可以划分为λK_m,n 的P_v-因子,则称 λK_m,n存在P_v-因子分解.当v是偶数时, Ushio和Wang及本文的第二作者给出了λK_m,n存在P_v-因子分解的充分必要条件.同时提出了当v是奇数时λK_m,n存在P_v-因子分解的猜想.最近我们已经证明当v=4k-1时该猜想成立. 对于正整数k,文中证明λK_m,n 存在P_4k+1-因子分解的充分必要条件是: (1) 2km ≤ (2k+1)n, (2) 2kn ≤(2k+1)m, (3) m+n ≡ 0 (mod 4k+1), (4)λ (4k+1)mn/[4k(m+n)]是整数. 即证明:对于任意正整数k, 当v=4k+1时上述猜想成立，从而最终完成了该猜想成立的证明.     

Hamiltonian二部竞赛图

设 T(n,n)表示 n×n 二部竞赛图。本文证明了:如果 uv 是 T(n,n)的一条弧,蕴含d~-(u) d~ (v)≥n-2≥4,则 T(n,n)是 Hamilton 图,除非 T(n,n)属于两类已被刻划的特殊图类。     

图G为自构线图的充要条件

首次给出自构线图的定义,并证明:简单图G为自构线图的充要条件是图G为2-正则简单图.     

完全图删边子图的子刻画

In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix.     

广义鸡尾酒宴图的谱特征

In the paper, we prove that all generalized cocktail-party graphs with order at least 23 are determined by their adjacency spectra.     

On Integral Graphs which Belong to the Class $\overline {\alpha K_{a,a,a}\cup \beta K_{b,b,b}}$

Let $G$ be a simple graph and let $\overline G$ denote its complement. We say that $G$ is integral if its spectrum consists entirely of integers. In this work we establish a characterization of integral graphs which belong to the class $\overline {\alpha K_{a,a,a} \cup\beta K_{b,b,b}}$, where $mG$ denotes the $m$-fold union of the graph $G$.     

K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS

§ 1　IntroductionLet Km,nbe a complete bipartite graph with two vertex sets having m and n vertices,respectively.A subgraph F of Km,n is called a spanning subgraph of Km,nif F contains allthe vertices of Km,n.Itis clearthata graph with no isolated vertices is uniquely determinedby the setofits edges.So in this paper,we considera graph with no isolated vertices to bea setof2 -elementsets ofits vertices.Letk be a positive integer.A K1 ,k-factor of Km,nis aspanning subgraph F of Km,nsuch th…     

关于二部图K(m,n)-2的色唯一性

设Ｋ（ｍ，ｎ）－２表示从完全二部图Ｋ（ｍ，ｎ）中删去任意２条边所得之图．本文证明了：１．若ｎ≥ｍ≥３，且ｎ＋ｍ＞(（ｎ－ｍ）^２＋８)^1/2＋１/２（ｎ－ｍ）^２＋４，则Ｋ（ｍ，ｎ）－２是色唯一图；２．当ｍ≥３时，Ｋ（ｍ，ｍ）－２，Ｋ（ｍ，ｍ＋１）－２和Ｋ（ｍ，ｍ＋２）－２均是色唯一图．     

完全二部多重图的K2,3-因子分解

如果完全二部多重图λK<,m,n>的边集可以划分为λK<,m,n>的K<,p,q>-因子,则称λK<,m,n>存在K<,p,q>-因子分解.当p=1和q=2时,λK<,m,n>的K<,1,2>-因子分解的存在性问题已被完全解决.最近我们得到了当λ=1时,K<,m,n>存在K<,2,3>-因子分解的充分必要条件.对于任意...     

Off‐diagonal and asymptotic results on the Ramsey number r(K2,m,K2,n)

An upper bound on the Ramsey number r(K_2,n‐s,K_2,n) where s ≥ 2 is presented. Considering certain r(K_2,n‐s,K_2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K_2,n‐s,K_2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K_2,m,K_2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K_2,m,K_2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003     

关于图C_n(a_1,a_2,…,a_n)的整数幻谱

一般没有有效的方法得到图G的幻谱.本文给出了一种整数幻谱的分析方法,讨论了图Cn(a1,a2,…,an)的整数幻谱问题,得到Cn(1,3,…,2n-1)与Cn(2,4,…,2n)等4类图的整数幻谱及一些新的结果.     

Bipartite Subgraphs of Graphs with Maximum Degree Three

We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound . Received: July 17, 1995 / Revised: April 5, 1996