Minimal non-odd-transversal hypergraphs and minimal non-odd-bipartite hypergraphs

Yi-Zheng Fan ; Yi Wang¹ ; Jiang-Chao Wan¹

¹School of Mathematical Sciences, Anhui University

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

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.

Détail

DOI : 10.37236/9519

Classification : 05C65, 05D15, 05C35, 15A18
Mots-clés : minimal non-odd-transversal hypergraphs