Self‐clique graphs and matrix permutations

DOI10.1002/jgt.10496zbMath1031.05115OpenAlexW2604724570MaRDI QIDQ4446891

Guillermo Durán, Min Chih Lin, Adrian Bondy, Jayme Luiz Szwarcfiter

Publication date: 3 February 2004

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/174244

zbMATH Keywords

computational complexityclique graphself-clique graphclique-Helly graphpermuted matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On self-clique shoal graphs ⋮ Faster recognition of clique-Helly and hereditary clique-Helly graphs ⋮ Split clique graph complexity ⋮ Biclique graphs of interval bigraphs ⋮ On self-clique graphs with triangular cliques ⋮ Symmetric games revisited ⋮ Biclique-Helly graphs ⋮ On hereditary clique-Helly self-clique graphs ⋮ Self-clique Helly circular-arc graphs ⋮ Biclique graphs and biclique matrices ⋮ The complexity of clique graph recognition ⋮ On self-clique graphs with given clique sizes. II ⋮ Biclique graphs of split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NP-completeness of the bandwidth minimization problem
• On clique-critical graphs
• Permuting matrices to avoid forbidden submatrices
• On self-clique graphs with given clique sizes
• A characterization of clique graphs
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization
• A partial characterization of clique graphs