Neighborhood hypergraphs of digraphs and some matrix permutation problems

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

Vladimir A. Gurvich, Igor Edm. Zverovich

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

symmetrizabilitygraph isomorphism probleminvolutory automorphismsmatrix complementationmatrix symmetrizationneighborhood dihypergraphneighborhood hypergraphs of digraphs and orgraphsskew-symmetrizability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Neighborhood hypergraphs of digraphs and some matrix permutation problems