آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 121 |
| تعداد مقالات | 1,448 |
| تعداد مشاهده مقاله | 1,555,683 |
| تعداد دریافت فایل اصل مقاله | 1,459,768 |
Derangement Representation of Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 13 خرداد 1404 اصل مقاله (846.82 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29684.2111 | ||
| نویسندگان | ||
| Somayeh Ashofteh؛ Moharram N. Iradmusa* | ||
| Department of Mathematical Sciences, Shahid Beheshti University, G.C., P.O. Box 19839-63113, Tehran, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Derangement؛ Symmetric Group؛ Derangement Representation Number | ||
| مراجع | ||
|
[1] Sagemath, the sage mathematics software system (version 9.4), The Sage Developers (2021), https://www.sagemath.org.
[2] L. Babai and V.T. S´os, Sidon sets in groups and induced subgraphs of Cayley graphs, Eur. J. Comb. 6 (1985), no. 2, 101–114. https://doi.org/10.1016/S0195-6698(85)80001-9
[3] L.W. Beineke and R.J. Wilson, Topics in Algebraic Graph Theory, Cambridge University Press, 2004.
[4] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Publishing Company, Incorporated, 2008.
[5] A. Cayley, On the theory of groups, as depending on the symbolic equation $\theta_n =1$, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 7 (1854), no. 42, 40–47.
[6] P. Erd¨os and A.B. Evans, Representations of graphs and orthogonal Latin square graphs, J. Graph Theory 13 (1989), no. 5, 593–595. https://doi.org/10.1002/jgt.3190130509
[7] P. Erdös, A.W. Goodman, and L. Pósa, The representation of a graph by set intersections, Can. J. Math. 18 (1966), 106–112. https://doi.org/10.4153/CJM-1966-014-3
[8] P. Frankl and M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Comb. Theory Ser. A. 22 (1977), no. 3, 352–360. https://doi.org/10.1016/0097-3165(77)90009-7
[9] C.C. Lindner, E. Mendelsohn, N.S. Mendelsohn, and B. Wolk, Orthogonal Latin square graphs, J. Graph Theory 3 (1979), no. 4, 325–338. https://doi.org/10.1002/jgt.3190030403
[10] C.C. Lindner and C.A. Rodger, Design Theory, Chapman and Hall/CRC, 2017.
[11] W.T. Trotter Jr and F. Harary, On double and multiple interval graphs, J. Graph Theory 3 (1979), no. 3, 205–211. https://doi.org/10.1002/jgt.3190030302 | ||
|
آمار تعداد مشاهده مقاله: 147 تعداد دریافت فایل اصل مقاله: 59 |
||