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,σ) 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 \emph{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 \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