A Study of Some Parameters in Signed Graphs

Abstract

Graphs with positive or negative edges are called signed graphs. We denote a signed graph and#931; by (G, and#981;), where G is called the underlying graph of and#931; and and#981; is a function that assigns +1 or and#8722;1 to the edges of G. The set of negative edges in and#931; is known as the signature of and#931;. An unsigned graph can be realized as a signed graph in which all edges are positive. Switching and#931; 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 and#8805; 3, n and#8805; 1, where K6 is the complete graph on six vertices, Pn,k denotes the eneralized 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 and#8805; 1. We prove that the size of a minimum signature of P2n+1,1, up to switching, is at most n + 1.