RNA Number of Some Parity Signed Generalized Petersen Graphs

MaRDI QIDQ6379641zbMATH OpenFDO

Authors Deepak Sehrawat, Bikash Bhattacharjya

Publication date 7 October 2021

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Connectivity (05C40) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A signed graph $Sigma=(G,sigma)$ is said to be parity signed if there exists a bijection $f:V(G)ightarrow1,2,\mathrm{...},|V(G)|$ such that $sigma(uv)=+$ if and only if $f(u)$ and $f(v)$ are of same parity, where $uv$ is an edge of $G$. The rna number of a graph $G$, denoted $sigm{a}^{-}(G)$, is the minimum number of negative edges among all possible parity signed graphs over $G$. The rna number is also equal to the minimum cut size that has nearly equal sides. In this paper, for generalized Petersen graph $P(n,k)$, we prove that $3leqsigm{a}^{-}(P(n,k))leqn$ and these bounds are sharp. The exact value of $sigm{a}^{-}(P(n,k))$ is determined for $k=1,2$. Some famous generalized Petersen graphs namely, Petersen graph $P(5,2)$, Durer graph $P(6,2)$, Mobius-Kantor graph $P(8,3)$, Dodecahedron $P(10,2)$, Desargues graph $P(10,3)$ and Nauru graph $P(12,5)$ are also treated. We show that the minimum order of a $(4n-1)$-regular graph having rna number one is bounded above by $12n-2$. The sharpness of this upper bound is also shown for $n=1$. We also show that the minimum order of a $(4n+1)$-regular graph having rna number one is $8n+6$. Finally, for any simple connected graph of order $n$, we propose an $O(2^n+n^{lfloorfracn2floor})$ time algorithm for computing its rna number.

This page was built for publication: RNA Number of Some Parity Signed Generalized Petersen Graphs

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