Article ID Journal Published Year Pages File Type
418871 Discrete Applied Mathematics 2014 13 Pages PDF
Abstract

Given integers m1,…,mℓm1,…,mℓ, the weighted clique graph   of GG is the clique graph K(G)K(G), in which there is a weight assigned to each complete set SS of size mimi of K(G)K(G), for each i=1,…,ℓi=1,…,ℓ. This weight equals the cardinality of the intersection of the cliques of GG corresponding to SS. 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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,