A study on certain bounds of the rna number and some characterizations of the parity signed graphs

Abstract

For a given graph $G$, let $f:V(G)\to \{1,2,\dots ,n\}$ be a bijective mapping. For a given edge $uv\in E(G)$, $\sigma (uv)=+$, if $f(u)$ and $f(v)$ have the same parity and $\sigma (uv)=-$, if $f(u)$ and $f(v)$ have opposite parity. The resultant signed graph is called a parity signed graph and the mapping $\sigma$ is called a parity signature of $G$. Let us denote a parity signed graph $S=(G,\sigma )$ by $G_{\sigma }$. Let $E^{-}(G_{\sigma })$ be a set of negative edges in a parity signed graph and let $Si(G)$ be the set of all parity signatures for the underlying graph $G$. We define the \textit{rna} number of $G$ as ${\sigma }^{-}(G)=\min \{|E^{-}(G_{\sigma })|:\sigma \in Si(G)\}$. In this paper, we prove a non-trivial upper bound in the case of trees: ${\sigma }^{-}(T)\le \lceil \frac{n}{2}\rceil$, where $T$ is a tree of order $n+1$. We have found families of trees whose \textit{rna} numbers are bounded above by $\lceil \frac{\Delta }{2}\rceil$ and also we have shown that for any $i\le \lceil \frac{n}{2}\rceil$, there exists a tree $T$ (of order $n+1$) with ${\sigma }^{-}(T)=i$. This paper gives a characterization of graphs with \textit{rna} number 1 in terms of its spanning trees and also a characterization of graphs with \textit{rna} number 2.

12 pages