(A) Study of Some Parameters in Signed Graphs
No Thumbnail Available
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Supervisor: Bhattacharjya, Bikash
Keywords
MATHEMATICS