Abstract:
Graphs with positive or negative edges are called signed graphs. We denote a signed
graph Σ by (G, ϕ), where G is called the underlying graph of Σ and ϕ is a function
that assigns +1 or −1 to the edges of G. The set of negative edges in Σ is known as
the signature of Σ. An unsigned graph can be realized as a signed graph in which
all edges are positive. Switching Σ by a vertex v is to change the sign of each edge
incident to v. Switching is a way of turning one signed graph into another. Two
signed graphs are called switching equivalent if one can be obtained from the other
by a sequence of switchings. Further, two signed graphs are said to be switching
isomorphic to each other if one is isomorphic to a switching of the other. In Chapter
2 of the thesis, we classify the switching non-isomorphic signed graphs arising from
K6, P3,1, P5,1, P7,1, and B(m, n) for m ≥ 3, n ≥ 1, where K6 is the complete graph
on six vertices, Pn,k denotes the generalized Petersen graph and B(m, n) denotes the
book graph consisting of n copies of the cycle Cmwith exactly one common edge. We
also count the switching non-isomorphic signatures of size two in P2n+1,1 for n ≥ 1.
We prove that the size of a minimum signature of P2n+1,1, up to switching, is at
most n + 1.