On the Semigroup Whose Elements Are Subgraphs of a Complete Graph

Abstract

Let K n be a complete graph on n vertices. Denote by S K n the set of all subgraphs of K n . For each G , H ∈ S K n , the ring sum of G and H is a graph whose vertex set is V ( G ) ∪ V ( H ) and whose edges are that of either G or H, but not of both. Then S K n is a semigroup under the ring sum. In this paper, we study Green’s relations on S K n and characterize ideals, minimal ideals, maximal ideals, and principal ideals of S K n . Moreover, maximal subsemigroups and a class of maximal congruences are investigated. Furthermore, we prescribe the natural order on S K n and consider minimal elements, maximal elements and covering elements of S K n under this order.

Keywords

• complete graph
• Green’s relations
• ideal
• natural order
• maximal subsemigroup
• maximal congruence