C-cycle Compatible Splitting Signed Graphs S(S) and Γ(S)

Rashmi Jain, Sangita Kansal, Mukti Acharya

Abstract

A \emph{signed graph} (or, in short, \emph{sigraph}) $S=(S^u,\sigma)$ consists of an underlying graph $S^u :=G=(V,E)$ and a function $\sigma:E(S^u)\longrightarrow \{+,-\}$, called the signature of $S$. A \emph{marking} of $S$ is a function $\mu:V(S)\longrightarrow \{+,-\}$. The \emph{canonical marking} of a signed graph $S$, denoted $\mu_\sigma$, is given as $$\mu_\sigma(v) := \prod_{vw\in E(S)}\sigma(vw).$$The \emph{splitting signed graph} $\mathfrak{S}(S)$ of a signed graph $S$ is formed as follows:\\Take a copy of $S$ and for each vertex $v$ of $S$, take a new vertex $v'$. Join $v'$ to all vertices $u\in N(v)$ by negative edge, if $\mu_\sigma(u)= \mu_\sigma(v) = -$ in $S$ and by positiveedge otherwise. \\ \\The \emph{splitting signed graph} $\Gamma(S)$ of a signed graph $S$ is formed as follows:\\Take a copy of $S$ and for each vertex $v$ of $S$, take a new vertex $v'$. Join $v'$ to all vertices $u\in N(v)$ and assign $\sigma(uv)$ as its sign. Here, $N(v)$ is the set of all adjacent vertices to $v$. \ \\ %A signed graph is called \emph{canonically%consistent (or $\mathcal{C}$-consistent)} if for every cycle $Z$ in $S$, the product of signs of its vertices with respect to canonical marking, is positive.if its an even number of vertices are negative with respect to its canonical markingA signed graph is called \emph{canonicallyconsistent (or $\mathcal{C}$-consistent)} if its every cycle contains even number of negative vertices with respect to its canonical marking.\ \\ A marked signed graph $S$ is called \emph{cycle-compatible} if for every cycle $Z$ in $S$, the product of signs of its vertices equals the product of signs of its edges. A signed graph $S$ is \emph{$\mathcal{C}$-cycle compatible} if for every cycle $Z$ in $S$,     $$\prod_{e\in E(Z)}\sigma(e) = \prod_{v\in V(Z)}\mu_\sigma(v).$$In this paper, we establish a structural characterization of signed graph $S$ for which  $\mathfrak{S}(S)$ and $\Gamma(S)$ are isomorphic and $\mathcal{C}$-cycle compatible.\end{abstract}

Keywords

Balanced signed graph, canonical marking, splitting signed graph, C-consistent, C-cycle compatible

Full Text:

PDF