On the existence of semigraphs and complete semigraphs with given parameters

Abstract

E. Sampathkumar has generalized a graph to a semigraph by allowing an edge to have more than two vertices. Like in the case of graphs, a complete semigraph is a semigraph in which every two vertices are adjacent to each other. In this article, we have generalized a problem noted by Gauss in 1796 about triangular numbers and shown that it is the deciding factor of when a semigraph is complete.Let P be a set with p elements and {E1,E2,…,Eq} be a collection of subsets of P with ⋃i=1qEi=P. We derive an expression for the maximum value of the difference ∑j=1k|Eij|-⋃i=1kEij for 2⩽k⩽q, where every two of the sets in the collection can have at most one element in common. We show that this result helps in answering the question of whether there exists a semigraph on the vertex set P having edges {e1,e2,…,eq}, where the set Ei is the set of vertices on the edge ei,1⩽i⩽q. Combining the above two results, we characterize a complete semigraph.

Keywords

• Complete semigraph
• Triangular numbers
• Vertex degree