On the semigroup whose elements are subgraphs of a complete graph

Abstract

© 2018 by the author. Let Knbe a complete graph on n vertices. Denote by SKnthe set of all subgraphs of Kn. For each G, H ∈ SKn, 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 SKnis a semigroup under the ring sum. In this paper, we study Green's relations on SKnand characterize ideals, minimal ideals, maximal ideals, and principal ideals of SKn. Moreover, maximal subsemigroups and a class of maximal congruences are investigated. Furthermore, we prescribe the natural order on SKnand consider minimal elements, maximal elements and covering elements of SKnunder this order.