No Detail Found!

New results regarding the permutation cycle structure of almost Moore digraphs

Author(s)
Edy T. Baskoro Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia; Center for Research on Graph Theory and Combinatorics, Indonesia
Arnau Messegue´ Departament de Matem a`tica i Inform a`tica, Universitat Rovira Virgili,,Spain
Josep M. Miret Departament de Matem`atica, Universitat de Lleida, Spain
Abstract
In this paper, we show that the nonexistence of almost Moore digraphs G with degree d > 3, diameter k > 4, and order N = d + d2 + · · · + dk can be reduced to the problem of showing the nonexistence of almost Moore digraphs with a specific permutation cycle structure. Specifically, if G has self-repeats, the structure is (k, 0, . . . , 0, ms, 0, . . .) with N = k + sms; if G does not have self-repeats, the structure is either (0, . . . , 0, ms, 0, . . .) with N = sms, or (0, . . . , 0, ms, 0, . . . , 0, m2s, 0, . . .) with N = sms + 2sm2s.
Publication Details
Page(s) 1-7
Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
degree/diameter problem, Moore bound, digraphs, permutation cycle structure
References
Baskoro E. T.,A E. T.,Miret J. M.,Baskoro E. T.,Miller M.,J. M. .1998 .Plesn´ık, On the structure of digraphs with order close to the Moore bound. Graphs Combin, 14 : 109-119.
Baskoro E. T.,Miller M.,J. M. .1995 .Plesn´ık, Sˇ. Zn a´m, Digraphs of degree 3 and order close to the Moore bound. J. Graph Theory, 20 : 339-349.
Baskoro E. T.,Miller M.,J. M.,Sutton M. .2005 .Complete characterisation of almost Moore digraphs of degree three. J. Graph Theory, 48 : 112-126.
Bridges W. G.,Toueg S. .1980 .On the impossibility of directed Moore graphs. J. Combin. Theory Ser. B, 29 : 339-341.
Cholily Y. M. .2011 .A conjecture on the existence of almost Moore digraphs. Adv. Appl. Discrete Math. 8, : 57-64.
Cholily Y. M.,Baskoro E. T.,S. Uttunggadewa, E. T.,Akiyama E. T.,Baskoro E. T. .2005 .Some conditions for the existence of (d, k)-digraphs. Combinatorial Geometry and Graph Theory, : 87-93.
Conde J.,Gimbert J.,Miller M.,Miret J. .2014 .On the nonexistence of almost Moore digraphs. European J. Combin, 39 : 170-177.
Conde J.,Gimbert J.,Moreno R. .2008 .Nonexistence of almost Moore digraphs of diameter three, Electron. , 15 : R87.
Conde J.,Gimbert J.,Moreno R. .2013 .Nonexistence of almost Moore digraphs of diameter four, Electron. , 20 : P75.
Fiol M. A.,I. Alegre M. A.,Yebra J. L. A. .1983 .Line digraphs iterations and the (d, k) problem for directed graphs. ACM SIGARCH Comput. Archit. News, 11 : 174-177.
Gimbert J. .1999 .On the existence of (d, k)-digraphs. , : 375-391.
Gimbert J. .2001 .Enumeration of almost Moore digraphs of diameter two. , 231 : 177-190.
Lo N.,Miret J. .2023 .Nonexistence of almost Moore digraphs of degrees 4 and 5 with self-repeats, Electron. , 30 : P156.
Messegue´ A.,Miret J.,Sillasen A. .2024 .On the nonexistence of almost Moore digraphs with self-repeats. arXiv:2410.20226 [math.CO], : .
Miller M.,I. Fris M.,Designs M. .1993 .Maximum order digraphs for diameter 2 or degree 2. , : 269-278.
Miller M.,Gimbert J. .2000 .. , 218 : 265-270.
Miller M.,Miret J.,Sillasen A. A. .2018 .On digraphs of excess one. Discrete Appl. Math, 238 : 161-166.
Miller M.,J. M.,J. Combin. M. .2005 .Sˇ ir a´nˇ , Moore graphs and beyond: A survey, Electron. , : DS14.
Miret J.,Simanjuntak R.,S. R. .2023 .Simo´n, On the permutation cycle structures for almost Moore digraphs of degrees 4 and 5. , 12 : 189-195.
Plesn J. .1974 .´ık, Sˇ . Zn a´m, Strongly geodetic directed graphs. Acta Fac. Rerum Natur. Univ. Comenian. Math, 29 : 29-34.
Sillasen A. A. .2014 .On k-geodetic digraphs with excess one. Electron. J. Graph Theory Appl, 2(2) : 150-159.
Sillasen A. A. .2015 .Subdigraphs of almost Moore digraphs induced by fixpoints of an automorphism, Electron. J. Graph Theory Appl, 3(1) : 1-7.
Tuite J. .2024 .The structure of digraphs with excess one. J. Graph Theory, 106 : 411-434.
0

Citations

0

Downloads

19

Views