关于超Euler图的一个猜想的注记

本文研究了Catlin的关于超Euler图的一个猜想,借助于收缩方法,得到了该猜想的两个充分条件.     

超图的最优标号与特征值

研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界.     

超图在圈中的嵌入问题

H为定义在圈G上的一个超图,将H的每条超边映射为圈G中不同的路,并且这条路包含此超边中的所有的顶点,此问题称为超边在圈G中的嵌入问题(MCHEC问题).超图在圈中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.应用组合最优化以及概率方法可得到MCHEC问题的PTAS算法.     

完全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.     

无标号真严格(d)-连通无圈超图的计数

本文得到了无标号真严格(d)-连通无圈超图的计数公式,并得到了无标号真严格(d)-连通同胚k不可约无圈超图的计数公式.     

关于D-完全一致混合超图上色数的一个结论的推广

混合超图的上、下色数的研究是超图研究中一个重要的话题.由于超图本身结构上的复杂性,近年来对超图色性的研究也近局限于对一些特殊图类的研究,其中完全一致混合超图是最为热门的图类之一.给出了D完全(C不完全)一致混合超图的概念,并运用组合数学中有关分划的思想和方法对该图类的色性进行了进一步的研究,对相关文献中给出的结论进行了推广,得到了一个较为一般化的结论.并在该定理的证明中得到并证明了一个关于混合超图C稳定集的重要论断,对超图色性研究有着重要的意义.     

强二部超图的饱和数

给定r-图F,称一个r-图G是F-饱和的,如果G不包含F,但是对于每条满足e∈E((G))的r-边e,G添加该边后会包含F,其中(G)表示G的补图.r-图F的饱和数,记为satr(n,F),指的是n个顶点的F-饱和r-图的最小边数.令Srl,m为一个有l+m个顶点的r-图,其边集合由所有与某固定l-集合交集非空的边组成...     

图的2-控制数的上界和一个Graffiti.pc猜想（英文）

设G=(V(G),E(G))是一个图,k是一个正整数.称一个顶点子集S为G的kk-控制集,若V(G)\S中的每个顶点在S中至少有k个邻点,我们用r_k (G)表示kk-控制集的最小阶数.令d₁≤d₂≤…≤d_n为图G的度序列.当n为偶数时,度序列中位数m(G)=d_n/2+1,当n为奇数时,度序列中位数m(G)=d_n+1/2.一个仍未解决的Graffiti.pc猜想说:对任一n个顶点的连通图G,r₂(G)≤n-m(G)+1.首先我们证明了此猜想的一个弱形式:r2(G) ≤n-d₁+1.此外,通过拓展此猜想在二部图上的结果,我们证明了对最小度不小于2的无三角形图G,r2(G)≤n-Δ(G),其中Δ(G)为图G的最大度.众所周知,每一个其边数不少于顶点数的图都包含一个圈.我们将此结论推广到超图上.进而得到上述猜想对所有分裂图都成立.     

线性超图的边染色

超图$H$的一个$k$-边染色是用$k$种颜色的边染色, 使得相交的边染不同的颜色. Erd\H{o}s-Faber-Lov\''asz猜想认为任一$n$个顶点的无环线性超图都有一个$n$-边染色. 2021年, Kang, Kelly, K\"uhn, Methuku和Osthus对充分大的$n$确认了该猜想成立. 在本文中, 我们证明该猜想对弱冲突的超图是成立的. 这严格拓展了Bretto, Faisant 和Hennecart在2020年的两个相关结果.