Self-Clique Graphs and Matrix Permutations

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-...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2003
Materias:	Clique graph Clique-Helly graph Computational complexity Permuted matrix Selfclique graph Algorithms Matrix algebra Vectors Clique graphs Matrix permutations Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v44_n3_p178_Bondy http://hdl.handle.net/20.500.12110/paper_03649024_v44_n3_p178_Bondy
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03649024_v44_n3_p178_Bondy
record_format	dspace
spelling	paper:paper_03649024_v44_n3_p178_Bondy2025-07-30T18:12:43Z Self-Clique Graphs and Matrix Permutations Clique graph Clique-Helly graph Computational complexity Permuted matrix Selfclique graph Algorithms Computational complexity Matrix algebra Vectors Clique graphs Matrix permutations Graph theory 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. 2003 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v44_n3_p178_Bondy http://hdl.handle.net/20.500.12110/paper_03649024_v44_n3_p178_Bondy
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Clique graph Clique-Helly graph Computational complexity Permuted matrix Selfclique graph Algorithms Computational complexity Matrix algebra Vectors Clique graphs Matrix permutations Graph theory
spellingShingle	Clique graph Clique-Helly graph Computational complexity Permuted matrix Selfclique graph Algorithms Computational complexity Matrix algebra Vectors Clique graphs Matrix permutations Graph theory Self-Clique Graphs and Matrix Permutations
topic_facet	Clique graph Clique-Helly graph Computational complexity Permuted matrix Selfclique graph Algorithms Computational complexity Matrix algebra Vectors Clique graphs Matrix permutations Graph theory
description	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.
title	Self-Clique Graphs and Matrix Permutations
title_short	Self-Clique Graphs and Matrix Permutations
title_full	Self-Clique Graphs and Matrix Permutations
title_fullStr	Self-Clique Graphs and Matrix Permutations
title_full_unstemmed	Self-Clique Graphs and Matrix Permutations
title_sort	self-clique graphs and matrix permutations
publishDate	2003
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v44_n3_p178_Bondy http://hdl.handle.net/20.500.12110/paper_03649024_v44_n3_p178_Bondy
_version_	1840323087505031168

Self-Clique Graphs and Matrix Permutations

Ejemplares similares