A study on parity signed graphs: the $rna$ number

DOI10.1016/J.AMC.2022.127322arXiv2111.04956MaRDI QIDQ6382553

X. Y. Chen, Ligang Jin, Yingli Kang

Publication date: 8 November 2021

Abstract: The study on parity signed graphs was initiated by Acharya and Kureethara very recently and then followed by Zaslavsky etc.. Let $(G,sigma)$ be a signed graph on $n$ vertices. If $(G,sigma)$ is switch-equivalent to $(G,+)$ at a set of $lfloorfracn2floor$ many vertices, then we call $(G,sigma)$ a parity signed graph and $sigma$ a parity-signature. $Sigm{a}^{-}(G)$ is defined as the set of the number of negative edges of $(G,sigma)$ over all possible parity-signatures $sigma$. The $rna$ number $sigm{a}^{-}(G)$ of $G$ is given by $sigm{a}^{-}(G)=minSigm{a}^{-}(G)$. In other words, $sigm{a}^{-}(G)$ is the smallest cut size that has nearly equal sides. In this paper, all graphs considered are finite, simple and connected. We apply switch method to the characterization of parity signed graphs and the study on the $rna$ number. We prove that: for any graph $G$, $Sigm{a}^{-}(G)=leftsigm{a}^{-}(G)ight$ if and only if $G$ is $K_{1,n-1}$ with $n$ even or $K_n$. This confirms a conjecture proposed in [M. Acharya and J.V. Kureethara. Parity labeling in signed graphs. J. Prime Res. Math., to appear. arXiv:2012.07737]. Moreover, we prove a nontrivial upper bound for the $rna$ number: for any graph $G$ on $m$ edges and $n$ ($ngeq4$) vertices, $sigm{a}^{-}(G)leqlfloorfracm2+fracn4floor$. We show that $K_n$, $K_n-e$ and $K_n-riangle$ are the only three graphs reaching this bound. This is the first upper bound for the $rna$ number so far. Finally, we prove that: for any graph $G$, $sigm{a}^{-}(G)+sigm{a}^{-}(overlineG)leqsigm{a}^{-}(GcupoverlineG)$, where $overlineG$ is the complement of $G$. This solves a problem proposed in [M. Acharya, J.V. Kureethara and T. Zaslavsky. Characterizations of some parity signed graphs. 2020, arXiv:2006.03584v3].

Mathematics Subject Classification ID

Perfect graphs (05C17) Signed and weighted graphs (05C22)

This page was built for publication: A study on parity signed graphs: the $rna$ number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382553)