✦ LIBER ✦

Focality and graph isomorphism

✍ Scribed by W. Imrich; G. Sabidussi

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 592 KB
Volume: 81
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90063-n

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is focal if the stabiliser of every vertex x fixes exactly one edge not incident with x. It is shown that the problem of testing whether a connected bipartite graph is focal has the same complexity as the graph isomorphism problem.

Several other similar questions are also considered.

📜 SIMILAR VOLUMES

Graph algebras and the graph isomorphism

Graph algebras and the graph isomorphism problem

✍ I. N. Ponomarenko 📂 Article 📅 1994 🏛 Springer 🌐 English ⚖ 525 KB

Graph isomorphism, general remarks

✍ Gary L. Miller 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 927 KB

The graph isomorphism problem

✍ X. Liu; D. J. Klein 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 598 KB

A chemically and graph-theoretically relevant problem is that of determining whether a pair of graphs G and G' are isomorphic. A two-stage computational test is developed. In the first stage an "eigenvalue-eigenprojector" tabular graph-theoretic invariant is computed, whence if the two tables differ

Reductions to Graph Isomorphism

✍ Jacobo Torán 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 382 KB

Hadamard equivalence via graph isomorphi

Hadamard equivalence via graph isomorphism

✍ Brendan D. McKay 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 180 KB

Two ~1 x n matrices with f I entries are H rdamard equivalent if one may be obtained from the other by a sequence of operations involvir g independent row and column permutations and multiplications of rows or columns by -1. We solve the computational problem of recognising Hadamard equivalence by r

Completeness results for graph isomorphi

Completeness results for graph isomorphism

✍ Birgit Jenner; Johannes Köbler; Pierre McKenzie; Jacobo Torán 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 239 KB

We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC 2 . In particular we show that tree isomorphism, when trees are encoded as strings, is NC 1 -hard under AC 0 -reductio