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

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

课题二:Cayley凯莱图的哈密顿性等问题

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

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

几十年来已做了很多研究,虽然进展不大,但最近,Igor Pak教授(他是哈佛大学博士、国际数学联盟主席László Lovász的博士后)和麻省理工Kleitman的博士Rados Radoicic2009证明“若有限群G的生成集S满足|S|≤log2|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—422s3>|G|-1,则G能被2个圈覆盖(更早的1987Enomoto等还得到d> (|G|-1)/3,则G能被2个圈覆盖)。Saito1999Degree sums and graphs that are not covered by two cycles. J. Graph Theory 32 (1999),1, 51-61)稍改进而有例外图:“s3|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.)提出推广的猜想:“s2n+1>(2n+1) (|G|-1)/3,则G能被2个圈覆盖”和猜想“s2n+1(2n+1) (|G|-1)/3,则G能被2个圈覆盖或2类例外图”,他们并证明猜想的n=2时的情况。

再就是:Ronald Gould教授的博士Colton Magnant的还没有出版的论文Partitioning graphs into paths or cycles of prescribed lengths”结合EnomotoOta2000Partitions of a graph into paths with prescribed endvertices and lengths. J. Graph Theory 34 (2000), no. 2, 163--169.)的猜想“n=a1+a2+…+at, s2≥n+t-1,则对任意t 个点x1,x2,…,xt,都有G都可划分为某t 条不交路P1,P2,…,Pt,使xiPi的一端点并|Pi|= ai,和2000Egawa等六人Vertex-disjoint cycles containing specified edges. Graphs Combin. 16 (2000), no. 1, 81--92.结果s2≥n+2t-2,则对任意2t 个点x1,x2,…,xty1,y2,…,yt,都有G都可划分为某t 条不交路P1,P2,…,Pt,使xiyiPi2端点 Colton Magnant只把后者的界加1提出猜想“n=a1+a2+…+at, s2≥n+2t-1, 则对任意2t 个点x1,x2,…,xty1,y2,…,yt,都有G都可划分为某t 条不交路P1,P2,…,Pt,使xiyiPi2端点并|Pi|= ai。还有一个G划分为t 个不交路圈的猜想(允许划分出的子图点数少于3的话,它们就是K1K2;还有是划分的圈Ci或路Pi可以与xiyi,这时界应比Ore条件弱,大概是s2≥n-t+1),等等。

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

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

课题三:图同态Homomorphism of graphs.

琼州大学做为海南省至今唯一的欧洲数学会《数学文摘》的评论员单位,这《数学文摘》就曾邀请我评论被当做数学诺贝尔奖Fields奖获得者Michael Freedman国际数学联盟主席László LovászAlexander 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教授,后两者分别在19981999年获得la BollobásNoga 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和以色列WISIrit Dinur,前者最近发表好几篇随机图论文,后者的论文主要是随机图的,也发表图同态和群同态的论文。

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

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

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

课题四:圈划分问题:

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

1996时在美国新奥尔良大学的现美国爱达荷大学Wang Hong-汪泓教授研究二分图,得到:设G=(V1,V2;E)是一个二分图,使得|V1|=| V2|=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能不能用d1,1或者s1,1代替上面Wang Hong的结果中的d(G)?(其中d1,1=min{d(x)+d(y)| xÎV1, yÎV2};  s1,1=min{d(x)+d(y)| xÎV1, yÎV2 ,xyÏE(G)}

问题2Wang Hong的结果中,如果不假定|V1|=| V2|,结论是否成立

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

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

kn1n23个正整数,G=(V1,V2;E)是一个二分图,使得|V1|= n1| V2|= n2,其中n1³2k+1n2³2k+1| n1n2|£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}的图的边定义为若|xx’|=1,|yy’|=1(x,y)(x’,y’)相邻。记其中的子图ECm,n的点集为{(x,y) | x+y是偶数}, OCm,n的点集为{(x,y) | x+y 是奇数},则子图ECm,n的点和OCm,n的点都不相邻而且它们刚好把这图划分。显然,ECm,nOCm,n的点数分别为mn/2ùëmn/2û。当mn是偶数时,ECm,nOCm,n同构。关于这类图,1982年国际奥林匹克数学竟赛中美国队唯一获得金牌26就成为哈佛大学正教授的Noam Elkies为第一作者的1992年的论文(James Alternating-sign matrices and domino tilings. I. J. Algebraic Combin. 1 (1992), no. 2, 111–132)称OC2n+1,2n+1nAztec菱形并证明OC2n+1,2n+1刚好有2n(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院士在他的上面论文中证明另一个结果“EC2n+1,2n+1的生成树数是OC2n+1,2n+14倍”。

Donald Knuth教授是如此处理的:记 二分图G的二部分点数为(p,q)、二分图H的二部点数为(r,s),其weak direct G´H定义为点(u,v)和点(u’,v’)相邻当且仅当uu’相邻、vv’相邻。记子图E(G, H)的点集:{(u,v)| uV(G)vV(H)是分别属于相对应的部分的点}, O(G,H)的点集:{(u,v)| uV(G)vV(H)是属于相反的部分的点},由定义知子图E(G,H)的点和子图O(G,H)的点都不相邻,且|V(E(G,H))|=pr+qs, |V(O(G,H))|=ps+qr。也有ECm,n=E(Pm,Pn)OCm,n=O(Pm,Pn),其中PmPn分别是点数为mn的路。Knuth证明(i):特征多项式P(E(G,H); x)P(O(G,H); x)满足P(E(G,H); x)P(O(G,H); x)= ∏j=1p+qk=1r+s(x-mjlk)P(E(G,H);x)=x(p-q)(r-s)P(O(G,H); x);也证明(ii): P(ECm,n; x)P(OCm,n; x)满足P(ECm,n; x)P(OCm,n; x)=∏j=1mk=1n[x-4cosjp/(m+1)cos kp/(n+1)];和证明(iii): P(ECm,n; x)=xmn  mod 2P(OCm,n; x);并证明(v): ECm,n的生成树数是P(OCm-2,n-2; 4) OCm,n的生成树数是P(ECm-2,n-2; 4)。如此由(iii)(v),得证“EC2n+1,2n+1的生成树是OC2n+1,2n+14倍”。

问题[6]:当ECm,n=E(Pm,Pn)OCm,n=O(Pm,Pn)PmPn换为树、偶圈、路之一时,情况又如何?能否求生成树数?能否求完美匹配数?是多少?或之间的关系如何?显然,也是很有兴趣的问题。

课题六:图的嵌入Graphs embeddable

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

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

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

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

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

定理:对于3-正则图G,其上有一个确向树Tod为路(在哈密顿圈上),有事实:每一个上树边gÎTod*Aux0G中伴随至多有两个变量,其一为树变量,另一为上树变量。

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

定理:任何一个3-正则可平面图G若有一个确向树Tod哈密顿圈上,则必有这样一个平面嵌入使得所有А0中的边皆在Tod上右(或左)侧而所有А1中的边皆在Tod的左(或右)侧。

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

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

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

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

定理:对于图G=(V, E)有一个确向树Tod哈密顿圈上,它的不同平面嵌入的数目为npe(G)=2c(Aux1G)-1

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

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

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

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

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

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

总而言之,正如美国工程院院士葛守仁教授说“在集成电路的布局中,通常用表示电路,将布图归结为在一些特定条件下图的嵌入”,但要从图的嵌入过度到实际的集成电路“布图设计”当然需要补充很多集成电路布图设计方面的知识和经验,而且随着集成电路布图设计的发展,任何人也得跟着发展。因很容易找到很多好著作和论文来参考,因篇幅所限,这里就不能做更多介绍。因此,如果我们项目获得资助,我们将象上面开创圈结构图理论一样,必定全力以赴,也将开拓出这领域崭新的系统性工作陈建二教授所攻读的是拓扑图论的博士学位,其导师之一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 {H1, H2, ,Hm} 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 GKm,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 Hj is denoted by åf(E(Hj)) then {åf(E(H1)), åf(E(H2)), ¼,åf(E(Hm))}={a, a+d, ¼,(m-1)d} with a=[m(n+1)2+(2n-1)(n+1)]/2 and d=-1.
结果3. If a non-trivial H-decomposable graph GKm,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 Hj is denoted by åf(V(Hj)) then {åf(V(H1)), åf(V(H2)), ¼,åf(V(Hm))}={a, a+d, ¼,(m-1)d} with a=mn+1+n(n+1)/2 and d=1.
结果4. Let GKm,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(H1)), åf(V(H2)), ¼,åf(V(Hm))}={a, a+d, ¼,(m-1)d} with a=mn+1+n(n+1)/2 and d=1. 
结果5. Suppose {H1, H2, ,Hm} is a H-decomposition of graph GKm,n with both m and n are even. Then G is not a H-V- super-strong magic decomposable graph.

课题七-2模糊图。

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

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

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

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

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

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

6Muhammad 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期也证明G2-边连通的,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-连通的或G12类图”(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 1hc(c)表示图Ghamiltonian染色 c 的最大染色数。图G Hamiltonian染色数hc(G)是全部Hamiltonian染色c min{hc(c)}它的最显著的意义在于:图G是哈密顿连通的当且仅当hc(G)=1 

2002ChartrandNebeský张平教授刻划 (n − 2)2 – 3≤ hc(G) ≤ (n –2)2 –1n (6)阶连通图G,得到

1hc(G)= (n−2)2 + 1ÛG=Sn.

2、如果G¹Snhc(G) ≤ (n−2)2–1

3hc(G)= (n–2)21ÛG=S¢n.

4、如果G¹SnG¹S¢nhc(G) ≤ (n–2)2–3

5hc(G)= (n–2)23ÛG=S²n.

2005ChartrandNebeský张平教授得到下面结果:

hc(Kn) = 1;当n 2时有hc(K1,n−1) = (n−2)2+1 ;当r2时有hc(Kr,r) =r hc(Cn) =n–2 (1)如果Gn (³3)阶哈密顿图,则hc(G) ≤ n−2。特别地,对任意整数k 1 n 3 (1 ≤k ≤ n−2),存在一个哈密顿图G使hc(G)=k (2)如果n (³ 4)阶连通图G的最长圈的长cir(G)=n1,则hc(G) ≤n–1(3) n (³ 2)阶连通图G均有 hc(G) ≤ (n−2)2+ 1(见Hamiltonian colorings of graphs. Discrete Appl. Math. 146 (2005), no. 3, 257--272.)。

2006Nebeský教授得到下面结果:

n (³ 3)阶连通图G,如果存在它的子图F 是满足2 £ i £(n+1)/2i阶哈密顿连通图,则有 hc(G) £(n−2)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.

2005ChartrandNebeský张平教授得到的其中主要结果是:

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.)。

2003Nebesky教授研究最长圈与hc(G)的关系。得到n (³ 7)阶连通图G的最长圈的长cir(G)=n2,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)。特别研究caterpillarsdouble starsOn Hamiltonian colorings for some graphs. Discrete Appl. Math. 156 (2008), no. 15, 3028--3034..

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

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

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

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

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

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

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

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

还可进一步研究AsratianKhachatrian的上面局部度和条件:

研究[5]: 2-连通图nG任意路xwy的不相邻点x,y 均有d(x)+d(y)≥ |N(x)N(y)N(w)|+k, Gk-path哈密顿图吗?2-连通图nG任意路xwy的不相邻点x,y 均有d(x)+d(y)≥ |N(x)N(y)N(w)|+k+1, Gk-path哈密顿连通图吗?

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

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

它们在这论文中说数学大师Erdos、法国巴黎第11大学Flandrin和李皓教授等分别在下面2篇论文证明“阶n≥k4和独立数α(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年的论文中也举例说明如果阶还能改进,那最好的阶至多是Ω(k2)。因此,若还能对指数改进1甚至1/2,都是一个非常大的突破和进展。如此,在目前看来,似乎离最好可能还非常远。

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

关于包含邻域并和距离是2范型AsratianKhachatrian的上面局部度和条件等情况,因还没有定义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ÎC2(6,k)除了可收缩为4个特殊图的图外,G均是超欧拉图”,它推广1999年以来的相关论文的工作。当然,一般情况Ch(l,K)中很多有趣类图的超欧拉图性的刻划仍是值得研究的待解决的问题。此外,超欧拉图的研究中还有其它许多有趣的问题。梁艳婷教授在跟赖虹建教授做博士生前跟我的导师柳柏濂教授读硕士,如此感到她的某些课题与我的可能相近)。众所周知,超欧拉图是图论中最古老又方兴未艾的领域,在图论教材中都会列为很重要的部分来讲解,因此大家都应有很好的基础。这为其后的进展,是很好的铺垫。因篇幅所限,这里不能做更多新进展的介绍。但因教授和欧洲数学会发展中国家委员会主席Fleischner是这领域最正宗的世界权威,在他们那里特别是教授那里可获得足够多的材料。

课题十二-1无爪图(K1,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 KiersteadXingxing Yu,(见会议网页 http://meetings.siam.org/sess/dsp_programsess.cfm?SESSIONCODE=9864

Gould教授也在2010年的“第23Cumberland 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? (若G4连通时,则哪些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连通无爪图的泛圈性?因此,本课题也将考虑问题48连通或9连通无爪图的泛圈图性。当然,泛连通图等如何也是要完成的课题

捷克大师Zdeněk Ryjáček1999年在《离散数学》得到: “3连通无爪图GZ4-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连通无爪图GZ8-free的,则G是哈密顿图Lai, Hong-Jian; Xiong, Liming; Yan, Huiya; Yan, Jin. Every 3-connected claw-free Z8-free graph is Hamiltonian. J. Graph Theory 64 (2010), 1, 1-11.

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

问题:“3连通无爪图GZ4-free的,则G是泛圈图吗?”

问题:“4连通无爪图GZ8-free的,则G是泛圈图吗?”

否则,问题h是多少时,3连通{K1,3, Zh}-freeG是泛圈图?”

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

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

2013Gould教授和他的4个博士在《离散数学》杂志证明4连通{K1,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

2012Ferrara,WagnerMorris在《图论杂志》证明:4连通{K1,3,P9}-free图是泛圈图Pancyclicity of 4-Connected, Claw-Free, P10-Free GraphsJ. Graph Theory, 71(2012), 4, 435–447

2013年赖虹建教授和他的合作者也得到3连通{K1,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);还有2012KaiserVrana证明最小度不小于65连通无爪图是哈密顿图 (Hamilton cycles in 5-connected line graphs , Euro.  J. Combin. 33 (2012), 924-947)。如此对Gould的问题还可研究3连通5连通的情形

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

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

1991ChoudumPaulraj得到:若无爪图G的最小度d(G)≥4,则G2因子(见Regular factors in K1,3-free graphs. J. Graph Theory 15 (1991), 3, 259-265);1996OtaTokuda得到:若K1,s-free Gd(G)≥2s−2,则G2因子(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≥3a3/2,则G有一个最大独立集S和有a个圈组成的2因子,使得每一圈含S的一点。

最近Kužel, OzekiYoshimoto论文研究一延伸课题(即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