what type is the graph reduced from k-regular hypergraph? A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. If each $|V| = 2$, H is a general graph.

The degree $d(v)$ of a vertex v is the number of edges that contain it. H is k-regular if every vertex has the same degree k.

My question is: If we reduce a k-regular hypergraph to a general graph by replacing each edge with a clique, then the resulted general graph is not of bounded degree (the degree of a vertex can be up to n-1 where n is the total number of vertices). However I think it must be a special type of graph, I cannot figure out which type it is.

If you can help me out here I'd really appreciate it.

• What you call bounded is usually called regular. A bounded-degree graph is just a graph in which all degrees are bounded by some $k$ (this definition only makes sense for a family of graphs, say all valid inputs to some algorithm). – Yuval Filmus Feb 28 '17 at 16:05
• Yuval, Thanks! In my application problem, the hypergraph $H$ is dual of another k-uniform hypergraph hence $H$ is k-regular, I am thinking reducing it to general graph however it lost the nice bounded degree property – Pepper M Feb 28 '17 at 16:11
• It looks like the average degree of general graph is bounded? – Pepper M Feb 28 '17 at 17:41