TECHNICAL FIELD
The present disclosure is related to graph theory and its applications in solving
isomorphism problem and more specifically, to a method and system for determining the
isomorphs for a query graph from a graph dataset comprising atleast one of johnson graphs
and strongly regular graphs, in polynomial time.
BACKGROUND
A graph is a combination of vertices and edges. The edges of graphs can be directed
or undirected. For a graph, an edge connects a pair of vertices. Graphs are extremely
diverse. An example of some of the most symmetric types of the graph are johnson graph,
srg etc. Johnson graphs are a special class of undirected graphs derived from the system
of subsets. Johnson graphs comprises two variables n and k and is denoted by J(n,k) where
n represents the total number of elements of the set and k represents the size of the subset.
Two vertices are said to be connected in a johnson graph if and only if their intersection has
a size of k-1. Johnson graphs are highly symmetrical distance transitive graphs. Strongly
regular graphs are a special class of undirected graphs which are defined as follows: every
adjacent pair of vertices has λ common neighbours and every non-adjacent pair of vertices
has μ common neighbours.
FIELD OF INVENTION
Graphs are a unique way of representing information that may pertain to any
combinatorial arrangement or finite algorithmic problems. Graph theory represents the
various designing and representational aspects of many day-to-day computer based
applications. The concepts of graph theory can be incorporated in solving problems related
to transportation, electrical circuits, CAD/CAM, computer networks, chemistry, molecular
biology and computer vision etc. Each of these problems can be represented as a graph
G(V, E) where V (finite set of vertices) represents the junction point in transportation and
electrical circuit problems, nodes or routers in computer network problems, molecules in
chemistry, while E (finite set of edges) represents a direct connection between two vertices,
analogously: a road in transportation, molecular bond in chemistry, electrical wires in
electrical circuits and computer networks.
The problem of graph isomorphism is determining whether two given finite graphs are
structurally different or one is just a perturbed variant of the other. More formally, two graphs
3
are said to be isomorphic if (1) Both the graphs have same number of vertices and edges;
(2) The corresponding vertices in these two graphs have same number of degrees; and (3)
There is a bijective mapping between the vertices of one graph to the vertices of the other
graph such that the edge connectivity is maintained.
Graph isomorphism is a classical problem that has gained huge attention in the theory
of computing because of its unresolved complexity status within the polynomial/ nondeterministic
polynomial (P/NP) space. The scientific community is divided among those
who deem it “solvable in Polynomial time (P-time)” and those who do not. However, until
today, no efficient method or system for it has yet been designed or created with P-time
complexity. It is the last of the 12 problems (Graph isomorphism, Subgraph homeomorphism
{for a fixed graph H}, Graph genus, Chordal graph completion, Chromatic index, Spanning
tree parity problem, Partial order dimension, Precedence constrained 3-processor
scheduling, Linear programming, Total unimodularity, Composite number, Minimum length
triangulation) whose complexity remains unresolved.
DESCRIPTION OF RELATED ART
There are sub-classes of graphs (e.g. johnson graph) for which the identification of
isomorphs by the existing methods (in the prior art) is possible in non-deterministic
polynomial time. In the past, many groups have come up with methods to generate solutions
for the graph isomorphism.
Nauty was designed by McKay, B.D. and Piperno, A. (McKay, B.D. and Piperno, A.,
Journal of Symbolic Computation, 60 (2014)) using degree information to build a search tree
examining choices not determined by degree information iteratively; and then using graph
automorphisms, as they are found, to prune the search tree. However, this method could
not solve johnson graph and strongly regular graph isomorphism in P-time. The time
complexity of this method is O(2√(n))where n is number of vertices in the graph. This makes it
very difficult to analyse graphs bigger than a few million vertices by this method.
Prof. Laszlo Babai came up with a quasi-polynomial time solution that starts by
considering a very small set of vertices in the first graph and colouring them differently. Then
it identifies isomorphism by assuming which vertices in the second graph might correspond
to the initial set. These vertices are coloured in the same hue. The method eventually cycles
through all possible combinations. Once the graphs are coloured, the method can rule out
all matchings that pair vertices of different colours. If the method is successful, the colouring
4
process will divide the graphs into many chunks of different colours, greatly reducing the
number of possible isomorphisms the method has to consider. Babai has developed a
different way to reduce the number of possible isomorphisms, which works except in one
case: when the graph is a “Johnson graph”. These are graphs that have so much symmetry
that the colouring process and Babai’s further refinements fail to provide enough information
to guide the method (Babai L. 2015, arXiv:1512.03547).
Thus, a method for solving the johnson graph and strongly regular graph isomorphism
in P-time would shift the nature of graph isomorphism from NP towards P-time and is
required. The present disclosure describes a method and system for solving graph
isomorphism for johnson graphs and strongly regular graphs in P-time.
OBJECT OF INVENTION
It has already been proposed that there are sub-classes of graphs for which the
identification of isomorphs by the existing methods (in the prior art) is possible in nondeterministic
polynomial time. In the past, many groups have come up with methods to
generate solutions for the graph isomorphism, however, these methods could not solve
johnson graph and strongly regular graph isomorphism within polynomial time. Thus, a
method for solving the johnson graph and strongly regular graph isomorphism in P-time
would shift the nature of graph isomorphism from non-deterministic polynomial time towards
polynomial time and is required. The principal object of this invention is to solve the graph
isomorphism for johnson and strongly regular graphs in polynomial time.
SUMMARY
The shortcomings in the field of isomorphism with respect to johnson and strongly
regular graphs are overcome and additional advantages are provided through the present
disclosure. Additional features and advantages are realized through the techniques of the
present disclosure. Other embodiments and aspects of the disclosure are described in detail
herein and are considered a part of the present disclosure.
The present disclosure provides a method for determination of graph isomorphism
for johnson graphs and strongly regular graphs. The process iterates over each member of
the graph dataset. It starts by taking two graphs: the query graph and a member of the graph
dataset. The first step in this process is to identify the number of vertices in the query graph
and compare with the vertices of the other graph. If the number of vertices in both the graphs
5
are equal then the number of edges of both the graphs are compared with each other. If
both the graphs have same number of edges then the girth of each graph is calculated by
taking a vertex (the vertices taken into consideration are maintained in a visited-list to keep
a track of the vertices being already visited) and exploring its directly connected vertices
(neighbours). The list of neighbours are stored in a stack (i.e. last in-first out order), called
neighbour-list. The penultimate vertex (i.e. the vertex visited before the current vertex) is
omitted from the stack. The next vertex to be considered is taken from the neighbour-list of
the current vertex and its neighbour-list is updated in the same manner. This process is
repeated recursively until there are one or more vertex/vertices common in the neighbourlist
and the visited-list. This implies that the path traversed has identified a cyclical structure.
The length of this cyclical structure is equal to the number of intermediate edges traversed
while moving from the first incidence to the last incidence of the common vertex and is stored
as the current girth of the graph. This process progresses until all the vertices of the graph
are covered. During this process, the calculated length for every such cyclical structure is
compared with the one stored and whichever is minimum is stored as the current girth. After
all the vertices are covered, the girth stored is considered as the girth of the graph. If the
girth for both the graphs are equal, an exhaustive calculation of the participation number for
each vertex in primary and secondary cyclical shapes are performed (wherein, the primary
cyclical shapes are the vertices connected in closed chain, whose length is equal to the
girth, includes overlapping primary cyclical shapes and secondary cyclical shapes are the
vertices connected in closed chain, whose length is atleast one more than the length of the
primary cyclical shapes, such that there is no primary cyclical shape completely
encompassed within it and includes overlapping secondary cyclical shapes). The primary
participation number for a vertex is the number of primary cyclical shapes in which it is a
part and similarly secondary participation number for a vertex is the number of secondary
cyclical shapes in which it is a part. The traversed paths during the identification of the
primary and secondary cyclical shapes are stored. In case of johnson graph, the primary
participation number itself distinguishes it from other non-isomorphic forms. In case of
strongly regular graphs, if the participation numbers (both primary and secondary) for each
vertex are same for both the graphs then the graphs are isomorphic. During this entire
procedure, if at any point of time, the comparisons among different parameters (the number
of vertices, the number of edges, girth, primary participation numbers and secondary
participation numbers) between the graphs differ then the graphs are classified as not
isomorphic and that member of the graph dataset is eliminated. When both the graphs are
declared isomorphic by the current disclosure, then the last step would be to give a one-to6
one correspondence of each vertex of the query graph to its isomorphic form (from the
member of the graph dataset). In case of strongly regular graphs, the variation in case of
scs will determine the origination of labelling of the vertices. As johnson graphs are highly
symmetrical graphs it is impossible to distinguish any vertex from one another in case of
isomorphs. Hence, each vertex of the query graph corresponds to every vertex of its
isomorphic form (from the member of the graph dataset). Labelling is done by taking a vertex
from both the graphs and applying a traversal approach for exploring other vertices
according to their neighbour-list. These vertices are then labelled accordingly.
The present disclosure provides a system for identifying isomorphs for johnson
graphs and strongly regular graphs. The system comprises a processing unit and a memory
unit. The processing unit is configured to iterate over each member of the graph dataset. It
starts by taking two graphs: the query graph and a member of the graph dataset. The
memory unit is configured to store data associated with the plurality of vertices and edges
connecting the vertices in the graph. The processing unit is then configured to perform a
comparison between the number of vertices in each graph. If the number of vertices are
equal then the comparison between the number of edges for both the graphs are performed
by the processing unit. If the number of edges are also equal then the processing unit is
configured to calculate the girth of the graphs. The girth is initialized by the processing unit
as one more than the number of vertices in the graph. The processing unit is configured to
calculate the girth by taking a vertex (the vertices taken into consideration are maintained in
a visited-list, by the memory unit, to keep a track of the vertices being already visited) and
exploring its directly connected vertices (neighbours). The memory unit is configured to store
the list of neighbours in a stack (i.e. last in-first out order), called neighbour-list. The
penultimate vertex (i.e. the vertex visited before the current vertex) is omitted from the stack.
The processing unit is configured to consider the next vertex from the neighbour-list of the
current vertex and its neighbour-list in the memory unit is updated in the same manner. This
process is repeated by the processing unit recursively until there are one or more
vertex/vertices common in the neighbour-list and the visited-list. The length of this cyclical
structure is equal to the number of intermediate edges traversed while moving from the first
incidence to the last incidence of the common vertex and is stored by the processing unit as
the current girth of the graph in the memory unit. This process progresses until all the
vertices of the graph are covered by the processing unit. During this process, the calculated
length for every such cyclical structure is compared with the one stored and whichever is
minimum is stored as the current girth. After all the vertices are covered, the girth stored in
7
the memory unit is the girth of the graph. If the girth for both the graphs are equal, an
exhaustive calculation of the participation number for each vertex in primary and secondary
cyclical shapes are then performed by the processing unit (wherein, the primary cyclical
shapes are the vertices connected in closed chain, whose length is equal to the girth,
includes overlapping primary cyclical shapes and secondary cyclical shapes are the vertices
connected in closed chain, whose length is atleast one more than the length of the primary
cyclical shapes, such that there is no primary cyclical shape completely encompassed within
it and includes overlapping secondary cyclical shapes). The primary participation number
for a vertex is calculated by the processing unit as the number of primary cyclical shapes in
which it is a part and similarly secondary participation number for a vertex is calculated by
the processing unit as the number of secondary cyclical shapes in which it is a part. The
traversed paths during the identification of the primary and secondary cyclical shapes are
stored in the memory unit. In case of johnson graph, the primary participation number itself
distinguishes it from other non-isomorphic forms. In case of strongly regular graphs, if the
participation numbers (both primary and secondary) for each vertex are same for both the
graphs then the graphs are classified as isomorphic by the system. During this entire
procedure, if at any point of time, the comparisons among different parameters by the
processing unit (the number of vertices, number of edges, girth, primary participation
numbers and secondary participation numbers) between the graphs differ, then the graphs
are classified as not isomorphic and that member of the graph dataset is eliminated.
When both the graphs are declared isomorphic by the current disclosure, then the
last step would be to give a one-to-one correspondence of each vertex of the query graph
to its isomorphic form (from the member of the graph dataset) by the processing unit. In
case of strongly regular graphs, the variation in case of scs will determine the origination of
labelling of the vertices. As johnson graphs are highly symmetrical graphs it is impossible to
distinguish any vertex from one another in case of isomorphs. Hence, each vertex of the
query graph corresponds to every vertex of its isomorphic form (from the member of the
graph dataset). Labelling is done by the processing unit by taking a vertex from both the
graphs and applying a traversal approach for exploring other vertices according to their
neighbour-list. These vertices are then labelled accordingly and stored in the memory unit.
The foregoing summary is illustrative only and is not intended to be limiting in any
way. In addition to the illustrative aspects and features described above, further aspects,
and features will become apparent by reference to the drawings and the following detailed
description.
8
BRIEF DESCRIPTION OF THE DRAWINGS
The novel features and characteristics of the disclosure are set forth in the appended
claims. The embodiments of the disclosure itself, however, as well as a preferred mode of
use, further objectives and advantages thereof, will best be understood by reference to the
following detailed description of an illustrative embodiment when read in conjunction with
the accompanying drawings. One or more embodiments are now described, by way of
example only, with reference to the accompanying drawings.
Figure 1 illustrates a system for identifying isomorphs for johnson graphs and
strongly regular graphs in accordance with an embodiment of the present disclosure;
Figure 2a and 2b show two graphs which are isomorphic to each other in accordance
with the present disclosure;
Figure 3 shows a graph which is johnson J(4,2) with n=4 and k=2 and also strongly
regular SRG(6,4,2,4) with λ=2 and μ=4 with an exemplary embodiment of the present
disclosure;
Figure 4-7 illustrates primary cyclical shapes (pcs) involving vertex 1 in graph (J(4,2)
/ SRG(6,4,2,4)) in accordance with the present disclosure;
Figure 8-9 depicts secondary cyclical shapes (scs) involving vertex 1 in graph (J(4,2)
/ SRG(6,4,2,4)) in accordance with the present disclosure; and
Figure 10-11 illustrates cyclical shapes which encompass two primary cyclical
shapes (pcs) in graph (J(4,2) / SRG(6,4,2,4)) in accordance with the present disclosure.
The figures depict embodiments of the disclosure for the purpose of illustration only.
One familiar with the art would readily undertand from the detailed description that
alternative embodiments of the structures and methods illustrated herein may be employed
without departing from the principles of the disclosure described herein.
9
DETAILED DESCRIPTION
The foregoing has broadly outlined the features and technical advantages of the
present disclosure in order that the detailed description of the disclosure that follows may
be better understood. Additional features and advantages of the disclosure will be described
hereinafter which form the subject of the claims of the disclosure. It should be appreciated
by those skilled in the art that the conception and specific aspect disclosed may be readily
utilized as a basis for modifying or designing other structures for carrying out the same
purposes of the present disclosure. It should be also realised by those skilled in the art that
such equivalent constructions do not depart from the spirit, scope and principles of the
disclosure as set forth in the appended claims.
The present disclosure is related to a method and system for identification of
isomorphs among johnson graphs and strongly regular graphs in polynomial time. A set of
two graphs are considered for this purpose where graph G1 consists of V1 number of vertices
and E1 number of edges and graph G2 consists of V2 number of vertices and E2 number of
edges with each edge connecting two vertices. Two graphs are said to be isomorphic to
each other if there is a bijective function for one-to-one and onto mapping. In this disclosure,
graphs are considered to be undirected, non-labelled and unweighted. However, the notion
of isomorphism may be applied to all other variants of graph, by appending the prerequisite
to preserve the corresponding additional elements of structure.
Determining whether two graphs, out of which atleast one must be a johnson graph
and strongly regular, is highly complex and there are no existing techniques which solve this
anywhere close to polynomial time. The best existing solution for solving strongly regular
graph isomorphism is quasi-polynomial. On the other hand, the best existing solution for
solving johnson graph isomorphism was given by Nauty with exponential running time
complexity. The complexity of the present disclosure is dependent upon the calculation of
primary cyclical shapes (pcs) and secondary cyclical shapes (scs). The length of pcs is the
girth (g). The time required to calculate the girth in worst-case is linear. In the present
disclosure, the length of pcs is bounded between 3 to 5. In the present disclosure, the length
of scs is bounded from 4 to 6 (since scs is atleast one more than the length of pcs). When
the length of scs is greater than “one more than the length of pcs”, in terms of the
participation numbers, the results are redundant. Hence, the run-time complexity is O(n6),
where n represents the number of vertices of the graph, which is P-time.
The procedure followed for carrying out the johnson graph and strongly regular graph
10
isomorphism test is as follows: Two graphs are taken wherein one is a query graph (G1) and
the other is a member of the graph dataset (G2). The graph dataset consists of atleast one
of johnson graphs and strongly regular graphs. The process iterates over each member of
the graph dataset. The first process proceeds by determining the number of vertices of both
the graphs G1 and G2 and comparing with each other. If the number of vertices are equal
then the number of edges for both the graphs are deduced and a comparison is made
whether both the graphs have equal number of edges. An edge of a graph is defined as the
direct connection between vertices. If the number of edges of both the graphs G1 and G2 are
equal then the girth of both the graphs are calculated. Girth of a graph is defined as the
length of the shortest cycle contained in the graph. Girth of each graph is calculated by
taking a vertex (the vertices taken into consideration are maintained in a visited-list to keep
a track of the vertices being already visited) and exploring its directly connected vertices
(neighbours). The list of neighbours are stored in a stack (i.e. last in-first out order), called
neighbour-list. The penultimate vertex (i.e. the vertex visited before the current vertex) is
omitted from the stack. The next vertex to be considered is taken from the neighbour-list of
the current vertex and its neighbour-list is updated in the same manner. This process is
repeated recursively until there are one or more vertex/vertices common in neighbour-list
and visited-list. This implies that the path traversed has identified a cyclical structure. The
length of this cyclical structure is equal to the number of intermediate edges traversed while
moving from the first incidence to the last incidence of the common vertex and is stored as
the current girth of the graph. This process progresses until all the vertices of the graph are
covered. During this process, the calculated length for every such cyclical structure is
compared with the one stored and whichever is minimum is stored as the current girth. After
all the vertices are covered, the girth stored is considered as the girth of the graph.
If the girth for both the graphs G1 and G2 are equal then the primary participation
number of each vertex in the formation of entire set of primary cyclical shapes (pcs) of which
it is a part, is calculated and stored. This is calculated to gain the knowledge of the
organization of the graph. The arrangement of cycles in a graph constitutes the entire
organization of the graph in symmetrical graphs. Primary cyclical shapes are the minimum
circular arrangement of vertices connected by edges. Its length is equal to the girth of the
graph and includes overlapping primary cyclical shapes. The traversed paths during the
identification of the primary cyclical shapes are stored. If two graphs are isomorphic then the
arrangement of the shortest cycles in the graphs must also be the same. Hence, the
participation number of each vertex in the formation of pcs should be the same. In case of
11
johnson graph, the primary participation number itself distinguishes it from other nonisomorphic
forms. In case of strongly regular graphs, if the primary participation numbers
stored in G1 correspond to G2 then the participation number of each vertex in the formation
of secondary cyclical shapes (scs) are calculated. Secondary cyclical shapes are vertices
connected in closed chain, whose length is atleast one more than the primary cyclical
shapes, such that there is no primary cyclical shape completely encompassed within it and
includes overlapping secondary cyclical shapes. The complete set of pcs is identified prior
to scs demarcation. A cyclical shape would be considered as scs if and only if it satisfies the
following conditions:
1. The length of the cyclical shape should be atleast equal to g+1 (where g stands for the
girth of the graph).
2. The cyclical shape should not encompass any of the pcs.
The method for calculation of scs is similar to the method used for the calculation of pcs.
The traversed paths during the identification of the scs are stored. If the participation
numbers of scs for each vertex are same for both the graphs then the graphs are classified
as isomorphic.
During this entire procedure, if at any point of time, the comparisons among different
parameters (the number of vertices, number of edges, girth, primary participation numbers
and secondary participation numbers) between the graphs differ, then the graphs are
classified as not isomorphic and that member of the graph dataset is eliminated.
When G1 and G2 are declared isomorphic by the current disclosure, then the last step
would be to give a one-to-one correspondence of each vertex of G1 to G2. In case of strongly
regular graphs, the variation in case of scs will determine the origination of labelling of the
vertices. As johnson graphs are highly symmetrical graphs it is impossible to distinguish any
vertex from one another in case of isomorphs. Hence, each vertex of G1 corresponds to
every vertex of G2. Labelling is done by taking a vertex from both the graphs and applying
a traversal approach for exploring other vertices according to their neighbour-list. These
vertices are then labelled accordingly.
Figure 1 illustrates a system 100 for identifying isomorphs among johnson graphs
and strongly regular graphs in accordance with an embodiment of the present disclosure.
The system comprises a processing unit 103 and a memory unit 105. The memory unit 105
is configured to store data associated with the plurality of vertices and edges connecting the
vertices in the graph. The processing unit 103 is then configured to perform a comparison
12
between the number of vertices in each graph. If the number of vertices equal then the
comparison between the number of edges for both the graphs are performed by the
processing unit 103. If the number of edges are also equal then the processing unit 103 is
configured to calculate the girth of the graphs. The girth is initialized by the processing unit
103 as one more than the number of vertices in the graph. The processing unit 103 is
configured to calculate the girth by taking a vertex (the vertices taken into consideration are
maintained in a visited-list, by the memory unit 105, to keep a track of the vertices being
already visited) and exploring its directly connected vertices (neighbours). The memory unit
105 is configured to store the list of neighbours in a stack (i.e. last in-first out order), called
neighbour-list. The penultimate vertex (i.e. the vertex visited before the current vertex) is
omitted from the stack. The processing unit 103 is configured to consider the next vertex
from the neighbour-list of the current vertex and its neighbour-list in the memory unit 105 is
updated in the same manner. This process is repeated by the processing unit 103
recursively until there are one or more vertex/vertices common in neighbour-list and visitedlist.
The length of this cyclical structure is equal to the number of intermediate edges
traversed while moving from the first incidence to the last incidence of the common vertex
and is stored by the processing unit 103 as the current girth of the graph in the memory unit
105. This process progresses until all the vertices of the graph are covered by the processing
unit 103. During this process, the calculated length for every such cyclical structure is
compared with the one stored in the memory unit 105 and whichever is minimum is stored
as the current girth. After all the vertices are covered, the girth stored in the memory unit
105 is the girth of the graph. If the girth for both the graphs are equal, an exhaustive
calculation of the participation number for each vertex in primary and secondary cyclical
shapes are then performed by the processing unit 103 (wherein, the primary cyclical shapes
are the vertices connected in closed chain, whose length is equal to girth, includes
overlapping primary cyclical shapes and secondary cyclical shapes are the vertices
connected in closed chain, whose length is atleast one more than the primary cyclical
shapes, such that there is no primary cyclical shape completely encompassed within it and
includes overlapping secondary cyclical shapes). The primary participation number for a
vertex is calculated by the processing unit 103 as the number of primary cyclical shapes in
which it is a part and similarly secondary participation number for a vertex is calculated by
the processing unit 103 as the number of secondary cyclical shapes in which it is a part. The
traversed paths during the identification of the primary and secondary cyclical shapes are
stored in the memory unit 105. In case of johnson graph, the primary participation number
itself distinguishes it from other non-isomorphic forms. In case of strongly regular graphs, if
13
the participation numbers (both primary and secondary) for each vertex are same for both
the graphs then the graphs are classified as isomorphic by the system 100. When both the
graphs are declared isomorphic by the current disclosure, then the last step would be to give
a one-to-one correspondence of each vertex of the query graph to its isomorphic form (from
the member of the graph dataset) by the processing unit 103. In case of strongly regular
graphs, the variation in case of scs will determine the origination of labelling of the vertices.
As johnson graphs are highly symmetrical graphs it is impossible to distinguish any vertex
from one another in case of isomorphs. Hence, each vertex of the query graph corresponds
to every vertex of its isomorphic form (from the member of the graph dataset). Labelling is
done by the processing unit 103 by taking a vertex from both the graphs and applying a
traversal approach for exploring other vertices according to their neighbour-list. These
vertices are then labelled accordingly and stored in the memory unit 105. During this entire
procedure, if at any point of time, the comparisons among different parameters (the number
of vertices, number of edges, girth, primary participation numbers and secondary
participation numbers) between the graphs differ, then the graphs are classified as not
isomorphic by the processing unit 103 and that member of the graph dataset is eliminated.
Figure 2 depicts two simple graphs with 5 vertices and 5 edges. Figure 2a and 2b
are tested for isomorphism. As clear from the figures, both have equal number of vertices
and edges. If checked for correspondence, 1→a, 2→c, 3→e, 4→b, 5→d. Hence, there is a
bijective one-to-one and onto mapping for both the graphs. Therefore, by the definition of
graph isomorphism, both the graphs in Figure 2a and 2b are isomorphic to each other.
Figure 3 shows a graph (J(n,k) / SRG(v,d,λ,μ)). In the current figure, the graph is a
johnson graph where n=4 represents the total number of elements of the set and k=2
represents the size of the subset. The number of vertices possible in J(4, 2) is given by 4C2 .
Hence, the number of vertices in this graph is equal to 6. Two vertices are said to be
connected in a johnson graph if and only if their intersection has a size of k-1. In the current
figure, the graph is also a strongly regular graph where v=6, d=4, λ=2 and μ=4 represents
the number of vertices in the graph, the degrees of each vertex of the graph, the common
neighbours between every adjacent pair of vertices and the common neighbours between
every non-adjacent pair of vertices, respectively. The girth calculated for this graph is 3.
Table 1 illustrates the procedure for calculation of girth for the graph represented in Figure
3. The current girth is initialised to 7(one more than the number of vertices).
14
Current
Node Neighbour Parent Visited Unfinished Current Girth
1 2 3 5 6 - 1 2 3 5 6 7
6 1 2 4 5 1 1 6 3 2 4 5 7
5 1 3 4 6 6 1 6 5 2 1 3 4 7
4 2 3 5 6 5 1 6 5 4 1 2 3 Min(3, 7) = 3
3 1 2 4 5 4 1 6 5 4 3 2 Min(5, 3, 3) = 3
2 1 3 4 6 3 1 6 5 4 3 2 - Min(6, 3, 5, 3) = 3
Table 1: Table showing the calculation of girth of J(4,2)
Figure 4-7 depicts a graph whose pcs are marked. The total participation number of
vertex 1 in the formation of primary cyclical shapes (triangles as in this case) in the figures
are as follows: 1-2-3, 1-2-6, 1-3-5, 1-3-2, 1-5-3, 1-5-6, 1-6-2, 1-6-5, 2-1-3, 2-1-6, 2-3-1, 2-6-
1, 3-1-2, 3-1-5, 3-2-1, 3-5-1, 5-1-3, 5-1-6, 5-3-1, 5-6-1, 6-1-2, 6-1-5, 6-2-1, 6-5-1. 1-2-3, 1-
3-2, 2-1-3, 2-3-1, 3-1-2 and 3-2-1 illustrate the overlapping primary cyclical shapes. Hence,
the total participation number of vertex 1 in the formation of primary cyclical shapes is equal
to 24. Likewise, the total participation number for each of the vertices is calculated and
stored. If two graphs are isomorphic then the arrangement of the shortest cycles in the
graphs must also be the same. Hence, the participation number of each vertex in the
formation of pcs should be the same. In case of johnson graph, the primary participation
number itself distinguishes it from other non-isomorphic forms.
Figure 8-9 depicts a graph whose scs are marked. The total participation number of
vertex 1 in the formation of secondary cyclical shapes (quadrilateral as in this case) in the
figures are as follows: 1-2-4-5, 1-3-4-6, 2-1-5-4, 3-1-6-4, 4-2-1-5, 4-3-1-6, 5-4-2-1, 6-4-2-1,
2-4-5-1, 3-4-6-1, 4-5-1-2, 4-6-1-3, 5-1-2-4, 6-1-3-4, 1-5-4-2, 1-6-4-3. 1-2-4-5, 2-1-5-4, 4-2-
1-5, 5-4-2-1, 2-4-5-1, 4-5-1-2, 5-1-2-4 and 1-5-4-2 illustrate the overlapping secondary
cyclical shapes. Hence, the total participation number of vertex 1 in the formation of
secondary cyclical shapes is equal to 16. Likewise, the total participation number for each
of the vertices is calculated and stored. If two graphs are isomorphic then the arrangement
of the secondary cyclical shapes in the graphs must also be the same. Hence, the
participation number of each vertex in the formation of scs should also be same.
Figure 10-11 depict cyclical shapes which encompass two primary cyclical shapes
(pcs). From Figure 10, it is clear that 1-2-4-6 cannot be termed as secondary cyclical shape
15
because it encompasses two primary cyclical shapes (1-2-6 and 2-4-6). Figure 11 also
shows a cyclical shape 1-3-5-6 encompassing two primary cyclical shapes (1-5-6 and 1-3-
5). Hence, this cyclical shape also cannot be considered to be a secondary cyclical shape.
Referral Numberals:
Reference Number Description
100 System
103 Processing Unit
105 Memory Unit

CLAIMS
We claim:
1. A method for identification of isomorphs for a query graph from a graph dataset in
polynomial time; comprising:
determining the number of vertices of the query graph and the members of the graph
dataset;
comparing the number of vertices of the query graph with that of the members of the
graph dataset;
eliminating those graphs from the graph dataset which have different number of
vertices from the query graph;
determining the number of edges of the query graph and the members of the graph
dataset;
comparing the number of edges of the query graph with that of the members of the
graph dataset;
eliminating those graphs from the graph dataset which have different number of
edges from the query graph;
calculating the girths for the query graph and the members of the graph dataset;
comparing the girth of the query graph with that of the members of the graph dataset;
eliminating those graphs from the graph dataset which have different girths from the
query graph;
identifying a primary participation number for each vertex, in the query graph and for
every member of the graph dataset;
identifying a secondary participation number for each vertex in the query graph and
17
for every member of the graph dataset;
labelling the vertices of the query graph and members of the graph dataset;
identifying the vertex correspondence between the query graph and for every
member of the graph dataset; and
obtaining the isomorphs for the query graph by eliminating those graphs from the
graph dataset which have non-equivalent vertex correspondence.
2. The method as claimed in claim 1, wherein the query graph must be atleast one of:
johnson graph and strongly regular graph.
3. The method as claimed in claim 1, wherein the graph dataset comprises atleast one of:
johnson graph and strongly regular graph.
4. The method as claimed in claim 1, wherein the primary participation number for a vertex
is obtained upon calculating all primary cyclical shapes in which it is participating, includes
overlapping primary cyclical shapes.
5. The method as claimed in claim 1, wherein secondary participation number for a vertex
is obtained upon calculating all secondary cyclical shapes of length atleast one more than
the girth of the graph in which it is participating, includes overlapping secondary cyclical
shapes, excludes those secondary cyclical shapes which encompass any primary cyclical
shape(s).
6. The method as claimed in claim 1, wherein the vertices are labelled by their respective
primary and secondary participation numbers.
7. The method as claimed in claim 1, wherein the vertex correspondence is identified by
comparing the labels of vertices.
8. A system for identification of isomorphs for a query graph from a graph dataset in
polynomial time; comprising:
18
a memory unit configured to store data associated with plurality of vertices and edges
connecting the plurality of vertices in the query graph; and
a processing unit communicatively connected to the memory unit to obtain the data
associated with plurality of vertices and edges connecting the plurality of vertices in the
query graph, the processing unit being capable of:
determining the number of vertices of the query graph and the members of
the graph dataset;
comparing the number of vertices of the query graph with that of the
members of the graph dataset;
eliminating those graphs from the graph dataset which have different number
of vertices from the query graph;
determining the number of edges of the query graph and the members of the
graph dataset;
comparing the number of edges of the query graph with that of the members
of the graph dataset;
eliminating those graphs from the graph dataset which have different number
of edges from the query graph;
calculating the girths for the query graph and the members of the graph
dataset;
comparing the girth of the query graph with that of the members of the graph
dataset;
eliminating those graphs from the graph dataset which have different girths
from the query graph;
identifying a primary participation number for each vertex, in the query graph
19
and for every member of the graph dataset;
identifying a secondary participation number for each vertex in the query
graph and for every member of the graph dataset;
labelling the vertices of the query graph and members of the graph dataset;
identifying the vertex correspondence between the query graph and for every
member of the graph dataset; and
obtaining the isomorphs for the query graph by eliminating those graphs from
the graph dataset which have non-equivalent vertex correspondence.
9. The system as claimed in claim 8, wherein the query graph must be atleast one of:
johnson graph and strongly regular graph.
10. The system as claimed in claim 8, wherein the graph dataset comprises atleast one of:
johnson graph and strongly regular graph.
11. The system as claimed in claim 8, wherein the processing unit obtains the primary
participation number for a vertex is by calculating all primary cyclical shapes in which it is
participating, includes overlapping primary cyclical shapes and stores these in the memory
unit.
12. The system as claimed in claim 8, wherein the processing unit obtains the secondary
participation number for a vertex by calculating all secondary cyclical shapes of length
atleast one more than the girth of the graph in which it is participating, includes overlapping
secondary cyclical shapes, excludes those secondary cyclical shapes which encompass
any primary cyclical shape(s) and stores these in the memory unit.
13. The system as claimed in claim 8, wherein the processing unit labels the vertices by
their respective primary and secondary participation numbers and stores them in the
memory unit.
14. The system as claimed in claim 8, wherein the processing unit identifies the vertex
correspondence by comparing the labels of vertices and stores them in the memory unit.