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

Authors

  • Rashmi Jain Department of Applied Mathematics Delhi Technological University Shahbad Daulatpur main Bawana road Delhi- 110 042, India
  • Sangita Kansal
  • Mukti Acharya

Keywords:

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

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}

Downloads

Published

2015-10-28

Issue

Section

Mathematical Analysis

How to Cite

C-cycle Compatible Splitting Signed Graphs S(S) and Γ(S). (2015). European Journal of Pure and Applied Mathematics, 8(4), 469-477. https://ejpam.com/index.php/ejpam/article/view/2426

Similar Articles

1-10 of 178

You may also start an advanced similarity search for this article.