3-连通P3-支配图的Hamilton性

引进了P3-支配图并对BROERSMA HJ和VUMAR E提出的作为半无爪图的一个超类,研究了这类图的一些性质.得到:若G是n阶3-连通P3-支配图,则当n≤5δ-4时,G是Hamilton图.     

几类特殊图的优美性

证明了对任意大于1的自然数n,p,当m≥2p＋2时,非连通图Fm∪Kn,p和Fm,2 m∪Kn,p是优美图;当m≥3时,图Fm∪St（n）是优美图;当m≥4,图Fm,2 m∪St（n）和Fm,2 m∪Gr是优美图.     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

广义Mycielskian图的连通度(英文)

Mycieski定义了一个图的运算即把一个图G变换为一个称为G的Mycielskian图的新图μ(G).广义Mycielskian图μm(G)(m≥0)是图的Mycielskian图的一个自然推广.本文证明对任意非平凡连通图G有κ(μm(G))=min{δ(G)+1,(m+1)κ(G)+1},而且对于m,i≥1,λ(μm(G))=λ(G)+i当且仅当δ(G)=λ(G)+i 1,其中κ(G),λ(G)和δ(G)分别为图G的连通度,边连通度和最小度.     

无限图的匹配扩张

作为有限图的ｎ－可扩性的一个自然推广，本文引入了ｎ－可扩无限图的概念．我们讨论了ｎ－可扩无限图的若干特性，并证明了无限Ａｂｅｌ群上的连通Ｃａｙｌｅｙ图是２－可扩的当且仅当它不是双向无限路．     

一类一致最优完全多部图

以(n,m)表示具有n个顶点m条边的图的集合.假设图G的边可靠,而顶点可靠的独立概率为p,若对于所有1 p∈(0,1),图G均为(n,m)中的最可靠图,则称G为一致最优图.本文证明了完全k-部图K(b,(b+2)k 1)在其图类中是一致最优的,而当i>3时,完全k-部图K(b,(b+2)k 2,b+i)在其图类中不是一致最优的.     

一类(0,1)矩阵变换图的Hamilton性

设G(R,S)表示m×n阶(0,1)矩阵类(R,S)的变换图.Brualdi提出问题:“G(R,S)有Hamilton圈吗?”当min{m,n}=2时,文献[3]中证明了此变换图是Hamilton连通的,并且是泛圈的(除K_1,K_2外),从而给该问题一个肯定的答案,当min{m,n}=3时,本文进一步地证明了此变换图是边Hamilton的(除K_1,K_2外),从而也给出该问题一个肯定的答案。     

图P_n~3的优美标号

定义了图 P3 n,证明了当 n =6 k 2及 n =6 k 4时 ,图 P3 n是优美图 ,并得到它们的优美标号 ,其中 k是任意自然数 .     

一类Cayley图的边传递性和Hamilton性

对每个简单图,可定义一个相应的Cayley图。本文证明了当简单图是边传递时,它对应的Cayley图也是边传递的,并证明了路对应的Cayley图(Bubble sort graph)和星对应的Cayley图(Star graph)都是Hamilton图。     

图P3n的优美标号

定义了图Ｐ＾３ｎ,证明了当ｎ＝６ｋ＋２及ｎ＝６ｋ＋４时,图Ｐ＾３ｎ是优美图,并得到它们的优美标号,其中ｋ是任意自然数。     

拟无爪哈密尔顿图的邻集条件

作为无爪图的一种推广,拟无爪图类Ainouche引入．已经知道：如果阶数为礼的3-连通无爪图G,对于每一对距离为2的点都有IN（x）∪N（y）｜≥（2n-6）／3,那么图G是哈密尔顿的．在本文中,推广了上述的结论并且得到：如果阶数为n的3-连通拟无爪图G,对于每一对距离为2的点都有｜N（x）∪N（y）｜≥（2n-6）／3,那么图G是哈密尔顿的．     

哈林图的偶匹配可扩性

称图 G 的匹配 M 是偶匹配,如果 M 中的边关联的点集在 G 中的导出子图是偶图,即 G[V(M)] 是偶图. 称图 G 是偶匹配可扩的,如果 G 的每一个偶匹配 M 都包含在 G 的一个完美匹配中. 本文的主要结果是:哈林图 H=(T∪C)是偶匹配可扩的当且仅当它的特征树 T 同构于 K1,3、K1,5 或者 K1,7.     

拉普拉斯整谱三圈图的刻画

如果一个图的拉普拉斯谱都是由整数构成的,那么这个图称为拉普拉斯整谱图。本文首先刻画了拉普拉斯三圈基图中最长圈的圈长c（H）≤6的整谱图,并且找出这些连通的拉普拉斯三圈基图的整谱图;其次刻画了至少含有一个悬挂点的连通三圈图的拉普拉斯整谱图,最后证明了至少含有一个悬挂点的连通三圈图的拉普拉斯整谱图都是由它们的拉普拉斯谱唯一确定的。     

二部图G的F－Hamilton问题

设Ｆ是二部图Ｇ的１－因子，如果Ｇ中有含Ｆ的Ｈａｍｉｌｔｏｎ图，则称Ｇ是Ｆ－Ｈａｍｉｌｔｏｎ的．本文给出了二部图Ｇ是Ｆ－Ｈａｍｉｌｔｏｎ的一个充要条件．     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.     

关于3-可选平面图的一点注记

图G=（V,E）称为L-可染的,如果对给定的列表L={L（v）：v∈V（G））,存在图G的一个正常染色c,满足c（v）∈L（v）．如果对任何｜L（v）｜≥南的列表,图G都是L-可染的,则称图G为k-可选的．本文我们证明了平面图不含4圈,5圈,7圈和三角形距离小于2是3-可选的．     

平面图的圈基内插性质

图Ｇ的一个圈基的长度是该自基中所有圈的长度之和．设Ｃ－、Ｃ－分别是Ｇ的最小、最大圈基长度．如果对任一自然数Ｃ，Ｃ－＜Ｃ＜Ｃ－，都存在Ｇ的一个长为Ｃ的圈基，则称Ｇ有圈基内插性质．本文证明了无三角形的外平面图没有圈基内插性质，并说明存在围长任意大且有圈基内插性质的平面图．     

单循赛赛程安排公平性问题的数学模型

探讨了n支球队在同一块场地上进行单循环赛时赛程安排的公平性问题．提出了公平性的2个评价指标：各队相邻两场比赛间最小间隔场次数mn和最大间隔场次数Mn．证明了mn的上限为[(n-3)／2]，并且当mn取到上限时，Mn的下限为[(n-1)／2]；提出了mn取到上限且Mn取到下限的赛程表构造法，并证明了此法的正确性；最后用构造法列举出n=5，6的赛程表．