Premium
Initial vertex partitioning and testing isomorphism of graphs and digraphs
Author(s) -
Bhat Kabekode V. S.,
Rahnavard M. H.
Publication year - 1981
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.4490090108
Subject(s) - digraph , graph isomorphism , combinatorics , vertex (graph theory) , isomorphism (crystallography) , mathematics , discrete mathematics , computer science , graph , line graph , chemistry , crystal structure , crystallography
In this paper, we present a new method for initial vertex partitioning of graphs (digraphs) using the notion of a vertex label that includes several parameters of the graph for each vertex of the graph (digraph). Our method provides a more refined initial vertex partitioning for graphs (digraphs) than any of the known methods in O( n E ) time for a graph with n vertices and E edges. Several examples are given as illustrations of the method. A computational comparison of our method with the Schmidt‐Druffel algorithm is presented. The method can be coupled with any existing good back‐tracking method for testing isomorphism of graphs and digraphs.