Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420622 | Discrete Applied Mathematics | 2008 | 11 Pages |
Abstract
A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
F. Larrión, M.A. Pizaña,