Star partitions and the graph isomorphism problem

DOI10.1080/03081089508818383zbMath0831.05043OpenAlexW2002060824MaRDI QIDQ4853929

Dragos Cvetković

Publication date: 12 February 1996

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/03081089508818383

zbMATH Keywords

strongly regular graphseigenvalueseigenspacescomplementationswitchingpolynomial timegraph decompositiongraph isomorphismeigenvalue multiplicitiesstar partitionsisomorphism testing for graphs

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

On the isomorphism of graphs having some eigenvalues of moderate multiplicity, Variable neighborhood search for extremal graphs 3

Cites Work

• Unnamed Item
• Unnamed Item
• A table of connected graphs on six vertices
• Man-machine theorem proving in graph theory
• Graph isomorphism is in the low hierarchy
• Recent results in the theory of graph spectra
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• A study of eigenspaces of graphs
• Strongly regular graphs with strongly regular decomposition
• Some recognition problems related to graph isomorphism
• On the Maximum Weight Clique Problem
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• The graph isomorphism disease
• Developments in the theory of graph spectra