Minimal Non-Odd-Transversal Hypergraphs and Minimal Non-Odd-Bipartite Hypergraphs
Minimal Non-Odd-Transversal Hypergraphs and Minimal Non-Odd-Bipartite Hypergraphs
复制标题
DOI：
10.37236/9519
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Yi-Zheng Fan;Yi Wang;Jiang-Chao Wan
中科院分区：
文献类型：
--
作者：
Yi-Zheng Fan;Yi Wang;Jiang-Chao Wan
在所有具有偶一致的一致超图中，从结构和谱的角度来看，奇横或奇二部超图都比二部超图更接近二部简单图。一个超图称为奇数横截超图，如果它包含一个顶点集的子集，使得每条边都在奇数个顶点中与该子集相交；如果它不是奇数横截的，但删除任何边都会得到一个奇数横截超图，则它称为最小非奇数横截超图。本文利用极小非奇横截超图在{Z}2上的关联矩阵的度和秩给出了它的一个等价刻画。如果一个极小非奇横截超图是一致的，那么它是偶一致的，因此是极小非奇二部图。刻画了极小非奇二部超图的$2$正则一致超图，并给出了几个极小非奇二部$d正则一致超图的例子。最后给出了极小非奇二部超图邻接张量的最小H-特征值的上界。
Among all uniform hypergraphs with even uniformity, the odd-transversal or odd-bipartite hypergraphs are closer to bipartite simple graphs than bipartite hypergraphs from the viewpoint of both structure and spectrum. A hypergraph is called odd-transversal if it contains a subset of the vertex set such that each edge intersects the subset in an odd number of vertices, and it is called minimal non-odd-transversal if it is not odd-transversal but deleting any edge results in an odd-transversal hypergraph. In this paper we give an equivalent characterization of the minimal non-odd-transversal hypergraphs by means of the degrees and the rank of its incidence matrix over $\mathbb{Z}_2$. If a minimal non-odd-transversal hypergraph is uniform, then it has even uniformity, and hence is minimal non-odd-bipartite. We characterize $2$-regular uniform minimal non-odd-bipartite hypergraphs, and give some examples of $d$-regular uniform hypergraphs which are minimal non-odd-bipartite. Finally we give upper bounds for the least H-eigenvalue of the adjacency tensor of minimal non-odd-bipartite hypergraphs.