Focality and graph isomorphism

DOI10.1016/0012-365X(90)90063-NMaRDI QIDQ913826zbMATH OpenFDO

Authors Wilfried Imrich, G. Sabidussi

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(90)90063-N

zbMATH Keywords

connected bipartite graphfocal graphsgraph isomorphism problem

Mathematics Subject Classification ID

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

Review text

A graph is focal if the stabiliser of every vertex x fixed 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.

Recommendations

• scientific article; zbMATH DE number 4043868
• scientific article; zbMATH DE number 3815
• scientific article; zbMATH DE number 3841910
• scientific article; zbMATH DE number 4156494
• The isomorphism problem for classes of graphs closed under contraction

Cites work

• Combinatorics 79. Part II
• scientific article; zbMATH DE number 4043868 (Why is no real title available?)
• The graph isomorphism disease
• Über das lexikographische Produkt von Graphen

Cited in

(1)

• scientific article; zbMATH DE number 4043868 (Why is no real title available?)

This page was built for publication: Focality and graph isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q913826)