A Tomographical Interpretation of a Sufficient Condition for h-Graphical Sequences

The notion of hypergraph generalizes that of graph in the sense that each hyperedge is a non-void subset of the set of vertices, without constraints on its cardinality. A fundamental and widely investigated notion related both to graphs and to hypergraphs is the characterization of their degree sequences, that is the lists of their vertex degrees. Concerning graphs, this problem has been solved in a classical study by Erdős and Gallai, while no efficient solutions are known for hypergraphs. If we restrict the (degree sequences) characterization to uniform hypergraphs, several necessary conditions are provided in the literature, but only few sufficient ones: among the latter, a recent one requires to split a sequence into suitable subsequences whose graphicality has to be recursively tested. Unfortunately, such an approach does not allow a direct efficient implementation. We study this problem under a tomographical perspective by adapting an already known reconstruction algorithm that has been defined for regular h-uniform degree sequences to the proposed instances, providing efficiency to the sufficient condition. Furthermore, we extend the set of h-uniform degree sequences whose graphicality can be efficiently tested. This tomographical approach seems extremely promising for further developments.