广义线图与{C_4~1,K_(1,3)~1,K_(1,4)}-free图的符号差

图的邻接矩阵的正,负特征值个数分别被称为图的正,负惯性指数.图G的正惯性指数与负惯性指数之差被称为图G的符号差,记作s(G). 2013年马海成等人提出符号差猜想:对于任意简单图G,都有-c_3(G)≤s(G)≤c_5(G),其中c_i(G)(i∈{3, 5})分别表示G中长为模4余3和模4余1的圈的个数.此文证明了广义线图和不含C_4~1, K_(1,3)~1,K_(1,4)之一作为诱导子图的图满足此猜想.     

含有多个圈的图的秩

研究了含有多个圈的图的邻接矩阵的秩.将k(k≥2)条点不交的路,首和尾分别粘合得到的图称为Θ-图.用Γ(k-1)表示含有Θ-图作为导出子图的(k-1)-圈图的集合,而用C(η,k)表示含有n个顶点和k个边不交的圈的图的集合.确定了Γ(k-1)中秩等于5和6的图以及C(n,k)中秩等于4,5和6的图.     

简单图圈基长度的最大值

图的圈基是图的一个重要结构，一个圈基的长度是该圈基中所有圈的长度之和，本讲座了简单图的圈基长度的最大值，得到了如下结果：设基圈数为k，顶点数为n的简单图的圈基长度最大值为C^*,i)若k≥4且n ≥k 2时，C^*-kn；Ⅱ）若k=2,3,则对任意n≥4，C^*=kn-1,Ⅲ）若n(n≥5）为奇数，则对k(k≥4）的所有可能值，C^*=kn。     

一类含有奇数个顶点的三色有向图本原指数上界

一个三色有向图D是本原的,当且仅当存在非负整数h、k和v,且h+k+v0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)-途径,h+k+v的最小值定义为三色有向图D的本原指数.研究了一类三色有向图,它的未着色图中包含2佗-4个顶点,一个n-圈、一个(n-2)-圈和一个2-圈,给出了本原指数上界.     

关于非交换群上Cayley图的Hamilton分解的一点注记

一、引言图的Hamilton分解问题是图论中的一个引人注目的问题。称一个2k-正则的连通图Γ可以Hamilton分解,是指Γ可以分解为k个Hamilton圈。Alspach在[1]中给出了如下猜测:是否每个2k度连通Cayley图都可以Hamilton分解?文[4]对此问题给出了部分回答,即任意一个4度交换群上连通Cayley图可以分解为2个Hamilton     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

图中相互独立的4圈和含4个点的路

设k是一个正整数，G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.     

非奇异单圈图的刻划

边数等于顶点个数的连通图称为单圈图.本文修正了文献[1]中关于奇异单圈图的充要条件,并且利用该条件证明了文献[2]中一个关于非奇异单圈图的猜想.     

平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.     

不含三圈的k圈图的拟拉普拉斯和拉普拉斯谱半径

k圈图是边数等于顶点数加k-1的简单连通图.文中确定了不含三圈的k圈图的拟拉普拉斯谱半径的上界,并刻画了达到该上界的极图.此外,文中确定了拟拉普拉斯谱半径排在前五位的不含三圈的单圈图,排在前八位的不含三圈的双圈图.最后说明文中所得结论对不含三圈的k圈图的拉普拉斯谱半径也成立.     

6-圈至多含一弦平面图的线性荫度

线性森林是指每个连通分支都是路的图.图G的线性荫度la(G)等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了,若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图,则la(G)=「(△(G))/2」.     

关于2-连通“几乎正则”图的Jackson猜想

Bill Jackson在[1]中作为猜想,提出了一个2-连通“几乎正则”(almost regular)图存在Hamilton圈的充分条件:“如果G是一个次序列为(k,k,…,k,k+1,k+1)的2-连通图,其顶点数不大于3k+2时,G是Hamilton图.本文举例说明     

均衡二部图中点不交的4-圈和6-圈（英文）

设G=(V_1,V_2,E)是一个均衡二部图满足|V_1|=|V_2|=n.令δ_(1,1)(G)=min{d(x)+d(y)|x∈V_1,Y∈V_2}.Amar猜想对任意的s个整数(n_1,n_2,…,n_s),n=n_1+n_2+…+n_s,其中n_i≥2.若δ_(1,1)(G)≥n+s,则G含s个点不交的圈,其长分别为2n_1,2n_2,…,2n_s(见[Discrete Math.,1986,58(1):1-10]).本文证明了若一个点数为4k的均衡二部图G满足δ_(1,1)(G)≥2k+4(k≥3),则G含k-3个4-圈和2个6-圈使得所有这些圈都是点不交的.     

有向完美图

Gallai 和 Milgram 曾经证明,有向图 G 的所有结点可用恰好 α(G) 条互不相交的路来复盖,此处 α(G) 为图 G 的内固数.然而这个结果的好多证明都未指出存在着一最优 内固集 S 以及结点集的一个路剖分 μ_1,μ_2,…μ_k,以致对于所有 i,均有|S∩μ_i|=1.Gallai 和 Roy 曾经独立地证明,在一有向图 G 中,令 k 为一条路所能包含的最多的结点的个数,则 k 至少等于图 G 的色数γ(G).同样,我们不知道是否存在一最优色谱(S_1,S_2,…,S_k)以及一条路μ,以致对于所有的 i,均有|S_i∩μ|=1.在本文中引进了下述概念:1.有向图 G 称为α-有向完美,若对于每一最优内固集 S,均存在结点集合的一个路剖分μ_1,μ_2,…,以致对于所有的 i,均有|S∩μ_i|=1(且此性质对 G 的任一子图亦成立).2.一有向图 G 称为 γ-完美,若对于每一最优色谱 (S_1,S_1,…S_k),均存在一条路 μ,以致对于所有 i,均有|μ∩S_i|=1(且此性质对 G 的每一子图亦均成立).3.一长度为2k+1的奇圈系由2k+1条弧 u_1,u_2,…,u_(2k+1) 所给出,并从而确定了一个有2k+1个结点的序列 x_1,x_2,…,x_(2k+1).一条弦,可以是 G 的一条弧,它联结在以上叙列中不相继的两个结点,或者是 G 的一条弧,它平行上述2k+1条弧中的一条弧.一个奇圈称为反有向的,若i)其长度>3,ii)最长     

三圈图的Harary指数

图G的Harary指数是指图G中所有顶点对间的距离倒数之和. 三圈图是指边数等于顶点数加2的连通图. 研究了三圈图的Harary数, 给出了所有三圈图中具有极大Harary指数的图的结构以及含有三个圈的三圈图中具有次大Harary指数的图的结构.     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

关于诱导子树与图的色数的一个注记

Gyrfs(1975)和Sumner(1981)分别独立地提出了以下猜想:对于任意的树T,存在一个函数f_T(x)使得每一个色数大于f_T(ω(G))的图均包含T作为诱导子图,其中ω(G)表示图G的团数.Gyrfs等(1980)证明了,若一个图G不含三角形和长为4的圈,则G含有任一个χ(G)个顶点的树作为诱导子图.另外,他们还证明了,若G不含三角形,且χ(G)≥m+n,则G一定包含一个特殊的树(m,n)-mop作为诱导子图.本文推广了Gyrfs等(1980)的这两个结果,证明了(1)若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且χ(G)≥t+2k+2k,则G包含任一个t个点的树作为诱导子图;(2)若图G中的每一个顶点至多包含在k个三角形中,且不能够诱导出T,则χ(G)m(k+1)+n,其中T为(m,n)-mop.     

一类双色有向图的本原指数上界

利用圈矩阵和图论的相关知识,研究一类双色有向图,它的未着色图中包含n+m-4个顶点,一个n-圈和一个m-圈,给出了本原条件和指数上界,并对达到指数上界的极图进行了刻画.     

单圈图的邻接矩阵的分类及其最大行列式

一个单圈图G的邻接矩阵是奇异的当且仅当G含完美匹配和4m(m∈N)阶圈，或G和从G中删去唯一圈中的顶点及其关联边后得到的导出子图均不含完美匹配．单圈图的邻接矩阵的最大行列式是4．