On the existence of semigraphs and complete semigraphs with given parameters

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 {E-1, E-2, ..., E-q} be a collection of subsets of P with (Ui-1Ei)-E-q = P. We derive an expression for the maximum value of the difference (Sigma(k)(j-1) vertical bar E-ij vertical bar - vertical bar(Ui-1Eij)-E-k vertical bar) for 2 <= k <= q, where every two of the sets in the collection can have at most one element in common. e show that this result helps in answering the question of whether there exists a semigraph on the vertex set P having edges {e(1), e(2), ..., e(q)}, where the set E-i is the set of vertices on the edge e(i), 1 <= i <= q. Combining the above two results, we characterize a complete semigraph. (C) 2021 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Engineering, Ain Shams University.

Automated summary

E. Sampathkumar has generalized a graph to a semigraph by allowing an edge to have more than two vertices. This article solves the issue of when a semigraph is complete, which relates to a problem noted by Gauss in 1796 about triangular numbers.