图与超图中的彩色匹配综述

超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.     

最大边连通和super-边连通超图的充分条件

设H是连通超图。若超图H的边连通度等于其最小度,则称H是最大边连通的。若超图H的每个最小边割总是由关联于某个最小度顶点的边集所构成,则称H是super-边连通的。首先给出一致线性超图是最大边连通超图的度序列条件。其次,给出一致线性超图是super-边连通超图的度条件。这些结果分别推广了Dankelmann和Volkmann（1997）以及Hellwig和Volkmann（2005）在图上的相关结论。     

超图的最优标号与特征值

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

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

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

秩为r的本原超图的指数集(英文)

本文研究了超图的本原性质.运用图论方法,得到了具有秩r(≥3)的所有n阶本原有向超图的指数集,并刻划了其极超图.     

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

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

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

本原简单超图的指数集

设H是一个超图, 用H\+*和L(H)分别表示H的对偶超图和线图. 定义H的邻接图是由L(H\+*)和H的所有环组成的图, 记作G\-H. 若G\-H是本原的, 则称H是本原的, 并称γ(G\-H)为H的指数. 该文得到了所有n阶本原简单超图以及所有秩不小于3的n阶本原简单超图的指数集, 并分别刻划了其极超图.     

无圈超图的计数

研究了标号超图的计数, 得到2个公式: 一个是关于严格(D)-连通无圈齐超图的显式计数公式, 另一个是关于线性无圈超图数目的递推公式.     

基于超图的超网络研究综述

超网络是一般网络的一类自然推广。超网络的研究将会有助于理解“复杂系统之所以复杂”这一极其重要的问题。现实世界中,很多复杂的系统都可以用超网络描述。超网络分为基于网络的超网络与基于超图的超网络。本文主要介绍的是基于超图的超网络,首先对超图理论进行描述,然后对基于超图的超网络进行分析,接着提出了基于超图的超网络和多层超网络的转换及实例并提出了基于超图的超网络演化模型。本文最后对超网络今后的研究方向进行了探讨,其中,超网络的指标构建、动力学研究、链路预测、应用等方面还有待于深入研究。     

Codismantlability and projective dimension of the Stanley–Reisner ring of special hypergraphs

In this paper, we generalize the concept of codismantlable graphs to hypergraphs and show that some special vertex decomposable hypergraphs are codismantlable. Then we generalize the concept of bouquet in graphs to hypergraphs to extend some combinatorial invariants of graphs about disjointness of a set of bouquets. We use these invariants to characterize the projective dimension of Stanley–Reisner ring of special hypergraphs in some sense.     

New short proofs to some stability theorems

We present new short proofs to both the exact and the stability result of two extremal problems. The first result is about the extension of Turán’s theorem to hypergraphs, and the second result is about cancellative hypergraphs. Our proofs are concise and straightforward, but give a sharper version of stability theorems to both problems.     

Strictly balanced uniform hypergraphs and generalizations of Zero-One Law

In this work we describe the spectra of all rational numbers that could be a density of a strictly balanced uniform hypergraph. We also introduce some specific constructions of strictly balanced uniform hypergraphs, and exploit them to generalize some results about Zero-One Law and Zero-One k-Law to the case of random uniform hypergraphs.     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

On the discovery of the cycle-axiom of hypergraphs

In this paper, the path through which the cycle axiom of hypergraphs was discovered will be retraced. The long process of discovery will be described, in particular how acyclic hypergraphs originated from the study of relational database schemes and how cycles of hypergraphs originated from the study of acyclic hypergraphs.