最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.     

覆盖数不超过3的图上渡河问题

1000多年前,英国著名学者Alcuin曾提出一个古老的渡河问题,即狼、羊和卷心菜的渡河问题。2006年,Prisner把该问题推广到任意的冲突图上,考虑了一类情况更一般的渡河运输问题。所谓冲突图是指一个图G=(V,E),这里V代表某些物品的集合,V中的两个点有边连结当且仅当这两个点是冲突的,即在无人监管的情况下不允许留在一起的点。图G=(V,E)的一个可行运输方案是指在保证不发生任何冲突的前提下,把V的点所代表的物品全部摆渡到河对岸的一个运输方案。图G的Alcuin数定义为它存在可行运输方案时所需船的最小容量。本文讨论了覆盖数不超过3的连通图的Alcuin数,给出了该类图Alcuin数的完全刻画。     

平面图的Alcuin数

广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数, 给出了该类图Alcuin数的完全刻画。     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．     

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

3-一致超图的反馈数研究（英文）

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τ_c(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τ_c(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τ_c(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τ_c′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τ_c'(H)≤2m-n+p.     

一致超图中Berge线性森林的Turán数

设F是一个图,■是一个超图,如果存在一个双射φ:E(F)→E(■),使得?e∈E(F)有e?φ(e),那么称超图■是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作ex_r(n,Berge-F).线性森林是指连通分支全是路或者孤立顶点的图.设■_n,k是一类含有n个顶点k条边的线性森林图族.本文研究了r-一致超图中Berge-■_n,k的Turán数.当r≥k+1和3≤r≤■(k-1)/2■-1时,分别确定了ex_r(n,Berge-■_n,k)的精确值;当■(k-1)/2■≤r≤k时,给出了ex_r(n,Berge-■_n,k)的上界.     

图的平面Turán数和平面anti-Ramsey数

在所有顶点数为$n$且不包含图$G$作为子图的平面图中,具有最多边数的图的边数称为图$G$的平面Turán数,记为$ex_{_\mathcal{P}}（n,G）$。给定正整数$n$以及平面图$H$,用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$,则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数,记作$ar_{_\mathcal{P}}（n,H）$。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。     

3一致 C-超图的最小边数

混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k 1时,该下界是可以达到的．     

超图的强星色数

图的星色数的概念是由Ａ．Ｖｉｎｃｅ（１９８８）首次提出来的,它是图的色数的一个自然而又重要的推广,Ｌ．Ｈａｄａｄ等人（１９９４）将这一概念推广到一致超图,定义了ｈ－一致超图的强（弱）星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了３－一致循环超图的强星色数,它们的强星色数形成了一个严格介于３和４之间的递减序列．     

连通简单$r$-一致超图的约化

It is proved in this paper that if G is a simple connected r-uniform hypergraph with G ≥ 2, then G has an edge e such that G-e-V1(e) is also a simple connected r-uniform hypergraph. This reduction is naturally called a combined Graham reduction. Under the simple reductions of single edge removals and single edge contractions, the minor minimal connected simple r-uniform hypergraphs are also determined.     

对谱半径至多为$\sqrt[r]{2+\sqrt{5}}$的超图的分类研究

在本文,我们研究谱半径至多为$\sqrt[r]{2+\sqrt{5}}$的超图.我们得到此种超图必须具有一个基普结构,这与Woo-Neumaier在2007年对谱半径至多为$\frac{3}{2}\sqrt{2}$的图的分类结果类似.     

The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

The Ferry Cover Problem on Regular Graphs and Small-Degree GraphsThe Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

Dimension of Slices Through Fractals with Initial Cubic Pattern

In this paper, the Hausdorff dimension of the intersection of self-similar fractals in Euclidean space R~n generated from an initial cube pattern with an(n-m)-dimensional hyperplane V in a fixed direction is discussed. The authors give a sufficient condition which ensures that the Hausdorff dimensions of the slices of the fractal sets generated by "multirules" take the value in Marstrand's theorem, i.e., the dimension of the self-similar sets minus one. For the self-similar fractals generated with initial cube pattern, this sufficient condition also ensures that the projection measure μVis absolutely continuous with respect to the Lebesgue measure L~m. When μV《 L~m, the connection of the local dimension ofμVand the box dimension of slices is given.     

完全3-一致超图的圈分解

The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs K_n~(3) into k-cycles(3 ≤ k n) was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that K_(n·5m)~(3) can be decomposed into 5-cycles for n ∈{5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.