On the rna number of generalized Petersen graphs

Document Type : Original paper

Authors

Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati, India

Abstract

A signed graph $(G,\sigma)$ is called a parity signed graph if there exists a bijective mapping $f \colon V(G) \rightarrow \{1,\ldots,|V(G)|\}$ such that for each edge $uv$ in $G$, $f(u)$ and $f(v)$ have same parity if $\sigma(uv)=+1$, and opposite parity if $\sigma(uv)=-1$. The \emph{rna} number $\sigma^{-}(G)$ of $G$ is the least number of negative edges among all possible parity signed graphs over $G$. Equivalently, $\sigma^{-}(G)$ is the least size of an edge-cut of $G$ that has nearly equal sides.

In this paper, we show that for the generalized Petersen graph $P_{n,k}$, $\sigma^{-}(P_{n,k})$ lies between $3$ and $n$. Moreover, we determine the exact value of $\sigma^{-}(P_{n,k})$ for $k\in \{1,2\}$. The \emph{rna} numbers of some famous generalized Petersen graphs, namely, Petersen graph, D\" urer graph, M\" obius-Kantor graph, Dodecahedron, Desargues graph and Nauru graph are also computed. Recently, Acharya, Kureethara and Zaslavsky characterized the structure of those graphs whose \emph{rna} number is $1$. We use this characterization to show that the smallest order of a $(4n+1)$-regular graph having \emph{rna} number $1$ is $8n+6$. We also prove the smallest order of $(4n-1)$-regular graphs having \emph{rna} number $1$ is bounded above by $12n-2$. In particular, we show that the smallest order of a cubic graph having \emph{rna} number $1$ is 10.

Keywords

Main Subjects

References

[1] M. Acharya and J.V. Kureethara, Parity labeling in signed graphs, J. Prime Research in Math. 17 (2021), no. 2, 1–7.
[2] M. Acharya, J.V. Kureethara, and T. Zaslavsky, Characterizations of some parity signed graphs, Australas. J. Comb. 81 (2021), no. 1, 89–100.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer London, 2008.
[4] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953), no. 2, 143–146.
[5] Y. Kang, X. Chen, and L. Jin, A study on parity signed graphs: The rna number, Appl. Math. Comput. 431 (2022), Article ID: 127322.
https://doi.org/10.1016/j.amc.2022.127322
Communications in Combinatorics and Optimization
Volume 9, Issue 3
September 2024
Pages 451-466

Files

Share

How to cite

Statistics