On the rna number of powers of cycles
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908841572040704 |
|---|---|
| author | Sehrawat, Deepak Kumar, Anil Ahlawat, Sweta |
| author_facet | Sehrawat, Deepak Kumar, Anil Ahlawat, Sweta |
| contents | A signed graph $(G,σ)$ on $n$ vertices is called a \textit{parity signed graph} if there is a bijective mapping $f \colon V(G) \rightarrow \{1,\ldots,n\}$ such that $f(u)$ and $f(v)$ have same parity if $σ(uv)=1$, and opposite parities if $σ(uv)=-1$ for each edge $uv$ in $G$. The \emph{rna} number $σ^{-}(G)$ of $G$ is the least number of negative edges among all possible parity signed graphs over $G$. In other words, $σ^{-}(G)$ is the smallest size of an edge-cut of $G$ such that the sizes of two sides differ at most one.
Let $C_n^{d}$ be the $d\text{th}$ power of a cycle of order $n$. Recently, Acharya, Kureethara and Zaslavsky proved that the \emph{rna} number of a cycle $C_n$ on $n$ vertices is $2$. In this paper, we show for $2 \leq d < \lfloor \frac{n}{2} \rfloor$ that $2d \leq σ^{-}(C_n^{d}) \leq d(d+1)$. Moreover, we prove that the graphs $C_n^{2}$ and $C_n^{3}$ achieve the upper bound of $d(d+1)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_08514 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the rna number of powers of cycles Sehrawat, Deepak Kumar, Anil Ahlawat, Sweta Combinatorics 05C22, 05C38, 05C40, 05C78 A signed graph $(G,σ)$ on $n$ vertices is called a \textit{parity signed graph} if there is a bijective mapping $f \colon V(G) \rightarrow \{1,\ldots,n\}$ such that $f(u)$ and $f(v)$ have same parity if $σ(uv)=1$, and opposite parities if $σ(uv)=-1$ for each edge $uv$ in $G$. The \emph{rna} number $σ^{-}(G)$ of $G$ is the least number of negative edges among all possible parity signed graphs over $G$. In other words, $σ^{-}(G)$ is the smallest size of an edge-cut of $G$ such that the sizes of two sides differ at most one. Let $C_n^{d}$ be the $d\text{th}$ power of a cycle of order $n$. Recently, Acharya, Kureethara and Zaslavsky proved that the \emph{rna} number of a cycle $C_n$ on $n$ vertices is $2$. In this paper, we show for $2 \leq d < \lfloor \frac{n}{2} \rfloor$ that $2d \leq σ^{-}(C_n^{d}) \leq d(d+1)$. Moreover, we prove that the graphs $C_n^{2}$ and $C_n^{3}$ achieve the upper bound of $d(d+1)$. |
| title | On the rna number of powers of cycles |
| topic | Combinatorics 05C22, 05C38, 05C40, 05C78 |
| url | https://arxiv.org/abs/2309.08514 |