35
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

On complete systems of invariants for small graphs

&
Pages 35-46 | Received 11 Mar 1996, Published online: 20 Jan 2011
 

Abstract

We define a small graph to be one with n ≤ 6 nodes. The celebrated Graph Isomorphism Problem (GIP) consists in deciding whether or not two given graphs are isomorphic, i.e., whether there is a bijective mapping from the nodes of one graph onto those of the other such that adjacency is preserved. An interesting algorithmic approach to graph isomorphism problem uses the “code” (sometimes called a complete system of invariants). Following this approach, two graphs are isomorphic if and only if they have the same code. We propose several complete sets of invariants to settle the GIP for small graphs. Note that no complete system of invariants for a graph is known, except for those that are equivalent to the entire adjacency matrix or list of adjacencies.

C.R.Categories:

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.