K(1,4)-自由的模k泛圈图(英文)

设G是2-连通的K1,4自由图.本文证明了当δ(G)≥k 1时,G是模k泛圈图.这一结果肯定了猜想2,继而也肯定了Thomassen猜想在2-连通图中的正确性.     

关于Sumner-Blitch猜想的一个注记

设G是一个图。G的最小度，连通度，控制数，独立控制数和独立数分别用δ，k，γ，i和α表示，图G是3－γ-临界的，如果γ=3，而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想：任意连通的3－γ临界图满足i=3，本文证明了如果G是使α＝k 1≤δ的连通3－γ-临界图，那么Sumner-Blitch猜想成立。     

关于3正则图的三匹配交猜想(Ⅱ)

Fan和Raspaud 1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配．本文证明了如下结果：若G是一个圈4-边连通的无桥3正则图，且存在G的一个完美匹配M1使得G—M1恰为4个奇圈的不交并，则存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=Φ。     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

二部图是可迹的一个充分条件

本文证明了以下结果:设G=(X,Y;E)是连通的二部图,如果4≤|Y|≤|X|≤|Y|+1,且NC_2≥|X|-1,则G是可迹的。从而表明[2]中的猜想对二部图是成立的。     

K1,p-受限图

图G中同构于Ki,p的子图叫G的p-爪(P≥3)．如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥P-2,则称G为K1,p-受限图,它是无爪图的推广．本文证明了连通、局部2-连通的K1,4-受限图是完全圈可扩的．     

极小3边连通可折图

本文证实了Catlin和赖虹建的猜想:设G是非平凡连通简化图,如果F(G)=2,则G∈{K_2,t;t≥1}.     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

收缩临界5-连通图的平均度

M．Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10．本文构造了一个反例证明M．Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界．     

广义友谊图乘积上的Graham pebbling猜想

连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.     

最大临界2-边连通图的结构

假若G是一个2-边连通图,但对G中任一点v,G\{v}不是2-边连通图,则称G为一个临界2-边连通图。具有最大边数的临界2-边连通图称为一个最大临界图。文[1]中,作者给出了p阶临界2-边连通图的边数的最大界f(p),列出了最大临界图结构的不同情况。并且他们猜测已经找出所有这类图。本文将证明他们的猜想是正确的。     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

高度图的关联色数

为了解决强边着色猜想,1993年,Brualdi和Massey（Discrete Math. (122)51-58)引入了关联着色概念,陈东灵等证明了对于△（G）=n-2的图G.inc(G)≤△(G) 2,其中n是G的阶数,本将进一步探讨在什么条件下,它的关联色数肯定是△（G） 1,又在什么条件下,肯定是△（G） 2。     

K1,4-受限图的路可扩性

图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,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 是上可嵌入的.
本文的主要工作是否定上述两个猜想, 同时探讨上述猜想成立的条件且得了一些新结果, 并提出有关进一步研究的问题.     

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

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

图的最大亏格的一个性质

本文所考虑的图均指有限元向图，没有解释的术语和记号同[1]．一个图称为简单图如果不含重边及环．曲面S这里指一个紧的，连通的，2－维闭流形（定向或不可定向），其亏格记为g（S）．连通图G在曲面S上的一个2－胞腔嵌入意指存在一个1－1连续映射h：G→S使得S＼h（G）的每个连通分支与圆盘拓扑同胚．连通图G的定向亏格γ（G）（或不可定向亏格γ（G））是指最小的整数k使得G在亏格为k的定向（或不可走向）曲面S上有2－胞腔嵌入；而图G的最大定向亏格，也常称之为最大亏格，记为γM（G）,是指最大的整数k使得G在亏格为k定向曲面S上有…     

图的正(负)特征值平方和界的估计

图G的特征值是指该图邻接矩阵的特征值,图G的正特征值平方和用符号S+(G)表示.关于图的正(负)特征值平方和界的估计,[Discrete Math.,2016,339(9):2215-2223]给出一个有趣的猜想:对于连通图G有min{S-(G),S+(G)}≥n-1,其中n表示图G的顶点数,S-(G)表示图G负特征值...