On Maximal Clique Irreducible Graphs

Abstract

A graph $G$ is said to be maximal clique irreducible if each maximal clique in $G$ contains an edge which is not contained in any other maximal clique of $G$. In 1981, Opsut and Roberts proved that any interval graph is maximal clique irreducible. In this paper, we generalize their result and consider the question of characterizing maximal clique irreducible graphs.