子课题之二：Hamiltonian染色问题：

附与琼州大学的哈密顿图学科相关的若干专题（其中一些专题竟还没有见到国内做一篇论文--如有许多数学“诺贝尔奖”得主做的2个专题：课题三：“图同态”和课题十九：“Szemerédi正则引理”，是为遗憾）：

课题一：随机图（最近些年来涌出现复杂网络这个非常火热的学科，它的很多论文不断在《自然》《科学》发表，而Erdös 和 Rényi 建立的随机图理论被公认为是开创复杂网络理论的系统性研究。因时间紧,我就先简约做这个网页介绍些随机图的基本概念、理论及某些应用以及这个复杂网络网页）：

课题二：Cayley图即凯莱图的哈密顿性等问题。

凯莱图最先是由英国科学促进协会主席凯莱于1880年提出的，它由一个群G和它的子集S所确定一个凯莱图G（其性质决定于G和S。当S有单位元时，每个点都有环，否则没有环点；当S=S^-时，是无向图；当S也是生成集时是连通图，再G是什么性质的群-图也有相应的性质，等）。

众所周知，国际数学联盟主席László Lovász的一类凯莱图--点可迁图的哈密顿性猜想是一个悬而未决的著名猜想：连通有限可迁图都有哈密顿路（因5-可迁图没有哈密顿圈，如此Lovász教授猜想除此外都有哈密顿圈。又因每个凯莱图都是点可迁图，如此有更弱些的猜想：每个凯莱图都有哈密顿圈。这里第3行说László Babai却提出相反的猜想：并非凯莱图都有哈密顿圈。然而这问题之艰巨如就是要证明或否定“凯莱图有哈密顿路”甚至“有大于某长度的路”或虽阿贝尔群已有更进一步的结果如“有限Abel群上围长为3,阶数至少为3的连通Cayley图是泛圈的”等但对一般的群等仍是非常困难，更不用说哈密顿圈！Knuth的名著中说这问题来源于英国的campanology，但也似乎启蒙于Rapaport在1959年的这论文。见Savage说与灰密码密切）；（Lovász主席还提出一些相关的著名猜想，如这杂志中提出“n连通图G的任何n条独立边集N都含在一圈中或N是奇割集”也非常著名。Lovász教授1979年证明n=3时这猜想成立；Erdős和Győri证明n=4时成立；Sanders证明n=5时成立；其后来信说我的证明是“确的nice”的Kawarabayashi教授最近以非凡才智用40余页长论文证明能有至多2个不相交的圈含N集--虽然离解决猜想还很远但比这么多年仅解决n=5又让人似乎看到某些希望）。下面再说上面Lovász主席的凯莱图猜想：

几十年来已做了很多研究，虽然进展不大，但最近，Igor Pak教授（他是哈佛大学博士、国际数学联盟主席László Lovász的博士后）和麻省理工Kleitman的博士Rados Radoicic在2009年证明“若有限群G的生成集S满足|S|≤log₂|G|则相应的凯莱图G(G,S)有哈密顿圈”（见Hamiltonian paths in Cayley graphs. Discrete Math. 309 (2009), 17, 5501--5508），这对都不知道凯莱图是否全都有哈密顿路的情况下确实是一个可喜的进展。然而也应看到这样的指数关系表明|S|相对于|G|小得很多。因此，|S|是否可再大一些？因本课题组有2个代数教授，就增加此问题，让他们尝尝凯莱图的味道。就是不成功，只要功夫下得深，也应可从其它途径做出些成果。

附：因上面课题研究历史长而且结论弹性大，如此与课题有关的问题很多。如Enomoto等（见 Degree sums and covering cycles. J. Graph Theory 20 (1995),4, 419—422）s₃>|G|-1，则G能被2个圈覆盖（更早的1987年Enomoto等还得到d> (|G|-1)/3，则G能被2个圈覆盖）。Saito在1999年（Degree sums and graphs that are not covered by two cycles. J. Graph Theory 32 (1999),1, 51-61）稍改进而有例外图：“s₃≥|G|-1，则G能被2个圈覆盖或明或2类例外图”。因此2010年（见Chiba, Tsugaki, A degree sum condition for graphs to be covered by two cycles. Discrete Math. 310 (2010),13-14, 1864--1874.）提出推广的猜想：“s_2n+1>(2n+1) (|G|-1)/3，则G能被2个圈覆盖”和猜想“s_2n+1≥(2n+1) (|G|-1)/3，则G能被2个圈覆盖或2类例外图”，他们并证明猜想的n=2时的情况。

再就是：Ronald Gould教授的博士Colton Magnant的还没有出版的论文“Partitioning graphs into paths or cycles of prescribed lengths”结合Enomoto和Ota在2000年（Partitions of a graph into paths with prescribed endvertices and lengths. J. Graph Theory 34 (2000), no. 2, 163--169.）的猜想“n=a₁+a₂+…+a_t, s₂≥n+t-1,则对任意t 个点x₁,x₂,…,x_t，都有G都可划分为某t 条不交路P₁,P₂,…,P_t，使x_i是P_i的一端点并|P_i|= a_i”，和2000年Egawa等六人（Vertex-disjoint cycles containing specified edges. Graphs Combin. 16 (2000), no. 1, 81--92.）的结果“s₂≥n+2t-2,则对任意2t 个点x₁,x₂,…,x_t，y₁,y₂,…,y_t，都有G都可划分为某t 条不交路P₁,P₂,…,P_t，使x_i和y_i是P_i的2端点”。 Colton Magnant只把后者的界加1就提出猜想“n=a₁+a₂+…+a_t, s₂≥n+2t-1, 则对任意2t 个点x₁,x₂,…,x_t，y₁,y₂,…,y_t，都有G都可划分为某t 条不交路P₁,P₂,…,P_t，使x_i和y_i是P_i的2端点并|P_i|= a_i”。还有一个G划分为t 个不交路圈的猜想（允许划分出的子图点数少于3的话，它们就是K₁和K₂；还有是划分的圈C_i或路P_i可以与x_i和y_i，这时界应比Ore条件弱，大概是s₂≥n-t+1），等等。

小结和剖析：优先选择上面Faudree校长的几个一般及无爪H图问题和猜想做为项目的主攻课题，是因我以前对Faudree校长的无爪图猜想做得比较深刻，积累很多经验和方法，特别是二十多年来我一直都做Faudree校长的问题和课题而产生了非常大的兴趣，促使我产生极大的热忱和动力，这是比其它一切都更重要的。

(这里最后部分附Cayley图、双环网络以及超立方体等领域在计算机网络等的一些应用工作)

课题三：图同态（Homomorphism of graphs）.

琼州大学做为海南省至今唯一的欧洲数学会《数学文摘》的评论员单位，这《数学文摘》就曾邀请我评论被当做数学诺贝尔奖的Fields奖获得者Michael Freedman、国际数学联盟主席László Lovász和Alexander Schrijver大师最近合作发表在2007年美国数学会杂志-JAMS的论文“Reflection positivity, rank connectivity, and homomorphism of graph”（这篇论文和评论见这里。发表他们论文的这JAMS杂志也很不错如这见2007年中国大陆学者才首次独立在JAMS上发表论文）。也因在国内还没有见对与他们这篇论文相关的图同态领域的介绍，在这里的网页我就顺利对图同态做一些介绍。

在国际数学联盟主席László Lovász教授的网（http://www.cs.elte.hu/~lovasz/publications.html ）上不难看到Lovász教授近几年的论文中图同态（graph homomorphisms）的占几乎一半。关于图同态近来受到国际数学界的广泛重视，可参考下面去年的国际数学家大会情况：

在2010年印度国际数学家大会做45分钟报告的三个组合学家是：捷克Charles大学的Jaroslav Nesetril教授（德国科学院通讯院士，在中大等台湾多个院所做过报告，去年曾来浙江师大做报告，报告题目是Sparse combinatorial structure: classification and applications），牛津大学Oliver Riordan教授（题目是Percolation on sequences of graphs），加州大学洛杉矶分校Benny Sudakov教授（题目是Recent development in extremeal combinatorics: Ramsey and Turán type problems）。前者的首个博士是乔治亚理工学院Robin Thomas教授，后两者分别在1998、1999年获得Béla Bollobás和Noga Alon的博士。他们近几年都主要搞随机图，主要用概率和代数的同态（homomorphism）方法处理随机模型现象（随机图），已广泛应用在统计物理等

在会前的组合学卫星会议做一小時报告的有三个数学家是：国际数学联盟主席László Lovász教授（题目是Extremal graph theory and graph limits），上面的Jaroslav Nesetril教授（Dualities for graphs and beyond），伦敦大学Peter Cameron教授（From synchronization to graph homomorphism）。这三人都是前辈大师，他们近年主要用概率和同态方法处理随机模型现象

在2010年国际数学家大会做1小时报告的两个数学家：加大伯克莱分校Nicolai Reshetikhin和以色列WIS的Irit Dinur，前者最近发表好几篇随机图论文，后者的论文主要是随机图的，也发表图同态和群同态的论文。

因国际数学家大会一小时报告20个，安排给组合学的45分钟报告7个，却有如此多涉及“图同态”的报告。这虽与主席有点关系，但主要还是图同态课题已广受重视！

在国际数学联盟主席László Lovász教授的网上也有一篇列举图同态的有待解决的问题的文章（Graph homomorphisms: Open problems），可惜的是国内几乎还没有人做出多少图同态的工作

最近,涉及国际数学联盟主席L. Lovász等的工作并有几篇论文在世界四大超一流数学杂志J. AMS、Ann. Math.、Acta Math.、Invent. Math.发表的年轻代表人是Asaf Nachmias，其导师Yuval Peres和许多师兄弟也在四大超一流数学杂志发表论文。姜铁峰教授的导师Amir Dembo和部分师兄弟也在四大超一流数学杂志发表论文，总之,在这些杂志网输入相关词搜索就可找到双环网络和分布环网络等相关论文.

课题四：圈划分问题：

1963年Corradi和Hajnal得到：若图G的点顶数n³3k并且最小度d(G) ³2k，则G包含k个相互独立的圈（同年Dirac和历史上十大数学天才之一的Erdős在同一杂志的论文先研究图G包含2个相互独立的圈的情况,其后研究包含k个相互独立的圈,最后研究平面图包含2个相互独立的圈的情况，“诺贝尔奖”获得者Szemerédi-塞迈雷迪等也为圈划分问题贡献良多）

1996年时在美国新奥尔良大学的现美国爱达荷大学Wang Hong-汪泓教授研究二分图,得到：设G=(V₁,V₂;E)是一个二分图，使得|V₁|=| V₂|=n³2k+1，如果d(G) ³k+1，则G包含k个相互独立的圈。

日本图论权威Hikoe Enomoto教授2001年就提出2个问题（见Enomoto, Hikoe. Graph partition problems into cycles and paths. Graph theory (Prague, 1998). Discrete Math. 233 (2001), no. 1-3, 93--101）：

问题1：能不能用d_1,1或者s_1,1代替上面Wang Hong的结果中的d(G)？（其中d_1,1=min{d(x)+d(y)| xÎV₁, yÎV₂}; s_1,1=min{d(x)+d(y)| xÎV₁, yÎV₂ ,xyÏE(G)}）

问题2：在Wang Hong的结果中，如果不假定|V₁|=| V₂|，结论是否成立？

在剑桥大学获得哈密顿图博士的Jacques Verstraëte于2003年猜想：若图G的点顶数n³4k并且最小度d(G) ³2k，则G包含k个同样长度的相互独立的圈（此猜想是关于Thomassen的猜想对图阶的明确化即n³4k，而且很大胆，是所谓艺高胆大-确实这课题他是弄得最熟悉之一--还是因自信而过于盲目。不论如此，这个阶界如此低确实超乎想象这肯定更难也确实还没有好的进展。Thomassen的猜想（k>2情形）和Häggkvist的猜想（k=2情形）是：充分大的图的最小度d(G) ³2k，则G含k个同样长度的相互独立的圈。其实，Yoshimi.Egawa在1996年已算证明这猜想即弄清楚了n³17k+o_k(1)，Verstraëte的这论文是用更简单的方法证明稍弱结果。Verstraëte现是美国加州大学圣地亚哥分校数学系副教授， 该数学系有数学诺贝尔奖获得者-我读研究生3年几乎每天都在里面的组合代数中心的主任Efim Zelmanov）

和琼州大学合作在国外SCI杂志发表论文的山东大学颜谨教授在《中国科学》2009年第4期已得到关于上面Enomoto问题的部分结果：

设k，n₁和n₂是3个正整数，G=(V₁,V₂;E)是一个二分图，使得|V₁|= n₁，| V₂|= n₂，其中n₁³2k+1和n₂³2k+1，| n₁−n₂|£1，则G包含k个相互独立的圈。

课题五-1：图论的匹配理论在博弈论领域的应用催生15个诺贝尔经济学奖获得者以及其它应用领域的诸多世界大师。

课题五-2：菱形等与完美匹配数、生成树数。

在这相关课题，被称为现代计算机科学鼻祖的计算机诺贝尔奖获得者Donald Knuth院士独立完成的论文[21]（Aztec diamonds, checkerboard graphs, and spanning trees. J. Algebraic Combin. 6 (1997) , 253-257 ；即“Aztec菱形, 棋盘格图，和生成树”），他的这论文解决这类图的生成树问题。这类图是这样定义的：mn个点集={(x,y)| 1≤x≤m,1≤y≤n}的图的边定义为若|x−x’|=1,|y−y’|=1则(x,y)和(x’,y’)相邻。记其中的子图EC_m,n的点集为{(x,y) | x+y是偶数}, 子图OC_m,n的点集为{(x,y) | x+y 是奇数}，则子图EC_m,n的点和OC_m,n的点都不相邻而且它们刚好把这图划分。显然，EC_m,n和OC_m,n的点数分别为「mn/2ù和ëmn/2û。当mn是偶数时，EC_m,n和OC_m,n同构。关于这类图，1982年国际奥林匹克数学竟赛中美国队唯一获得金牌并26岁就成为哈佛大学正教授的Noam Elkies为第一作者的1992年的论文（James Alternating-sign matrices and domino tilings. I. J. Algebraic Combin. 1 (1992), no. 2, 111–132）称OC_2n+1,2n+1为n阶Aztec菱形并证明OC_2n+1,2n+1刚好有2^n(n+1)/2个完美匹配。我的导师柳柏濂教授八十年代曾去跟其做访问学者的Richard A. Brualdi教授在2005年也给出它一个新证明（见 Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers. J. Combin. Theory Ser. B 94 (2005),2, 334--351）。其后，Donald Knuth院士在他的上面论文中证明另一个结果“EC_2n+1,2n+1的生成树数是OC_2n+1,2n+1的4倍”。

Donald Knuth教授是如此处理的：记二分图G的二部分点数为(p,q)、二分图H的二部点数为(r,s)，其weak direct积 G´H定义为点(u,v)和点(u’,v’)相邻当且仅当u和u’相邻、v和v’相邻。记子图E(G, H)的点集:{(u,v)| u∈V(G)和v∈V(H)是分别属于相对应的部分的点}, O(G,H)的点集:{(u,v)| u∈V(G)和v∈V(H)是属于相反的部分的点}，由定义知子图E(G,H)的点和子图O(G,H)的点都不相邻，且|V(E(G,H))|=pr+qs, |V(O(G,H))|=ps+qr。也有EC_m,n=E(P_m,P_n)和OC_m,n=O(P_m,P_n)，其中P_m和P_n分别是点数为m和n的路。Knuth先证明(i):特征多项式P(E(G,H); x)和P(O(G,H); x)满足P(E(G,H); x)P(O(G,H); x)= ∏_j=1^p+q∏_k=1^r+s(x-m_jl_k)，P(E(G,H);x)=x^(p-q)(r-s)P(O(G,H); x)；也证明(ii): P(EC_m,n; x)和P(OC_m,n; x)满足P(EC_m,n; x)P(OC_m,n; x)=∏_j=1^m∏_k=1ⁿ[x-4cosjp/(m+1)cos kp/(n+1)]；和证明(iii): P(EC_m,n; x)=x^mn^{mod 2}P(OC_m,n; x)；并证明(v): EC_m,n的生成树数是P(OC_m-2,n-2; 4) ，OC_m,n的生成树数是P(EC_m-2,n-2; 4)。如此由(iii)和(v),得证“EC_2n+1,2n+1的生成树是OC_2n+1,2n+1的4倍”。

问题[6]：当EC_m,n=E(P_m,P_n)和OC_m,n=O(P_m,P_n)中P_m和P_n换为树、偶圈、路之一时，情况又如何？能否求生成树数？能否求完美匹配数？是多少？或之间的关系如何？显然，也是很有兴趣的问题。

课题六：图的嵌入（Graphs embeddable）

若图画在平面上满足：1、任何一条表示边的曲线段除端点外不通过任何其它的代表节点的点；2、任何二条边表示边的曲线段除端点可能公共外不再有任何公共点，在数学上称这样的平面表示为图的平面嵌入。一个图G有平面嵌入，也称G是平面的。如果一个平面嵌入还满足条件3、所有表示边的曲线段全是由水平或铅垂线段组成的折线段，则称它为纵横嵌入。一个图G，若将它的一些边用引进一些次为的2节点而得的路所代替，记所得的图为G¢，则G和G¢称为同胚的。记住判定图的可平面的一个简明结果：定理(Kuratowski):一个图G=(V, E)是平的当且仅当G没有一个子图与K₅或K_3,3同胚。

若将集成电路中的继电器作为节点，继电器之间需要有导线连接表示它们相应的节点相邻，这样就得到一个图。这样设计一个电路就相当于找这个图的一个纵横嵌入。更完全地说，首先应判断这个图是否纵横的。如果是，才有求它的问题。如果不是，则要看是否可通过扩点之后而得到一个纵横的图。事实上，这有一个可以利用上面定理证明的判断定理：一个图可以通过扩点而得到一个纵横的图而且仅当这个图是平面的。在集成电路设计中，常称纵横嵌入中边上的折为孔道。每条无折的纵横嵌入也称为网格嵌入。判定一个图是否有网格嵌入可转化为考察一个图是否有完美集对。在集成电路设计中，要先解决极大极小设计、最少孔道设计及最小面积设计，为了实现这些设计就遇到二个方面的关键问题：首先是如果将继电器安置在一块板上使得又此可以实现所要求的已经证明存在设计。数学上，就是将一个图的节点安置在什么位置使得可以实现已经证明存在的纵横嵌入。这就是所谓的定位问题。而所谓布线问题就是在节点位置给定之后研究能否或如何求得一个给定图的满足要求的嵌入。因确向树几乎贯穿于整个图的嵌入：对于图G上的一个树，或说对于G的一个支撑树T，如果存在对G的边的定向使得任一基本圈上的边均有相同的走向或者说为有向圈或回路，则称T为一个准确向树。如果一个节点在准确向树上没有进入边，则称它为T的源。一个准确向树可以有两个以上的的源。若只有一个源，则称它为确向树。下面是图的嵌入的一些基本理论和结果：

下面是与哈密顿图相关的主要结果，它们贯穿于“图的可嵌入性”的前300页-其贯穿占了全书正文412页的约2/3，可见涉及哈密顿图的工作之广泛：一个图G的平面嵌入数记为n_pe(G)，与它的平面性辅助图Aux_iG(i=0, 1, 2)有关。即有定理：设c(Aux₂G)为Aux₂G中连通片的数目，则对于任何哈密顿图只要T落在一个哈密顿圈上就有n_pe(G)=2^c^(Aux1G)^-¹。

如果一个平面图有一个r-扩张，则称它为r-可扩张，定理：任何3-正则的哈密顿平面图是3-可扩张的。

对于一个曲线Z的交叉序列的劈分图G^~(Seq)，劈分曲线Z^~常是相应G^~(Seq)的一个哈密顿圈。

定理：对于3-正则图G，其上有一个确向树Tod为路（在哈密顿圈上），有事实：每一个上树边gÎTod*在Aux₀G中伴随至多有两个变量，其一为树变量，另一为上树变量。

定理：一个确向树Tod在哈密顿圈上的3-正则图G是可平面的当且仅当Seq(G)不含禁用子序列。

定理：任何一个3-正则可平面图G若有一个确向树Tod在哈密顿圈上，则必有这样一个平面嵌入使得所有А₀中的边皆在Tod上右（或左）侧而所有А₁中的边皆在Tod的左（或右）侧。

定理：一个确向树Tod在哈密顿圈上的G=(V, E)是可平面的当且仅当所确定的G^~=(V^~, E^~)是可平面的。

定理：一个确向树Tod在哈密顿圈上的G=(V, E)有e(Aux₁G)£12v(G)-36.

平面的当且仅当所确定的G^~=(V^~, E^~)是可平面的。

定理：对于图G=(V, E)，确向树Tod在哈密顿圈上，有|S(G; Tod)|与Tod的选择无关和|S(G; Tod)|就是G的不同平面嵌入的数目。

定理：对于图G=(V, E)有一个确向树Tod在哈密顿圈上，它的不同平面嵌入的数目为n_pe(G)=2^c^(Aux1G)^-¹。

定理：若一个3-正则图G有Tod为它的一个确向树且在哈密顿圈上，则G的任何一个平面嵌入全是3-可扩张的。

定理：任何一个图，若它是某哈密顿平面图的子图，则它必为2-页可嵌入的。

定理：一个不可分离的图G的页数为2，当且仅当G是某哈密顿平面图的子图并且有一个图与K₄同胚。

…

因若将集成电路的印刷线路板的表面视为与球面等价，则将它打P个洞就成了一个亏格为P的可定向曲面。这样，我们总可以将非平面的图嵌入到某亏格的曲面上。因此，这里附说很重要也极难处理的图的亏格：给定图G和曲面S（指一个连通紧致2-维闭流形，其亏格记为g(S)的），G到S的一个2胞腔嵌入是指一个同胚映射Φ：G→S使得S\Φ(G)的每个连通分支同胚一个开圆盘，此时S\Φ(G)的每个连通分支称为G在S的一个面（关于嵌入Φ）。图G的最大可定向亏格（简称最大亏格）记为g_M(G)，是指那些G可嵌入的可定向曲面亏格最大者，即指最大的整数g使得G能2胞腔嵌入亏格为g的定向曲面上S_g，又Euler公式易得：E(G) -V(G)+ F(G)=2-2 g(S)（若S可定向）或2- g(S)（若S不可定向），于是，图G的最大亏格自然有如下的上界：g_M(G)£ëb(G)/2û，其中b(G)= E(G) -V(G)+1=意为图的不在任一支撑树上的边的数目，称为G的Betti数。若上式中等号成立，则称G是上可嵌入的。

设T为图G的一颗生成树，x(G, T)表示G\E(T)中边数为奇数的连通分支个数，x(G,)=min_Tx(G, T)为图G的Betti亏数

确定图的亏格问题是拓扑图论的基本问题，且已被Thomassen证明亏格问题是NP难的。目前已知结果主要是关于特定的对称性比较好的图类，德国专家Gerhard Ringel已分别在1955年、1968年和1965年对n-方体、完全图、完全二部图等亏格公式得出结果，Frank Harary等人也独立得到部分结果。Endre Szemerédi大师的博士Sarmad Abbasi于2000年研究星图的亏格等。可参考一些专题基本网站：如亏格和图嵌入（关于这学科某些进展见华东师范大学博士导师任韩教授说刘彦佩教授正用代数拓扑的“同调论”等的方法来研究图在曲面…。关于“同调论”和胞腔，我这里的网有拓扑学的“同调论”的胞腔等的相关概念和一些基本理论

总而言之，正如美国工程院院士葛守仁教授说“在集成电路的布局中，通常用图表示电路，将布图归结为在一些特定条件下图的嵌入”，但要从图的嵌入过度到实际的集成电路“布图设计”当然需要补充很多集成电路布图设计方面的知识和经验，而且随着集成电路布图设计的发展，任何人也得跟着发展。因很容易找到很多好著作和论文来参考，也因篇幅所限，这里就不能做更多介绍。因此，如果我们项目获得资助，我们将象上面开创圈结构图理论一样，必定全力以赴，也将开拓出这领域崭新的系统性工作。陈建二教授所攻读的是拓扑图论的博士学位,其导师之一Gross的拓扑图论专著是这方面世界最权威的著作，可参考，若陈建二也从他导师的此方向必定比别人更自信而在此方面有建树，可联系）

课题七-1：校园信息系统（Campus information systems）:

Campus information systems is a interrelated group of information sources, accessible by computer through campus institutional external and internal web environment, that a institution place at the disposal of its users to enable them result it and /or provide a selection of significant relevant data. In the wide context of their institution life in its academic, administrative and social senses, in order to imptove students knowledge base. It intends to provide the users with various selected sets of data that deai with the institution. In some case, the system can enable with other people in institution in order to enhance various information or knowledging sharing.

结果1. Suppose {H₁, H₂, …,H_m} is a H-decomposition of graph G with at least m or n is odd. Then G is H-V- super-strong magic decomposable with magic constant k=(mn+1)+(n+1)(n(m+3)+(m-1))/2.

结果2. If a non-trivial H-decomposable graph G≅K_m,n is a H-V- super-strong magic decomposable graph with at least m or n is odd and if the sum of edge labels of a decomposition graph H_j is denoted by åf(E(H_j)) then {åf(E(H₁)), åf(E(H₂)), ¼,åf(E(H_m))}={a, a+d, ¼,(m-1)d} with a=[m(n+1)²+(2n-1)(n+1)]/2 and d=-1.

结果3. If a non-trivial H-decomposable graph G≅K_m,n is a H-V- super-strong magic decomposable graph with at least m or n is odd and if the sum of vertex labels of a decomposition graph H_j is denoted by åf(V(H_j)) then {åf(V(H₁)), åf(V(H₂)), ¼,åf(V(H_m))}={a, a+d, ¼,(m-1)d} with a=mn+1+n(n+1)/2 and d=1.

结果4. Let G≅K_m,n be a non-trivial H-decomposable graph with at least m or n is odd and if V(G)=U(G)ÈW(G) with |U(G)|=m and |W(G)|=n, Let g is a bijection from V(G) onto { 1, 2, ¼, p} with g(U(G))= { 1, 2, ¼, m} and g(W(G))= { m+1, m+2, ¼, m+n=q} then g can be extended to a H-V- super-strong magic labeling if and only if {åf(V(H₁)), åf(V(H₂)), ¼,åf(V(H_m))}={a, a+d, ¼,(m-1)d} with a=mn+1+n(n+1)/2 and d=1.

结果5. Suppose {H₁, H₂, …,H_m} is a H-decomposition of graph G≅K_m,n with both m and n are even. Then G is not a H-V- super-strong magic decomposable graph.

课题七-2：模糊图。

我为欧洲数学会的《数学文摘》评论员，最近它邀请我评论Mathew和Sunitha的模糊图论文“Node connectivity and arc connectivity of a fuzzy graph”。我就请国际不确定性数学学会主席、模糊图主要开拓者之一John Mordeson教授寄来他的一些相关资料（他是《模糊图和超图》一书的作者。我本来请他从邮箱里发给我就行，结果他从邮电局寄来给我，且寄来此外的更多资料。就使我们感到不认真做很过意不去，也因模糊图学科的基本概念理论的论文也就几百篇，更为了欧洲“数学文摘”的评论工作，我就围绕着他寄来的论文从网上再下载了其它近2百篇这模糊数学和模糊图的论文来全读或选为研读，也把模糊图理论知识在我的这网www.qzu5.com/articles.htm 的第10节中介绍出来），这学科论文大多都发表在与图论相关的核心杂志，如：

1、John Mordeson, Prem. Nair, Cycles and cocycles of fuzzy graphs. Inform. Sci. 90 (1996), no. 1-4, 39--49.

2、John Mordeson, Chang-Shyh Peng, Operations on fuzzy graphs. Inform. Sci. 79 (1994), no. 3-4, 159--170

3、John Mordeson, Fuzzy line graphs, Pattern Recognition Letters, 14(1993), 5,381-384.

4、Oriolo et al., On the recognition of fuzzy circular interval graphs. Discrete Math. Vol.312, no. 8, 1426-1435.

5、F.Eisenbrand, M.Niemeier, Coloring fuzzy circular interval graphs. Eur. J. Combin. Vol.33, no. 5, 893-904

6、Muhammad Akram, Bipolar fuzzy graphs. Information Sciences Vol.181, no.24, 5548-5564.

现在，（见本人的上面网的第10节），还因从上面几行也可窥见模糊图的工作越来越得到更多图论组合重要杂志发表。确实这方面尚有很大发展空间，如虽然已把图论的很不少概念推广到模糊图，也据自身特性建立一些自已的概念，但也确实有很多图的概念还没有推广到近几年创立的区间值模糊图、直觉模糊图、Vague图、双向模糊图、二型模糊集图等，以及结合粗糙集的区间值模糊粗糙图、直觉模糊粗糙图、区间值直觉模糊粗糙图，双向模糊粗糙图，还有结合Vague集的Vague粗糙图、拓扑粗糙Vague图、粗糙区间值Vague图等，得推广更少，而且它们本身的概念和理论空白更多。特别是上面结合粗糙集或结合Vague集的某些概念也仅是本申请人非正式提出的，如此这几类图本身还需要很多更精准和有用的概念和定义。而面对如此多类模糊图，我们的优先工作不应偏于一隅，应以大统一的视角，以权威杂志的模糊图论文为导向，建立基础的一般化的能被更多类模糊图纳入的概念理论，以便建立各领域一般化系统性理论。

其实，模糊图对图论工作者本来应不会太陌生，它就是类似图论中的带权图。只是模糊的思想是考察元素（包含点和边）的隶属度（就权的大小），从而根据点、边的相对隶属度，可做出点、边所属于类的划分，它们的点边连通度、圈、哈密顿圈、匹配、生成树等都是由此确定。它们的研究方法大多也和图论的方法差不多。因此在弄通内在本质的基础上可据此定义和研究若干类与上面本课题的概念和理论密切的各类模糊图，其后以点带面建立更系统化的概念和理论。当然，选择模糊图仅做为本项目次之的课题，因尚没有在这方面取得重要工作，就具有不确定性，但因其处理方法大多和图论差不多如此可借鉴图论的

课题八：图的群连通性（Group connectivity of graphs）

美国美国西弗吉尼亚大学赖虹建教授和李相文教授等最近在《数学学报》(英文版)[L-22]出版了群连通性和群着色的一个很好的综述文章，很值得好好看。最近赖虹建教授等也在《离散数学》2010年第5期也证明“G是2-边连通的，A是阶至少为4的阿贝尔群，如果不相邻的任两点 u,v均有max{d(u),d(v)}≥n/4，则 G是 A-连通的或G是某些例外情况”。此外，获得美国伊利诺伊大学香槟分校博士学位、现在任教美国历史上第二悠久大学（在文理并重的美国大学排名中也多次居美国第一大学）的硕士生阶段和我同师柳柏濂教授的喻革新教授等在2008年合作得到 “G是简单图，A是阶至少为3的阿贝尔群，如果不相邻的任两点 u,v均有d(u)+d(v)≥n，则 G是 A-连通的或G是12类图”（见European J. Combin., 29, (2008),7, 1587-1595。刚见喻革新当上副教授，在这样著名的大学任副教授是很不容易的（如该系副主任早在1963年已博士毕业于也是伊利诺伊大学香槟分校，但仍是副教授）。关于我师弟喻革新获得博士学位的美国伊利诺伊大学香槟分校是世界名校，该数学系Douglas West教授是《离散数学》杂志主编，他的网站内容非常丰富，为博士生也为研究人员提供的“REGS”最新介绍的几十个课题中一个是由计算机诺贝尔奖得主姚期智发展的）。总之，这是最近极为充满活力的领域，其中中国学者是推动其向前发展的一股重要力量。但因篇幅所限，这里就不能做更多介绍，在美国西弗大研究生院院长赖教授那里有最全面的信息

课题九：Hamiltonian染色问题，以及赖虹建教授等开创的图的动态着色与条件着色(我们琼州大学林越教授取得一些结果)

这课题是美国WMU数学与计算机系两个权威-前辈大师Gary Chartrand和近十年来在该系培养博士生最多的张平教授以及欧洲布拉格大学资深教授Ladislav Nebeský这3个专家一起提出的。很多基础性问题仍还没有得到解决。因国内接触过它的人可能很少（直到现在才见何文杰教授刚发表一篇论文就补充在下面--至今国内可能仅有这一篇吧），也因这美国大学和我们琼州大学合作多篇论文，如此就在此先简述一些基本概念：对n阶连通图G的两点 u 和 v ，D(u, v)表示u-v path的最长路的长度。图G的一个hamiltonian染色c是对全部顶点的色分派（用正整数表示）并使任意两点u 和 v都满足 D(u, v) + |c(u) –c(v)|≥n –1。hc(c)表示图G的hamiltonian染色 c 的最大染色数。图G的 Hamiltonian染色数hc(G)是全部Hamiltonian染色c中的min{hc(c)}。它的最显著的意义在于：图G是哈密顿连通的当且仅当hc(G)=1。

2002年Chartrand、Nebeský和张平教授刻划 (n − 2)² – 3≤ hc(G) ≤ (n –2)² –1的n (≥6)阶连通图G，得到

1、hc(G)= (n−2)² + 1ÛG=S_n.

2、如果G¹S_n，hc(G) ≤ (n−2)²–1。

3、hc(G)= (n–2)²–1ÛG=S¢_n.

4、如果G¹S_n和G¹S¢_n，hc(G) ≤ (n–2)²–3。

5、hc(G)= (n–2)²–3ÛG=S²_n.

2005年Chartrand、Nebeský和张平教授得到下面结果：

hc(K_n) = 1；当n ≥2时有hc(K_1,n−1) = (n−2)²+1 ；当r≥2时有hc(K_r,r) =r ；hc(C_n) =n–2。 (1)如果G是n (³3)阶哈密顿图，则hc(G) ≤ n−2。特别地，对任意整数k ≥1 和n ≥ 3 (1 ≤k ≤ n−2)，存在一个哈密顿图G使hc(G)=k 。(2)如果n (³ 4)阶连通图G的最长圈的长cir(G)=n−1，则hc(G) ≤n–1。(3) 对n (³ 2)阶连通图G均有 hc(G) ≤ (n−2)²+ 1（见Hamiltonian colorings of graphs. Discrete Appl. Math. 146 (2005), no. 3, 257--272.）。

2006年Nebeský教授得到下面结果：

n (³ 3)阶连通图G，如果存在它的子图F 是满足2 £ i £(n+1)/2的i阶哈密顿连通图，则有 hc(G) £(n−2)²+1−2(i−1)(i−2)（见The Hamiltonian chromatic number of a connected graph without large Hamiltonian-connected subgraphs. Czechoslovak Math. J. 56(131) (2006), no. 2, 317--338.）

2005年Chartrand、Nebeský和张平教授得到的其中主要结果是：

n (³ 4)阶连通图G ，如果2≤hc(G) ≤ n−1，则hc(G)+cir(G)³n+2（见On Hamiltonian colorings of graphs. Discrete Math. 290 (2005), no. 2-3, 133--143.）。

2003年Nebesky教授研究最长圈与hc(G)的关系。得到n (³ 7)阶连通图G的最长圈的长cir(G)=n−2,则hc(G) ≤ 3n−ë(n−2)/3û−6.（见Hamiltonian colorings of graphs with long cycles. Math. Bohem. 128 (2003), no. 3, 263--275.）。

2008年何文杰教授等讨论max{D(u,v)|u,vÎV(G),u¹v}£n/2的图的hc(G)。特别研究caterpillars和double stars（On Hamiltonian colorings for some graphs. Discrete Appl. Math. 156 (2008), no. 15, 3028--3034..）

课题十：度型条件、A-K条件、邻域并条件对Set-泛圈图、k-path哈密顿图、k-path可迹图等。

关于Set-泛圈图，《离散数学》执行编委Wayne Goddard和Hendry的分别解决最小度d(G)≥(n+1)/2、度和d(x)+d(y)≥(3n-3)/2的情况。本课题计划去探索最小度d(G)≥n/2、度和d(x)+d(y)≥n的非Set-泛圈图有哪些？也研究在1990年Asratian和Khachatrian局部新条件基础上的更进一步条件的泛圈性

关于k-path哈密顿图、k-path可迹图，我们也计划去彻底完成在Kronk教授在Proc. Amer. Math. Soc和J. Combin. Theory B上的最小度和“度和”基础上的k-path哈密顿图、k-path可迹图的完整理论框架（包含邻域并和距离是2的“范型”等情况）。此外，似乎还没有定义“k-path哈密顿连通图”，也没有一篇这方向的任何结果。如此

我们即定义k-path哈密顿连通图：对任意满足|P|≤n-2的一条路P，若对任何x,y∈V(G-P)均有以为x,y两端点的一哈密顿路含路P，则称G是“k-path哈密顿连通图”。

研究[1]: 若2-连通图n阶G不相邻的任意两点x,y均有d(x)+d(y)≥n+k+1，则G是k-path哈密顿连通的

研究[2]: 若2-连通图n阶G的距离为2的任意两点x,y均有2|N(x)∪N(y)|≥n-δ+k+1，则G是k-path哈密顿连通图或例外图（因我们上面定理的k-path哈密顿图已有例外图，则哈密顿连通图也有）

研究[3]: 若2-连通n阶图G的距离为2的任意两点x,y均有|N(x)∪N(y)|≥(n-1)/2+k+1，则G是k-path可迹的（k=0时，它是Bauer和范更华教授等的1991年的论文[4]中再提及的一个猜想。我也已给出这猜想的简单证明，见网www.qzu5.com/l.htm ）

研究[4]: 若2-连通图n阶G的距离为2的任意两点x,y均有2|N(x)∪N(y)|+d(x)+d(y)≥2n-1+k，则G是k-哈密顿图或例外图（距离为2时应该有例外图）

还可进一步研究Asratian和Khachatrian的上面局部度和条件：

研究[5]: 若2-连通图n阶G的任意路xwy的不相邻点x,y 均有d(x)+d(y)≥ |N(x)∪N(y)∪N(w)|+k, 则G是k-path哈密顿图吗？若2-连通图n阶G的任意路xwy的不相邻点x,y 均有d(x)+d(y)≥ |N(x)∪N(y)∪N(w)|+k+1, 则G是k-path哈密顿连通图吗？

1999年才获得博士并已在普林斯顿大学指导出5个博士，特别是在2010年的印度国际数学家大会做45分钟报告的Benny Sudakov，最近和他的博士在刚出版的论文[10]（即Choongbum Lee , Benny Sudakov, Hamiltonicity, independence number, and pancyclicity, European J. Combin. 33 (2012), no. 4, 449–457）得到下面结果：

定理(2012,)：若存在某常数c使得对任何正整数k，每个阶n≥ck^7/3和独立数α(G)≤k的哈密顿图都是泛圈图。

它们在这论文中说数学大师Erdos、法国巴黎第11大学Flandrin和李皓教授等分别在下面2篇论文证明“阶n≥k⁴和独立数α(G)≤k的图是的泛圈图”，其中，后者的界更弱些。

P. Erdos, Some problems in graph theory, Hypergraph Seminar, Lecture Notes in Math., Springer , 411(1974) , 187--190,

E. Flandrin, H. Li, A.Marczyk, M. Woźniak, Mariusz. A note on pancyclism of highly connected graphs. Discrete Math. 286 (2004), no. 1-2, 57—60。

问题[6]：Sudakov等在上面2012年的论文中也举例说明如果阶还能改进，那最好的阶至多是Ω(k²)。因此，若还能对指数改进1甚至1/2，都是一个非常大的突破和进展。如此，在目前看来，似乎离最好可能还非常远。

Sudakov的另一纪录是他的2010年才获得者博士的Jacob Fox已是《图论杂志》3个执行编委之一！毕业一年就任权威专业杂志编委，可能史无前例？如此，他的成果若是次品是不会发表、是不能如此受重视的。

关于包含邻域并和距离是2的“范型”和Asratian和Khachatrian的上面局部度和条件等情况，因还没有定义“k-path哈密顿连通图”，没有一篇这方向的任何结果。如此，我们定义k-path哈密顿连通图：对任意满足|P|≤n−2的一条路P，若对任何x,yÎV(G−P)均有以为x,y两端点的一哈密顿路含路P，则称G是“k-path哈密顿连通图”。并将先研究核心的问题：

因关于这一课题的Set-泛圈图和k-path哈密顿图，我们都已取得最小度及度和条件下的对前人所有工作的改进，也开拓它们的邻域并条件的领域。因此，它们仅是补充课题

课题十一：超欧拉图(Supereulerian graphs)

超欧拉图(Supereulerian graphs)的当今世界权威中心应属美国西弗吉尼亚大学赖虹建教授那里。赖虹建教授的工作应是传承于他导师，并做出许多创新和发展。赖教授曾多次回国内介绍这领域的进展。赖教授和美国丰迪拉克市威斯康星大学分校梁艳婷教授等最近合作发表几篇这方面的非常有趣的论文（如梁艳婷教授最近寄来给我的2011年《离散应用数学》出版的论文[L-24]就是证明“对任意的k，相应地阶n大于某个数时的图GÎC₂(6,k)除了可收缩为4个特殊图的图外，G均是超欧拉图”，它推广1999年以来的相关论文的工作。当然，一般情况C_h(l,K)中很多有趣类图的超欧拉图性的刻划仍是值得研究的待解决的问题。此外，超欧拉图的研究中还有其它许多有趣的问题。梁艳婷教授在跟赖虹建教授做博士生前跟我的导师柳柏濂教授读硕士，如此感到她的某些课题与我的可能相近）。众所周知，超欧拉图是图论中最古老又方兴未艾的领域，在图论教材中都会列为很重要的部分来讲解，因此大家都应有很好的基础。这为其后的进展，是很好的铺垫。因篇幅所限，这里不能做更多新进展的介绍。但因赖教授和欧洲数学会发展中国家委员会主席Fleischner是这领域最正宗的世界权威，在他们那里特别是赖教授那里可获得足够多的材料。

课题十二-1：无爪图(K_1,3–free)等禁止子图问题：

美国十大老牌名校-Emory大学的学术委员会主席Ronlad Gould教授在2009年的美国工业与应用数学学会年会（2009 SIAM Annual Meeting）做标题为《Strong Hamiltonian Properties in 4-connected Graphs》的报告（共有三个人在这大会的“图的圈结构”分会议做报告，另2人是Akira Saito（《图与组合》现任执行主编），Douglas B. West（《离散数学》主编）。见会议网址http://meetings.siam.org/sess/dsp_programsess.cfm?SESSIONCODE=8427 ）

Gould教授最近又在2010年美国工业与应用数学学会的离散数学会议（2010 SIAM Conference on Discrete Mathematics）做标题为《Connectivity and Forbidden Families for Hamiltonian Properties》的报告（共有三个人在这大会的“图的圈结构”分会议做报告，另2人是Hal Kierstead，Xingxing Yu，（见会议网页 http://meetings.siam.org/sess/dsp_programsess.cfm?SESSIONCODE=9864 ）

Gould教授也在2010年的“第23届Cumberland Conference on Combinatorics, Graph Theory and Computing”做大会报告（仅四人做大会报告，见会议网址http://www.olemiss.edu/depts/mathematics/cumberland2010/index.htm ）。

这三个报告虽然标题不同，但报告内容几乎相同，也同样提出下面3个“泛圈图”问题。足见“泛圈图”是重要课题之一。

即，他在报告中总结他和前人的2连通有禁止子图的图的泛圈性后，提出第一个问题1：“Question: What changes if we consider 3-connected graphs?”。（即若考虑3连通图，则要做何条件变化才保证G是泛圈图？）。其后，他在总结他和两个专家2004年得到的条件的基础上，提出第二个问题2：“Question: What about 4-connected ?”（注：若只考虑哈密顿图，无爪图就足够了）；最后，他提出第三个问题3：“Question: Can we characterize the 4-connected forbidden pairs that implying a graph is pancyclic ? Are there pairs not involving the claw?” （若G是4连通时，则哪些2对禁止子图条件能保证G是泛圈性？若不涉及“爪”呢？）（见 http://www.mathcs.emory.edu/~rg/orsay10.pdf ）

关于只单单考虑无爪图。

Ryjacek1997年证明“7连通无爪图是哈密顿图”（见On a closure concept in claw-free graphs, J Combin Theory B 70 (1997), 217–224）。

Brandt 1999年考虑哈密顿连通图并证明“9连通无爪图是哈密顿连通图”（见9-connected claw-free graphs are Hamilton-connected, J Combin Theory B 75 (1999), 167–173.）。

胡智全教授、田老师和卫兵教授等在2005年改进到“8连通无爪图是哈密顿连通图”（见Zhiquan Hu, Feng Tian, Bing.Wei, Hamilton connectivity of line graphs and claw-free graphs. J. Graph Theory 50 (2005), no. 2, 130--141 ）。

基于Gould教授近两年在美国几个有影响的传统大会都重点呼吁研究泛圈图性，而目前仍不知道8连通甚至9连通无爪图的泛圈性？因此，本课题也将考虑问题4：8连通或9连通无爪图的泛圈图性。当然，泛连通图等如何也是要完成的课题。

捷克大师Zdeněk Ryjáček等1999年在《离散数学》得到： “3连通无爪图G是Z₄-free的，则G是哈密顿图” （Brousek, Jan; Ryjáček, Zdeněk; Favaron, Odile. Forbidden subgraphs, Hamiltonicity and closure in claw-free graphs. Discrete Math. 196 (1999), no. 1-3, 29-50.）

赖虹建教授2010年和熊黎明教授等在《图论杂志》(见[L-19])推广上面结果到：“3连通无爪图G是Z₈-free的，则G是哈密顿图”（Lai, Hong-Jian; Xiong, Liming; Yan, Huiya; Yan, Jin. Every 3-connected claw-free Z₈-free graph is Hamiltonian. J. Graph Theory 64 (2010), 1, 1-11.）

结合上面Ronlad Gould教授在几个有影响大会对泛圈图的重视，则建立下面这类禁止子图的图的泛圈图理论必是很好的更高层次的课题（哈密顿连通图也值得优先解决）：

问题：“3连通无爪图G是Z₄-free的，则G是泛圈图吗？”

问题：“4连通无爪图G是Z₈-free的，则G是泛圈图吗？”

否则，问题：h是多少时，3连通{K_1,3, Z_h}-free图G是泛圈图？”

课题十二-2：无爪图的泛圈图问题：

1984年Matthews和Sumner猜想“4连通无爪图是哈密顿图”，1986年 Thomassen提出等价的线图猜想，又因1971年Bondy猜测“哈密顿圈的充分条件都蕴含图几乎是泛圈图”。如此泛圈图常常是跟着在哈密顿圈之后要解决的问题。前面第1.3节已说在《离散数学》主编 Douglas West的网站见Ronald Gould教授提出的问题是West于2012年收录的组合数学约30个课题之一。此问题为“确定最大图H使每个4连通 (claw,H)-free图是泛圈图”。确实，从1974年Goodman和Hedetniemi的著名结果：“2连通{claw, paw}-free图是哈密顿图”起，这些年来的进展都较缓慢,大多对最大图H更是模糊，但近年来，特别是他们等的下面几篇论文的进展工作，使这问题已到了要全面解决的时候：

2013年Gould教授和他的4个博士在《离散数学》杂志证明：4连通{K_1,3, B(i,j)}-free图是泛圈图(i+j=6而且都非零)。（Ferrara, Gehrke, Ronald Gould, Magnant, Powell, Pancyclicity of 4-connected {claw, generalized bull}-free graphs. Discrete Math. 313 (2013), 4, 460--467）

2012年Ferrara,Wagner和Morris在《图论杂志》证明：4连通{K_1,3,P₉}-free图是泛圈图（Pancyclicity of 4-Connected, Claw-Free, P₁₀-Free Graphs，J. Graph Theory, 71(2012), 4, 435–447）

2013年赖虹建教授和他的合作者也得到3连通{K_1,3, N(i,j,k)}-free的哈密顿性结果（见Wei Xiong, Hong-Jian Lai, Xiaoling Ma, Keke Wang, M. Zhang, Hamilton cycles in 3-connected claw-free and net-free graphs, Discrete Math., 313(2013), 6, 784-795）；还有2012年Kaiser和Vrana证明“最小度不小于6的5连通无爪图是哈密顿图” (Hamilton cycles in 5-connected line graphs , Euro. J. Combin. 33 (2012), 924-947）。如此对Gould的问题还可研究3连通和5连通的情形。

课题十三：无爪图的2因子和独立集关系问题：

哈密顿圈是圈数为1个的2因子,则若不清楚是否有哈密顿圈，常先突破2因子。

1991年Choudum和Paulraj得到：若无爪图G的最小度d(G)≥4，则G有2因子（见Regular factors in K_1,3-free graphs. J. Graph Theory 15 (1991), 3, 259-265）；1996年Ota和Tokuda得到：若K_1,s-free G的d(G)≥2s−2，则G有2因子（J. Graph Theory 22 (1996), 1, 59-64）

2012年美国孟菲斯大学常务校长、欧拉奖得主Faudree为第一作者的论文[F]（即Ralph Faudree, C. Magnant, K.Ozeki, K.Yoshimoto, Claw-free graphs and 2-factors that separate independent vertices, Journal of Graph Theory, 69 (2012),3, 251–263）中提出下面5个猜想：

猜想1(2012,[F]):若G是最小度d(G)≥5的无爪图，S是任一独立集，则G都有2因子使得每一圈含S的至多一点。

猜想2([F]):若G是最小度d(G)≥n/a≥5的无爪图，则G都有a个圈组成的2因子。

猜想3( [F]):若G是最小度d(G)≥n/a≥5的无爪图，则G有一个最大独立集S和有a个圈组成的2因子，使得每一圈含S的一点。（a是独立数）

猜想4([F]):若G是最小度d(G)≥a+1无爪图，则G都有a个圈组成的2因子。

猜想5([F]):若G是最小度d(G)≥a+1无爪图，对G的任一个最大独立集S，其后存在a个圈组成的2因子，使得每一圈含S的一点。

对于猜想1,最大独立集做到，其它独立集一般都可以，这就要保证2因子足够多，当然只要这关系只要恰好也行。如此，在他们的这篇论文中仅解决d(G)≥7的下面定理：

定理1([F]):若G是最小度d(G)≥7的无爪图，S是任一独立集，则G都有2因子使得每一圈含S的至多一点。

对于猜想3的条件d(G)≥n/a，他们在这篇论文中仅解决d(G)≥2n/a-2的下面定理：

定理2([F]):若G是最小度d(G)≥2n/a-2的无爪图，n≥3a³/2，则G有一个最大独立集S和有a个圈组成的2因子，使得每一圈含S的一点。

最近Kužel, Ozeki和Yoshimoto的论文研究一延伸课题（即2-factors and independent sets on claw-free graphs, Discrete Math., 312 (2012), 2, 202–206），即考虑d(G)≥3的每圈含独立集S的至少一点的情况，而且他们在这篇2012年的论文中只证明下面一个定理：

定理3(2012,[KOY])：若G是最小度d≥3的l-连通无爪图，l∈[2,3]，则对G的任一个最大独立集S和有α个圈组成的2因子，使得每一圈含S的至少l-1点。

推论(2012,[KOY])：3连通无爪图G有一圈数至多a/2≤|V(G)| / (d+1)的2因子。

因已知3连通无爪图有2因子，要趋向哈密顿圈，那就要知道存在圈数少的情况？ Ozeki, Ryjacek和Yoshimoto刚完成的论文得到定理：3连通无爪图有一圈数至多max{2(a+1)/5, 1}的2因子（这论文是K. Ozeki, Z. Ryjacek and K. Yoshimoto，2-factors with bounded number of components in claw-free graphs，在提交本申请书时，他们的这论文尚未确定被录用）。

课题十四：包含线图的更一般的著名图类的s-哈密顿图与(s+2)-连通图的关系；s-哈密顿连通图与(s+5)-连通图的关系，还有兼与(s+2)-边连通图的关系。

显然，所有s-哈密顿图都是(s+2)-连通的，但对一般图及就是不少特殊图类，反过来却不成立。那么就有问题：那些图类反过来也成立呢？

赖虹建教授和邵叶红副教授在即将于2013年出版的《图论杂志》得到s³5时的线图成立，即他们得到：s³5时，线图G是s-哈密顿图当且仅当G是(s+2)-连通的（见Hong-Jian Lai, Yehong Shao, On s-hamiltonian line graphs, 已在 J. Graph Theory网站在线出版）

他们只考虑s³5是因Thomassen的4连通线图是哈密顿图的猜想离解决还远，而s=2时就是4连通线图，则肯定非常困难。s=3时困难也会不少，但s=4时是可以做的。不论如何，除了线图，还应研究s³5时其它更一般的图类，特别是包含线图的更一般的图类（如下面的半无爪图等等）的上面关系，是更广的课题。也还可结合一些著名限制条件（如下面的“边连通”）的一般图或其它特殊图，研究它们的(s+2)-连通的与s-哈密顿图性的关系等，以及下面进一步的s-哈密顿连通性的关系，也是极有趣的课题。

即赖虹建教授、梁艳婷博士和邵叶红博士2008年也已得到连通线图和s-哈密顿连通图的关系：s³2时，①(s+5)-连通图G是s-哈密顿连通图；② (s+3)-连通图G是s-哈密顿连通图的当且仅当G还是(s+2)-边连通图。（Hong-Jian Lai, Yanting Liang, Yehong Shao, On s-Hamiltonian-connected line graphs. Discrete Math. 308 (2008), 18, 4293--4297.）

即可把上面课题三推广到quasi-claw-free graphs（称半无爪图或拟无爪图）等等。它1998年最先由Ainouche[1]引进的（见A.Ainouche, quasi-claw-free graphs, Discrete Math,
179(1998),1-2,13-26），记J(x,y)={uÎN(x)∩N(y): N[u]Í N(x)∪N(y), d(x,y)=2, x,yÎV(G)}，若对图G距离是2的任一对点x和y，均有J(x,y)≠空集，则称G是半无爪图）。而无爪图是其任何导出子图都不同构于K_1,3的图。显然，半无爪图是比无爪图更广泛的图类。

课题十五：圈设计

组合设计理论是离散数学的一个重要分支，这一理论的基本问题即是各类设计的存在性与构作，自1847年Kirkman解决一类经典的设计即Steiner三元系的存在性问题以来，关于组合设计的研究得到了蓬勃的发展。近几十年来可分解设计尤其得到重视，历史上著名的Kirkman女生问题即是研究λ=1时的可分解三元系(即Kirkman三元系)的存在性, 区组设计的存在性问题可以看作图分解为完全子图的问题.如Steiner三元系即为完全图的3阶完全图分解.在区组设计之后，圈设计自然地成为了图的分解问题的一个重要的研究对象。关于这一问题的研究最早可以追溯到20世纪60年代, Kotzig和Rosa解决了完全图K₂_´_k+1的k-圈分解问题.从那以后，圈分解问题尤其是完全图的可分解的圈分解问题引起了很多专家学者的关注。D．Bryant在中构作了K_2t+1与K_2t-F的Hamilton圈分解大集，以及K_2t与K_2t+1-f的Hamilton路分解大集，在完全图的圈分解问题中, Oberwolfach问题是其中重要的一类。这一问题是Ringle于1967年在德国Oberwolfach召开的图论会议上提出的，它研究的是是否可以把完全图分解成一些2-因子(2-正则生成子图)，使得所有的2-因子都同构于一个给定的2-因子F。当F由长为3的圈组成时，此问题即是Kirkman女生问题；而当F为一个Hamilton圈时，这一问题就是完全图的Hamilton圈分解问题。Hamilton-Waterloo问题是Oberwolfach问题的一个推广。对于给定的2-因子R和S, Hamilton-Waterloo问题研究是否能把完全图K_n(当n为奇数时)或Kn´In(当n为偶数时, In为Kn的一个1-因子)分解为若干个2-因子，使得其中r个2-因子同构于R，另外s个同构于S。当给定的两个2-因子分别由长为p和q的圈组成时，我们称这样的2-因子分解是均匀的，此时记2-因子分解为HW(n;r,s;p,q)

我导师钟集教授和他评论的欧拉奖获得者苏州大学朱烈、河北师范大学康庆德是这组合设计理论领域的领军人物，还有上海交通大学沈灏以及朱烈的博士常彦勋和他的更年轻有为的师弟葛根年教授

课题十六：控制圈（Dominating cycles）。

最近亚美尼亚国家科学院院士Zh.G. Nikoghosyan教授2009年在《离散数学》发表几个新概念的控制圈论文，其论文中列出他也提出的或别人的共8个猜想，它们是猜想 (l+c)连通图在某些最小度条件下的最长圈是PD_l-圈或最基本的控制圈以及相关问题（最长圈Ω是PD_l-圈是J.A.Bondy在1981年提出的概念。若l=0,则图是哈密顿图，若l=1,则最长圈是控制圈）。.Bondy 的视角是考察Ω是控制G-Ω的分支子图的路长，Zh.G. Nikoghosyan教授在2009年也相应考察Ω控制G-Ω的分支子图的圈长而提出CD_l-圈。不论如此，为推广哈密顿圈，从Ω控制某一（些）方面的状况出发，这2个概念的拓展都各有特色和优势。此外，我们还可以考察Ω是控制G-Ω的分支子图的直接影响和大小（点数或边数或匹配）等出发去提出概念：可为别记为DD_l-圈和，SD_l-圈。在Zh.G. Nikoghosyan教授送来的《离散数学》2011年出版的另一篇论文{Zh-21}中他们又解决4连通情况，即他们“记4连通图G的最长圈的长为c，若最小度³(c+k+4)/4，则这最长圈是控制圈”。如此，我们课题组既不因他不是国际顶级权威就不重视这方向（他能连续在权威杂志发表PD_l-圈方面的论文，就足于解决PD_l-圈领域问题），也不因最近《离散数学》多次发表这领域论文就重视(特别是出版论文有限的《组合学杂志B》已考虑他的课题)。他的课题是有待进一步开拓的重要课题是不争的现实，重要的是他的真诚迫近合作研究的愿望。我相信只要真诚合作，发挥各国的研究特色，取长补短互利促进，就能做出重要工作。因此，本人以及课题组部分研究精英将和他进行深入的交流合作，优先解决部分最受重视的猜想，若在充足研究其它课题下，也将花更多一些精力逐步去攻克更多猜想以形成更深入系统的理论工作。

最后，考察1990年Asratian和Khachatrian局部条件“n≥3阶图G的任意路xwy的不相邻点x,yÎSÍV(G), |S|≥3, 均有d(x)+d(y)≥ |N(x)∪N(y)∪N(w)|”，我们把这局部条件推广到S的cyclable：

:问题1：若n≥3阶图G的任意路xwy的不相邻点x,yÎSÍV(G), |S|≥3, 均有d(x)+d(y)≥ |N(x)∪N(y)∪N(w)| ，则S是cyclable？。

因上面条件等价于|N(x)∩N(y)|≥|N(w)\(N(x)∪N(y))|，可见这是一个非常漂亮的条件。

2007年Asratian和Khachatrian在Australa. J. Combin.提出局部条件的“范型”猜想：

猜想2 (Asratian和Khachatrian):若n≥3阶图G的距离是2的任意2点x,y均有max(d(x), d(y))≥ max(|M₃(x)|, |M₃(y)|)/2，则图G是哈密顿图。

其中M_r(x)是到x的距离不大于r的所有点组成的点集。显然，这条件又是他们的1990年的局部条件的推广。当上面猜想[4]中的M₃(x)换成M₄(x)时，他们已证明成立。而M_r(x)中的r=3时，这问题难度就更大，猜想也未必成立。显然，不论M_r(x)中的r是多少都有|M_r(x)|≤|V(G)|，如此r是多少，这猜想都推广范定理。因此，这是一新课题但要没有例外图才是极好问题-当然还是范的简洁，但还是应该做。

最后再说W-局部泛圈图：1999年Ladislav Stacho（Locally Pancyclic Graphs, J. Combin. Theory B 76 (1999), 1, 22--40.）推广上面cyclable和泛圈图概念而得（W-locally-pancyclic，即W-局部泛圈图的定义是：对图G的点数不少于3的点子集W，若G存在含W的i个点的圈，3≤i≤|W|）。当|W|=|V(G)|时, 图G就是泛圈图。Stacho并得到：

定理(Stacho ,1999): n≥3阶图G的W ÍV(G), |W|≥3，若对任意2个不相邻点x,yÎW, 均有d(x)+d(y)≥n，则G是W-局部泛圈图或G=K_n/2,n/2或|W|=4并G[W]= K_2,2，或另一个结构对称的例外图。

从定理，看到当|W|≤|V(G)|-1时，有几个例行图。可见探索这类结构的图虽然是推广上面2类图的有兴趣的工作，但难度也更大。如此至今几乎没有再在其它充分条件上开展探索。如此我们有问题：

问题: 若n≥3阶图G的W ÍV(G), |W|≥3，若对任意2个不相邻点x,yÎW, 均有|N(x)∪N(y)|≥n-δ，则G的非W-局部泛圈图有哪些？

（前世纪30年代左右德国学派在哈密顿图及其相关学科做出许多先导性开创性工作，追本溯源，可帮助理解现在的某些状况，如Robert Frucht1939年的立方体哈密顿图，他的导师是图论与组合数学大师Issai Schur，此人在柏林大学培养很多图论博士，这些博士又培养很多图论专家，所以这一学派值得关注）

课题十六-2：邻域并条件等的dominating paths（与以前不同的是这类控制路的点数有限制）。

近年的2017年Ralph J. Faudree, Ronald J. Gould, Michael S.Jacobson, Douglas B.West，发表最小度条件的控制路论文（Minimum degree and dominating paths. J. Graph Theory 84 (2017), no. 2, 202--213）得到分母为3和4的表达式型结果（本项目将先试探：是否可有象上面课题一，当图阶充分大时，可得有足够意义的更大分母或更小分子？），此论文中并提出的5个问题中的前3个问题的类型曾是我们多次研究的：

Question 1. For a > 1/3, what is the smallest constant c_a such that for large n, every n-vertex graph G with δ(G) ≥ a⋅n has a dominating path with at most c_a log1/(1−a) n vertices?

Question 2. For a > 1/(k +2) and n sufficiently large, what is the least s such that every k-connected n-vertex graph G with δ(G) ≥ a ⋅ n has a dominating path with at most s vertices?

Question 3. For fixed s∈N and n sufficiently large, what is the least t such that every n-vertex graph with minimum degree at least t has a dominating path with at most s vertices?

显然，去年的2018年Jill Faudree, Ralph J. Faudree, Ronald J. Gould, Paul Horn, Michael S.Jacobson再进一步发表度和条件的控制路论文（Degree sum and vertex dominating paths. J. Graph Theory 89 (2018), no. 3, 250--265），这是为解决上面问题2的度和的形式的，即这论文证明：

every n-vertex k-connected graph with s₂(G)³ 2n/(k+2)+f(k) contains a path of length at most 2k|T|, through any set of T vertices where |T|£n/(900k⁴).

基于上面课题最后部分所阐述的理由，以及本申请人赵克文和这2篇论文的作者Ronald J. Gould教授合作过2篇SCI杂志论文并他曾来信高度评价本人的工作，因此第2个研究内容是这邻域并条件的dominating paths。

课题十七：整数流理论

从有向图D的点u到v的流f是指定义在边集E(D) 上的函数,所有不同与u和v的顶点的流入值之和等于流出值之和。

命题：每一无桥的平面有向图都存在一个整数流，且每条边的流值属于集合{±1,±2,±3}

猜想：每一无桥的有向图都存在一个整数流，且每条边的流值属于集合{±1,±2,±3，±4}。这就是TUUTE提出的至今仍没有解决的5流猜想。

A是一个阿贝尔加法群,D(G)是G的定向图,一个A-流是指一个从边集E(D)到A的映射j，使得对任意点子集SÌ V(D)满足，å_e_Î_E+D(S)j(e)-å_e_Î_E_-_D(S)j(e)=0,其中的“0”是阿贝尔群中的单位元。

一个A -流j支撑集Supp(j)是指图中流值不为零的边的集合,

如果A-流j满足Supp(j)=E(G),则称是处处非零流.

一个阶数为k的加法群记为Z_k。

称j是图G的一个处处非零的k-流j是指j是一个处处非零的Z_k-流，且每条边eÎE(G)的流值满足0<j(e)<k。

Seymour在1994年世界数学家大会一小时的邀请报告中重点介绍了整数流理论的研究进展

课题十八-1：信息超图的圈分解问题（可参考这里）

课题十八-2： k-th power哈密顿圈猜想和我们提出的推广它的3个新猜想

课题十八-3：Masatoshi Enomoto和Yasuo Watatani的A graph theory for C*-Algebras。这里有个简短介绍

注意：这Masatoshi Enomoto非是图论大师Hikoe Enomoto！其源于这篇“A class of C∗-algebras and topological Markov chains”论文。这领域主要属于泛函分析，准确地说是属于“算子代数”，可参考Jean-Pierre Francoise等的《泛函分析和算子代数; 量子化方法和路径积分; 变分技术》（Jean-Pierre Francoise是做动力系统的而他的导师的导师正是Mauricio Matos Peixoto，他和Gregory Naber以及Tsou Sheung Tsun合著这书。他们3人还合写《无序系统;动力系统》-其重要分支遍历论的大部分主体就是围绕下面奖金最多的数学诺贝尔奖的Szemerédi引理和Szemerédi定理建立的.

课题十九：kth power of a Hamiltonian cycle问题：

1973年Paul Seymour教授推广Pósa猜想如下：

Pósa-Seymour猜想：A graph of order n with minimum degree at least ((k/(k+1))n contains the kth power of a Hamiltonian cycle。

迄今离散数学界唯一获得Abel阿贝尔奖的Endre Szemerédi长期为证明Pósa-Seymour猜想做出了很多努力。2010年他们再用新的方法几乎完全证明猜想（见Ian Levitt, Gábor Sárközy, Endre Szemerédi, How to avoid using the regularity lemma: Pósa's conjecture revisited. Discrete Math. 310 (2010), no. 3, 630–641。看这篇论文20篇参考文献中见引用Endre Szemerédi自己的论文有8篇并好几篇的标题含有Pósa-Seymour猜想一词）.

因这个猜想已差不多解决，目前也尚没有反例，那从事更进一步的课题就是时候了。如此，本申请人赵克文2013年在已有2百多年历史的英国Taylor & Francis出版社的J. Discrete Math. Sci. Cryptogr. 16 (2013), no. 2-3提出下面3个更进一步的更深刻的猜想并也取得一些进展。

猜想1（Ore型）： If graph G has d(u)+d(ν)≥2(k/(k+1))n for each pair of nonadjacent vertices u,v, then G contains the kth power of a Hamiltonian cycle。

猜想2（Fan型）：Let G be a 2-connected graph. If max{d(x),d(y)}≥((k/(k+1))n for any two vertices u,v of d(u,v)=2, then G contains the kth power of a Hamiltonian cycle。

猜想3（邻域并型）：Let G be a 2-connected graph. If |N(u)∪N(ν)|+δ≥2(k/(k+1))n for each pair of nonadjacent vertices u,v, then G contains the kth power of a Hamiltonian cycle。

因我们提出的这3个猜想都包含上面1973年的Paul Seymour猜想。因此，解决其中一个，也就解决Paul Seymour猜想，也就是解决2012年度阿贝尔奖获得者Szemerédi和合作者长期以来发表的许多论文。可见这是不会容易就能解决的问题，甚至是非常艰难的长期性问题。。

除了上面3类型问题之外，确实还有度序列型，如前年2017年英国伯明翰大学Katherine Staden, Andrew Treglown就对度序列型取得很好的进展：On degree sequences forcing the square of a Hamilton cycle. SIAM J. Discrete Math. 31(2017), no. 1, 383--437.

当然，不论是上面开创性的Pósa和Seymour的最小度型猜想还是上面3型猜想，都是远不够精确刻划的，随着研究的深入向前推进，需要引入相关参数来更精确地刻划。当然，对其结构还可做相关的描述。

如最近，Emory大学博士Andrzej Dudek, Christian Reiher，Andrzej Ruciński, Mathias Schacht（后者2004年才获得Emory大学图论博士但已是Discrete Math，SIAM J. Discrete Math，J. Combin. Theory B，J. Graph Theory等几个图论界最著名的杂志编委）刚合作完成的论文“Powers of Hamiltonian cycles in randomly augmented graphs”就是研究“Powers of Hamiltonian cycles”。

这里再要特别说上面4作者中的2个作者在2016年分别独立在美国《数学年刊》发表2篇论文：即Mathias Schacht，Extremal results for random discrete structures. Ann. of Math. (2)184 (2016), no. 2, 333–365.（这论文给出上面获得2012年阿贝尔奖的Szemerédi定理等的临界值，以及证明Turán型问题的一个猜想）。

Christian Reiher，The clique density theorem. Ann. of Math. (2) 184 (2016), no. 3, 683--707.

（证明Lovász和Simonovits在1983年提出的n点、gn²边图的g阶完全子图数的猜想）。

数学界都知道在《数学年刊》发表论文意味着什么！而他们其后最近仍合作研究这课题“power of a Hamiltonian cycle”，可见，这课题之分量。

课题二十：Erdős 猜想：

Paul Erdős在论文（Some old and new problems in various branches of combinatorics, Discrete Math. 165/166 (1997), 227--231）提出几个猜想问题，其中第一个问题在今年的Wiebke Bedenknecht, Guilherme Oliveira Mota, Christian Reiher, Mathias Schacht合作的论文（On the local density problem for graphs of given odd-girth. J. Graph Theory90 (2019), no. 2, 137–149）中的Conjecture 1.1 (Erdős). Every (a，b)=(1/2, 1/50)-dense graph contains a triangle（其中最后2个作者就是上面课题说到的在《数学年刊》分别独立发表各1篇论文的汉堡大学专家）。

Erdős在1997年的论文中说这猜想已提出几十年并设250美元奖寻求证明或否定，可见这猜想实在难，如此上面2019年的论文只研究不含triangle的界，那当然是考察a=1/2下的b<1/50或更低值的情况。其实它更只研究不含triangle的Andrásfai图，即研究与其同构的图类，是否都有b<1/50？而不含triangle的其它更多图类还没考察（当然Erdős在上面论文的第一段即关于上面Conjecture 1.1后在第二段说求使b³1/50的(10n，e_n）的最小e_n更恼人)。

2004年才毕业但已是图论所有重要杂志编委并在Ann. of Math独立发表论文的Mathias Schacht最近还合作发表下面相关论文：Josefran de Oliveira Bastos, Guilherme Oliveira Mota, Mathias Schacht, Jakob Schnitzer, Fabian Schulenburg，Loose Hamiltonian cycles forced by large(k-2)-degree. SIAM J. Discrete Math. 31 (2017), no. 4, 2328--2347.

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi，On the Hamiltonicity of triple systems with high minimum degree. Ann. Comb. 21 (2017), no. 1, 95--117.

E. Buß, H. Hàn, M. Schacht，Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs. J. Combin. Theory Ser. B 103 (2013), no. 6, 658--678.

Christian Reiher, Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi，Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs。

Yoshiharu Kohayakawa, Guilherme Oliveira Mota, Mathias Schacht，Monochromatic trees in random graphs. Math. Proc. Cambridge Philos. Soc. 166 (2019), no. 1, 191--208.

Paul Erdős接着在上面1997年论文的第3节说他和András Gyárfás在3年以前的提出并奖金提升到1000美元寻求解决的下面猜想（他可是“三无科学家”，能出到这样多钱可能是最高的了）：

Erdos-Gyárfás猜想（1995）: Every graph with minimum degree 3 has a cycle whose length is a power of 2。（即最小度是3的图存在某正整数m和它有长为2^m的圈。这猜想出于这论文。

最近Mohammad Ghaffari, Zohreh Mostaghim证明对某些Cayley图这猜想（Erdős-Gyárfás conjecture for some families of Cayley graphs. Aequationes Math. 92 (2018), no. 1, 1--6.）。

之前，也仅有几篇论文分别证明这猜想对planar claw-free graphs等几类较特殊的图成立；Pouria Nowbandegani等2014年证明对度数都是3的无爪图猜想成立（The Erdős-Gyárfás conjecture in claw-free graphs. Discuss. Math. Graph Theory 34 (2014), no. 3, 635--640.）Heckman和Krakovski在2013年证明对3-connected cubic planar graphs也成立（见Christopher Heckman, Roi Krakovski, Erdös-Gyárfás Conjecture for Cubic Planar Graphs，Electronic Journal of Combinatorics 20 (2013) , 2, P7）

这猜想实在是简洁漂亮。只需要最小度是3。而当阶很大时存在长为2^m的圈的可能性更倍增。但是要清理证明的头绪却很复杂。

总之，我们还可考虑，似乎Erdos-Gyárfás猜想能可推广到下面猜想1。同时，因本申请人已发现几类最小度是3的图没有长为2^2m的圈，但这些例外图都是结构对称漂亮的，因此，有必要提出下面问题2。此外，本申请人赵克文进一步提出供考虑最小度是4时的下面猜想3会如何：

猜想1: Every graph with minimum degree 3的存在某正整数m和有长2^2m+1的圈。

问题2:哪些graph with minimum degree 3的没有长为2^2m的圈，m是正整数。

猜想3: Every graph with minimum degree 4的存在某一正整数m和它既有长为2^2m的圈，也有长为2^2m+1的圈，及有长为2^3m的圈。

其中，猜想3的这3类圈2^2m、2^2m+1、2^3m都是指对同一个整数m。也可先研究更弱的猜想3：对最小度为的4图存在3个正整数m、k、s和有长为2^2m、2^2k
+1、2^3s的圈（因最小度是4是较强的，此条件应该存在3个不同的整数m，使猜想3中的3类圈分别存在。这时的问题比Erdos-Gyárfás猜想似乎还弱。为了加强猜想的戏剧性，就猜想存在紧密相关的这3类圈。猜想对小阶图不成立，若充分大阶图成立也是很有意思的）。不过，迄今仅解决Erdős -Gyárfás猜想的几类较特殊的图，那在如此困境下，把Erdős -Gyárfás猜想的最小度3升为4，是以做为猜想的过度性工作，也还是有分量的问题的。

这样艰难的长期性问题，适合那些有时间深入广泛掌握挖掘图论及相关学科尽可能多的方法又执着尝试的人。

课题二十：图论及遍历理论等中极其重要的Szemerédi正则引理

关于最近获得奖金近百万美元的阿贝尔奖的Szemerédi在60、70年代得到的Szemerédi正则引理和Szemerédi定理（以前2个数学最高奖Fields奖和Wolf奖的奖金好象仅几万和近十万），剑桥大学 Fields奖获得者Timothy Gowers教授在Ann. of Math.说Szemerédi Regularity Lemma的“precise statement is as follows”：

Szemerédi引理：Let e>0, Then there exists a positive integer K such that, given any graph G, the vertices can be partitioned into at most K sets V_i, with sizes differing by at most 1, such that all but at most eK² of the pairs (V_i, V_j) are e-regular.

（Szemerédi引理：对每个e>0和m³1，有一整数M使得每个阶至少是M的图G(V, E)必有一e-regular.划分P（|P|Î[m,M]）（注：e-regular.划分P 就是“划分(V₀ , V₁,…, V_k)(m£k£ M)能使至多ek²个G[V_i, V_j] (1£i<j£ k)不是e-regular）。对做图论的人只需先掌握有严格定义的e-regular（e-正则）概念就可理解）。

其重要性可参考Timothy Gowers写的安德烈·塞迈雷迪(Endre Szemerédi)的工作，陶哲轩写的What is Good Mathematics?有PDF（有翻译：什么是好数学？，也参可看他2006年写的一篇论文），Simonovits最近撰写的正则性引理与极值图论，

具体的描述也可参考牛津大学Alexander Scott教授下面的表达（Fields奖获得者Timothy Gowers和他的师弟Alexander Scott教授的导师Béla Bollobás院士曾在这里最后来信高度评价我们琼州大学的工作）：

剑桥Gowers和牛津Scott对引理的描述已非常清楚准确了。不过，既然上面M依赖于e和m，我就参考下面Lovász,主席的表达方式-把它们的关系更具体地表示出来如下：

Szemerédi引理：对每个e>0和每个m³1，存在整数k = k(e, m)和M=M (e, m)使得每个阶至少是k的图G(V, E)必有一e-regular.划分(V₀ , V₁,…, V_k)(m£k£M) 使至多ek²个G[V_i, V_j] (1£i<j£ k)不是e-regula。

只要了解密度(density d(A,B):=e(A,B)/|A||B|)、e-regularity(如果对所有满足|A¢|³e|A|和|B¢|³e|B|的点子集A¢ÌA，B¢ÌB，均有|d(A¢,B¢)-d(A,B)|£e)和e-regular.划分(满足引理结论的划分)就能理解上面引理-这就不详细解说了（上面Gowers的论文以及很多国外论文中都有它们-但似乎国内竟还没有见到在图论中如此重要如此基本的概念和引理以及下面定理？

下面László Lovász,主席的描述和Gowers的一样-仅是具体一点吧：

Szemerédi引理：For every e>0 and m>0 there is k = k(e, m) such that every graph G(V, E) on at least k nodes has an equipartition (V₀ , V₁,…, V_k)(m£k£ k(e, l)) such that subsets for all but ek² pairs indices (1£i<j£ k), the bipartite graph G[V_i, V_j] is e-regular。（理解概念equipartition就可理解它, 此文中有此概念的定义）。

下面是Erdős和Turán的1936年提出的一个猜想基础上形式的Szemerédi定理，见下面陶哲轩的论文：

Szemerédi定理：Let K³1 be a natural number, and let d>0. Them if N is sufficiently large, every subset A of [N]:={nÎZ: 1£ n £N} of cardinality |A|³dN contains an arithmetic progression a, a+r, …, a+(k-1)r of length k, where aÎZ and r is a positive integer.

关于Szemerédi引理，原先只是为了解决Erdős和Turán在1936年提出的一个猜想而引进的引理。然而，其后却在图论等相关学科发挥非常重要的作用，成为在图论和相关学科中很重要很基本的概念，并有各种形式的引理并推广到很多学科中去。

For ε > 0, a pair of vertex sets X and Y is called ε-pseudo-random, 如果满足|A¢|³e|A|和|B¢|³e|B|的点子集A¢ÌA，B¢ÌB，均有|d(A¢,B¢)-d(A,B)|£e。可见e-regularity和ε-pseudo-random是一致的。如此Gowers等推广引理和定理到Quasirandomness、Hypergraphs，在图论还有很多推广，如Scott 等推广到sparse graphs等。还可推广到其它学科，如概率、信息（Tao），分析（Lovász）等等

关于Erdős和Turán在1936年提出的一个猜想，长k = 1和k = 2是平凡的，最先，Klaus Roth在1953年证明k = 3时的情况，但他不是用图论的方法；再其后，Szemerédi在1968年解决1969年发表用图论方法（包括Szemerédi正则引理）证明k = 4时的情况；几年后的1974年Szemerédi再解决1975年再发表证明k 为任意长的情况。Hillel Furstenberg在1977年用遍历理论也给出这猜想的证明。把这引理和定理的推广到更多学科的各类形式，是一个近年来引人关注的课题

附：上面这几个人都是非常利害，如Erdős和陶哲轩(Tao) 高居世界历史上十位数学天才的第7和第10位。Gowers在国际奥林匹克数学竟赛中以满分42分获世界第一，Lovász,参加4届其中后2届都获满分-当时满分是40。国外参加这竟赛的大多是在业余时间只靠自已做准备，而我国是由顶级教师队伍来长期集中指导培训。这竟赛在1958年才开始-而上面2个数学诺贝尔奖获得者Klaus Roth和Hillel Furstenberg在1958年前已博士毕业，那应说也利害。看看这阵势-这或许是我国至今没有人做这课题一篇论文的原因吧？-按说中国人不会输给外国人,但很多氛围不允许你做如此艰巨的课题啊。

返回哈密顿图进展综述