Majority Logic Synthesis Based on Nauty Algorithm - Field-Coupled Nanocomputing: Paradigms, Progress, and Perspectives - page 113

Fig. 6. A graphical representation for graph G

A graph F is considered a subgraph of a graph G if V(F) (V(G), E(F) (E(G) and
W F is under restriction of W G . Such a graph F is contained by G and denoted as
F(G. There are two ways of obtaining a subgraph from a graph G. One is to delete
the vertices as well as the edges linked to them. The other one is to delete the edges as
well as vertices attached to them. In this work, the former method is used. For
example, by deleting the vertices x and z from V(G) and updating E(G) and W G
correspondingly, V(F), E(F) and W F are obtained as shown in Eq. ( 5 ) and E(F) a
graphical representation is shown in Fig. 7 . It can be seen from what has been dis-
cussed that a subgraph is a partition of a graph.

)

f g ; E ðÞ¼ a ; d ; f g
W G ðÞ¼ w f ; W G ðÞ¼ u fg ; W G ðÞ¼ v fg

V ðÞ¼ u ; v ; w ; y

ð 5 Þ

2.5 Graph Isomorphism and Nauty Algorithm

Two different graphs that have essentially the same structure are isomorphic to each
other. In other words, these two graphs are not distinguishable from one another in
terms of the number of nodes and their edge connectivity. A more precise definition is:
for two graphs G and H, if there are bijections h: V(G) ? V(H) and u: E(G) ? E(H)
so that W G (e) = uv if and only if W H (u (e)) = h (u) h (v), G and H are isomorphic
[ 18 ]. Consider two graphs G and H as shown in Fig. 8 (a) and (b). Though they look
different, with the bijections h and u shown as Eq. ( 6 ), G and H are isomorphic to
each other. According to the definitions, for example, in graph G, W G (n8) = 15?
W H (u (n8)) = h (1) h (5) ?W H (m8) = ae, which is exactly the case in graph H.All
vertices and edges can be verified in this way to show that G and H are isomorphic.
However, testing of the graph isomorphism is a formidable task. Theoretically, for
two graphs with n vertices, one needs to test all n! bijections between G and H and

Fig. 7. A graphical representation for graph F (a subgraph of graph G)