Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism

DOI10.1137/0215045MaRDI QIDQ3738557zbMATH OpenOpenAlexWikidataFDO

Authors Joan Feigenbaum, Alejandro A. Schäffer

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215045

zbMATH Keywords

composite graphgraph algorithmsgraph compositiongraph multiplication operatorgraph products

Mathematics Subject Classification ID

Graph theory (05C99) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Direct product primality testing of graphs is GI-hard
• Graph algebras and the graph isomorphism problem
• scientific article; zbMATH DE number 3815
• Recognizing some complementary products
• Exact profile values of some graph compositions

Cited in

(9)

• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Equipartitions of graphs
• Direct product primality testing of graphs is GI-hard
• On recognition of strong graph bundles
• Bounds for metric dimension and defensive k-alliance of graphs under deleted lexicographic product
• Recognizing graph products and bundles
• Finding the prime factors of strong direct product graphs in polynomial time
• Quantum chromatic number of products of quantum graphs
• Homological invariants of edge ideals of Wollastonite graphs

This page was built for publication: Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism

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