آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 116 |
| تعداد مقالات | 1,314 |
| تعداد مشاهده مقاله | 1,310,916 |
| تعداد دریافت فایل اصل مقاله | 1,217,434 |
On the rna number of generalized Petersen graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 9، شماره 3، آذر 2024، صفحه 451-466 اصل مقاله (619.14 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.27973.1408 | ||
| نویسندگان | ||
| Deepak Sehrawat* ؛ Bikash Bhattacharjya | ||
| Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| generalized Petersen graph؛ parity labeling؛ parity signed graph؛ rna number؛ edge-cut | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 475 تعداد دریافت فایل اصل مقاله: 1,715 |
||