Self-Clique Graphs and Matrix Permutations

Mostrar todas las versiones(2)

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
Autores principales:	Bondy, A., Durán, G., Lin, M.C., Szwarcfiter, J.L.
Formato:	JOUR
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:	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	todo:paper_03649024_v44_n3_p178_Bondy
record_format	dspace
spelling	todo:paper_03649024_v44_n3_p178_Bondy2023-10-03T15:27:39Z Self-Clique Graphs and Matrix Permutations Bondy, A. Durán, G. Lin, M.C. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Bondy, A. Durán, G. Lin, M.C. Szwarcfiter, J.L. 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.
format	JOUR
author	Bondy, A. Durán, G. Lin, M.C. Szwarcfiter, J.L.
author_facet	Bondy, A. Durán, G. Lin, M.C. Szwarcfiter, J.L.
author_sort	Bondy, A.
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
url	http://hdl.handle.net/20.500.12110/paper_03649024_v44_n3_p178_Bondy
work_keys_str_mv	AT bondya selfcliquegraphsandmatrixpermutations AT durang selfcliquegraphsandmatrixpermutations AT linmc selfcliquegraphsandmatrixpermutations AT szwarcfiterjl selfcliquegraphsandmatrixpermutations
_version_	1807318400334036992

Self-Clique Graphs and Matrix Permutations

Ejemplares similares