zbMATH — the first resource for mathematics

On hereditary clique-Helly self-clique graphs. (English) Zbl 1138.05054
Summary: 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.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI
[1] Balakrishnan, R.; Paulraja, P., Self-clique graphs and diameters of iterated clique graphs, Utilitas math., 29, 263-268, (1986) · Zbl 0614.05053
[2] Balconi, G.; Grieco, M.; Zucchetti, B., Grafi di dualità di strutture d’incidenza, Bol. un. mat. ital. B, 18, 5, 799-810, (1981) · Zbl 0487.05035
[3] Balconi, G.; Grieco, M.; Zucchetti, B., Algoritmo per la construzione di grafi di dualitá, Atti sem. mat. fis. univ. modena, XXX, 131-137, (1981) · Zbl 0505.05035
[4] Bondy, A.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L., Self-clique graphs and matrix permutations, J. graph theory, 44, 178-192, (2003) · Zbl 1031.05115
[5] Bonomo, F.; Durán, G., Computational complexity of classical problems for hereditary clique-Helly graphs, Pesquisa operacional, 24, 435-443, (2004)
[6] Chia, G.L., On self-clique graphs with given clique sizes, Discrete math., 212, 185-189, (2000) · Zbl 0945.05050
[7] Escalante, F., Über iterierte clique-graphen, Abh. math. sem. univ. Hamburg., 39, 58-68, (1973) · Zbl 0266.05116
[8] Hamelink, R.C., A partial characterization of clique graphs, J. combin. theory, 5, 192-197, (1968) · Zbl 0167.22203
[9] Larrión, F.; Neumann-Lara, V.; Pizaña, M.A.; Porter, T.D., Self-clique graphs with prescribed clique-sizes, Congressus numerantium, 157, 173-182, (2002) · Zbl 1032.05101
[10] Larrión, F.; Neumann-Lara, V.; Pizaña, M.A.; Porter, T.D., Recognizing self-clique graphs, Mat. contemporânea, 25, 125-133, (2003) · Zbl 1049.05057
[11] Larrión, F.; Neumann-Lara, V.; Pizaña, M.A.; Porter, T.D., A hierarchy of self-clique graphs, Discrete math., 282, 193-208, (2004) · Zbl 1042.05073
[12] Lim, C.K.; Peng, Y.H., On graphs without multicliqual edges, J. graph theory, 5, 443-451, (1981) · Zbl 0492.05056
[13] McKee, T.A., A new characterization of strongly chordal graphs, Discrete math., 205, 245-247, (1999) · Zbl 0942.05060
[14] Prisner, E., Hereditary clique-Helly graphs, J. combin. math. combin. comput., 14, 216-220, (1993) · Zbl 0794.05113
[15] Roberts, F.S.; Spencer, J.H., A characterization of clique graphs, J. combin. theory ser. B, 10, 102-108, (1971) · Zbl 0215.05801
[16] Szwarcfiter, J.L., Recognizing clique-Helly graphs, Ars combin., 45, 29-32, (1997) · Zbl 0933.05127
[17] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. comput., 6, 505-517, (1977) · Zbl 0364.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.