✦ LIBER ✦

Self-clique graphs and matrix permutations

✍ Scribed by Adrian Bondy; Guillermo Durán; Min Chih Lin; Jayme L. Szwarcfiter

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 140 KB
Volume: 44
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10496

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Squares, clique graphs, and chordality

✍ W. D. Wallis; Julin Wu 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB

## Abstract We study the squares and the clique graphs of chordal graphs and various special classes of chordal graphs. Chordality conditions for squares and clique graphs are given. Several theorems concering chordal graphs are generalized. © 1996 John Wiley & Sons, Inc.

Clique Minors in Graphs and Their Comple

Clique Minors in Graphs and Their Complements

✍ Bruce Reed; Robin Thomas 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 107 KB

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 . Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has

Metric characterizations of proper inter

Metric characterizations of proper interval graphs and tree-clique graphs

✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

Graph relations, clique divergence and s

Graph relations, clique divergence and surface triangulations

✍ F. Larrión; V. Neumann-Lara; M.A. Pizaña 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

## Abstract This work has two aims: first, we introduce a powerful technique for proving clique divergence when the graph satisfies a certain symmetry condition. Second, we prove that each closed surface admits a clique divergent triangulation. By definition, a graph is clique divergent if the orde

Iterated clique graphs with increasing d

Iterated clique graphs with increasing diameters

✍ Bornstein, Claudson F.; Szwarcfiter, Jayme L. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(K i (G)) = diam(G) + i. Exam