Characterization of classical graph classes by weighted clique graphs

BONOMO, FLAVIA; SZWARCFITER, JAYME

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2014 vol. 165 p. 83 - 95

0166-218X

Given integers $m_1, ldots, m_{ell}$, the emph{weighted clique graph/} of $G$ is the clique graph $K(G)$, in which there is a weight assigned to each complete set $S$ of size $m_i$ of $K(G)$, for each $i = 1, ldots, ell$. This weight equals the cardinality of the intersection of the cliques of $G$ corresponding to $S$. We characterize weighted clique graphs in similar terms as Roberts and Spencer´s characterization of clique graphs. Further we characterize several classical graph classes in terms of their weighted clique graphs, providing a common framework for describing some different well-known classes of graphs, as hereditary clique-Helly graphs, split graphs, chordal graphs, interval graphs, proper interval graphs, line graphs, among others.