On the rna number of generalized Petersen graphs.

A signed graph (G, σ) is called a parity signed graph if there exists a bijective mapping f : V (G) → {1, . . ., |V (G)|} such that for each edge uv in G, f(u) and f(v) have same parity if σ(uv) = +1, and opposite parity if σ(uv) = −1. The rna number σ−(G) of G is the least number of negative edges among all possible parity signed graphs over G. Equivalently, σ−(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 Pn,k, σ−(Pn,k) lies between 3 and n. Moreover, we determine the exact value of σ−(Pn,k) for k ∈ {1, 2}. The rna numbers of some famous generalized Petersen graphs, namely, Petersen graph, Dürer graph, Möbius-Kantor graph, Dodecahedron, Desargues graph and Nauru graph are also computed. Recently, Acharya, Kureethara and Zaslavsky characterized the structure of those graphs whose rna number is 1. We use this characterization to show that the smallest order of a (4n + 1)-regular graph having rna number 1 is 8n + 6. We also prove the smallest order of (4n − 1)-regular graphs having rna number 1 is bounded above by 12n − 2. In particular, we show that the smallest order of a cubic graph having rna number 1 is 10. [ABSTRACT FROM AUTHOR]