Premium
Self‐clique graphs and matrix permutations
Author(s) -
Bondy Adrian,
Durán Guillermo,
Lin Min Chih,
Szwarcfiter Jayme L.
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10496
Subject(s) - combinatorics , mathematics , clique graph , split graph , simplex graph , block graph , discrete mathematics , clique sum , clique , chordal graph , line graph , graph , graph power , 1 planar graph
The clique graph of a graph is the intersection graph of its (maximal) cliques. A graph is self‐clique when it is isomorphic with its clique graph, and is clique‐Helly when its cliques satisfy the Helly property. We prove that a graph is clique‐Helly and self‐clique if and only if it admits a quasi‐symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex‐clique duality. We describe new classes of self‐clique and 2‐self‐clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). We prove that deciding whether a (0,1)‐matrix admits a symmetric (quasi‐symmetric) permuted matrix is graph (hypergraph) isomorphism complete. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 178–192, 2003