Enumerations of vertex orders of almost Moore digraphs with selfrepeats (Q2463473): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q223565 |
Changed an Item |
||
Property / author | |||
Property / author: Edy Tri Baskoro / rank | |||
Normal rank |
Revision as of 16:14, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumerations of vertex orders of almost Moore digraphs with selfrepeats |
scientific article |
Statements
Enumerations of vertex orders of almost Moore digraphs with selfrepeats (English)
0 references
12 December 2007
0 references
The number \(n\) of vertices of a digraph with maximum out-degree \(d\) and diameter \(k\) cannot exceed the Moore bound \(M_{d,k}=1+d+d^2+\cdots +d^k\). It is known that except in trivial cases Moore digraphs (those with \(n=M_{d,k}\)) do not exist. The authors study almost Moore digraphs (\(n=M_{d,k}-1\)) via the notion repeat. A vertex \(v\) is called a repeat of a vertex \(u\) if there are two \(u\)-\(v\) walks of length not exceeding \(k\), which is denoted by \(r(u)=v\). The smallest positive integer \(p\) such that \(r^p(u)=u\) is called the order of \(u\). A selfrepeat is a vertex of order one. This notion has been studied in several papers (see e.g. \textit{E. T. Baskoro, Y. M. Cholily} and \textit{M. Miller} [Bull. Inst. Comb. Appl. 46, 99--109 (2006; Zbl 1099.05046)]). In this paper, an exact formula is given for the number of all vertex orders based on the vertex orders of the out-neighbours of any selfrepeat vertex.
0 references