(A) Study of Some Parameters in Signed Graphs

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
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.
Supervisor: Bhattacharjya, Bikash