enter image description here 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.

  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Feb 28 '17 at 16:05
  • $\begingroup$ 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 $\endgroup$ – Pepper M Feb 28 '17 at 16:11
  • $\begingroup$ It looks like the average degree of general graph is bounded? $\endgroup$ – Pepper M Feb 28 '17 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.