Neighborhood hypergraphs of bipartite graphs

DOI10.1002/jgt.20293zbMath1167.05041OpenAlexW4248711660MaRDI QIDQ5387058

Endre Boros, Vladimir A. Gurvich, Igor Edm. Zverovich

Publication date: 14 May 2008

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

Full work available at URL: https://doi.org/10.1002/jgt.20293

zbMATH Keywords

computational complexitysymmetrizabilitymatrix transpositiongraph isomorphism probleminvolutory automorphismsmatrix symmetrizationneighborhood hypergraphstransposability semi-induced matchings in bigraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

On the complexity of reconstructing H-free graphs from their Star Systems ⋮ Completion and decomposition of hypergraphs into dominating sets of graphs ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Graphs whose Kronecker covers are bipartite Kneser graphs ⋮ Neighborhood inclusion posets and tree representations for chordal and dually chordal graphs ⋮ Uniform clutters and dominating sets of graphs ⋮ Neighborhood complexes and Kronecker double coverings ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ Neighborhood hypergraphs of digraphs and some matrix permutation problems ⋮ Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism ⋮ On the Complexity of Reconstructing H-free Graphs from Their Star Systems

Cites Work

• Group-theoretic algorithms and graph isomorphism
• A V log V algorithm for isomorphism of triconnected planar graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item