Derangement Representation of Graphs
| Autor: | Ashofteh, Somayeh, Iradmusa, Moharram N. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A derangement $k$-representation of a graph $G$ is a map $\pi$ of $V(G)$ to the symmetric group $S_k$, such that for any two vertices $v$ and $u$ of $V(G)$, $v $ and $u$ are adjacent if and only if $\pi(v)(i) \neq \pi(u)(i)$ for each $i \in \{1,2,3,\ldots,k\}$. The derangement representation number of $G$ denoted by $drn(G)$, is the minimum of $k$ such that $G$ has a derangement $k$-representation. In this paper, we prove that any graph has a derangement $k$-representation. Also, we obtain some lower and upper bounds for $drn(G)$, in terms of the basic parameters of $G$. Finally, we determine the exact value or give the better bounds of the derangement representation number of some classes of graphs. Comment: 20 pages, 3 figures, 4 tables |
| Databáze: | arXiv |
| Externí odkaz: |
|