Neighborhood hypergraphs of digraphs and some matrix permutation problems

DOI10.1016/j.dam.2009.03.023zbMath1209.05108MaRDI QIDQ967325

Igor Edm. Zverovich, Vladimir A. Gurvich

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.03.023

zbMATH Keywords

symmetrizability; graph isomorphism problem; involutory automorphisms; matrix complementation; matrix symmetrization; neighborhood dihypergraph; neighborhood hypergraphs of digraphs and orgraphs; skew-symmetrizability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C20: Directed graphs (digraphs), tournaments

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Le problème d'étoiles pour graphes est NP-complèt
• Reconstructing a Graph from its Neighborhood Lists
• Neighborhood hypergraphs of bipartite graphs
• Enumeration of bipartite self-complementary graphs