construct, one cycle, say C 3 , can be obtained from two other cycles, say C 1 and C 2
from the previous example by a symmetric cycle-plus operation È defined below:
Let an edge between vertices i and j be denoted by e ij . Let a cycle be denoted by
the set of all such edges present in the cycle. Then for any two cycles A and B, the
result of cycle-plus operation is:
A È B ¼ e ij je ij 2 A [ B; e ij 6 2 A \ B
È
É ¼ A [ B
ð
Þn A \ B
ð
Þ
The same operation can be performed computationally faster when all the edges
present in the graph are assigned a unique number and a given cycle is represented
by a bit string where bit positions from right are set “on” corresponding to the
unique numbered edges in the cycle. The cycle-plus operation is then exactly
analogous to the bit-wise XOR (^) operation, i.e. A È B , A
^ B.
At this point, it is worthwhile to note that the following property, henceforth
called Property 1, of the cycle-plus operator holds, which is proved using XOR
operation on bit string representation of cycles A and B:
A È A È B
ð
Þ,A
^ A
^ B
ð
Þ
, A
^ A
ð
Þ
^ B By associative property
, 0
^ B , B
Hence, A È A È B
ð
Þ¼B Propertyð1Þ
In terms of cycles, the result of the cycle-plus operation can either be another
cycle or a union of cycles having no common edges. Thus, all the cycles present in
the graph can be obtained by linear combination of cycles taken two at a time in the
fundamental set, supplemented successively by the increasing number of cycles and
union of cycles obtained through cycle-plus operation. In the end, the entries that
supplemented the fundamental set should only be cycles and the edge disjoint union
of cycles should be removed. The final set so obtained will be the set of all cycles,
say in the considered example the final set will be {C 1 , C 2 , C 3 } starting from the
fundamental set {C 1 , C 2 }.
It is easy to comprehend and evident from the previous example that the final set
may contain cycles smaller in size than those in the starting fundamental set of
cycles. Moreover, as the cycles are generated by linear combination over two cycles
at any given time using cycle-plus operator and as Property (1) holds, any resultant
cycle in combination with a fundamental cycle will yield the other fundamental
cycle from which it was produced. This is to say, in previous case, C 2 can be
obtained from C 1 and C 3 .
Thus, the entire fundamental set can be changed to another fundamental set
which contains only the cycles of non-decreasing number of sides starting from the
smallest sized cycle, so that all the cycles in the final set can still be generated.
Henceforth, the term fundamental set will correspond to this newly constructed set.
It can be noted, though, that the cardinality of the fundamental set does not
get altered. In the examples considered so far, this will lead to a change of
84
Md.I. H. Rizvi et al.
from the previous example by a symmetric cycle-plus operation È defined below:
Let an edge between vertices i and j be denoted by e ij . Let a cycle be denoted by
the set of all such edges present in the cycle. Then for any two cycles A and B, the
result of cycle-plus operation is:
A È B ¼ e ij je ij 2 A [ B; e ij 6 2 A \ B
È
É ¼ A [ B
ð
Þn A \ B
ð
Þ
The same operation can be performed computationally faster when all the edges
present in the graph are assigned a unique number and a given cycle is represented
by a bit string where bit positions from right are set “on” corresponding to the
unique numbered edges in the cycle. The cycle-plus operation is then exactly
analogous to the bit-wise XOR (^) operation, i.e. A È B , A
^ B.
At this point, it is worthwhile to note that the following property, henceforth
called Property 1, of the cycle-plus operator holds, which is proved using XOR
operation on bit string representation of cycles A and B:
A È A È B
ð
Þ,A
^ A
^ B
ð
Þ
, A
^ A
ð
Þ
^ B By associative property
, 0
^ B , B
Hence, A È A È B
ð
Þ¼B Propertyð1Þ
In terms of cycles, the result of the cycle-plus operation can either be another
cycle or a union of cycles having no common edges. Thus, all the cycles present in
the graph can be obtained by linear combination of cycles taken two at a time in the
fundamental set, supplemented successively by the increasing number of cycles and
union of cycles obtained through cycle-plus operation. In the end, the entries that
supplemented the fundamental set should only be cycles and the edge disjoint union
of cycles should be removed. The final set so obtained will be the set of all cycles,
say in the considered example the final set will be {C 1 , C 2 , C 3 } starting from the
fundamental set {C 1 , C 2 }.
It is easy to comprehend and evident from the previous example that the final set
may contain cycles smaller in size than those in the starting fundamental set of
cycles. Moreover, as the cycles are generated by linear combination over two cycles
at any given time using cycle-plus operator and as Property (1) holds, any resultant
cycle in combination with a fundamental cycle will yield the other fundamental
cycle from which it was produced. This is to say, in previous case, C 2 can be
obtained from C 1 and C 3 .
Thus, the entire fundamental set can be changed to another fundamental set
which contains only the cycles of non-decreasing number of sides starting from the
smallest sized cycle, so that all the cycles in the final set can still be generated.
Henceforth, the term fundamental set will correspond to this newly constructed set.
It can be noted, though, that the cardinality of the fundamental set does not
get altered. In the examples considered so far, this will lead to a change of
84
Md.I. H. Rizvi et al.