ON CHARACTERIZING WEAKLY MAXIMAL CLIQUE IRREDUCIBLE GRAPHS

摘要

In a graph we call a maximal clique essential if it contains an edge which is not contained in any other maximal cliques. A graph in which each maximal clique is essential, or equivalently the set of all maximal cliques is a set of least number of maximal cliques that contains every edge, is said to be maximal clique irreducible. Maximal clique irreducible graphs were introduced and studied by W.D. Wallis and G.-H. Zhang in 1990 [8]. We define a graph to be weakly maximal clique irreducible if the set of all essential maximal cliques is a set of least number of maximal cliques that contains every edge. Note that maximal clique irreducible graphs are weakly maximal clique irreducible. In this article, we obtain the characterization of hereditary type for the weakly maximal clique irreducible graphs.