Enumerations of vertex orders of almost Moore digraphs with selfrepeats |
| |
Authors: | ET Baskoro |
| |
Institution: | a Combinatorial Mathematics Research Division, FMIPA, Institut Teknologi Bandung, Jl. Ganesa 10, Bandung 40132, Indonesia b Universitas Muhammadiyah Malang, Jl. Tlogomas 246, Malang 65144, Indonesia c School of Information Technology and Mathematical Sciences, University of Ballarat, P.O. Box 663, Ballarat, Vic. 3353, Australia d Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic |
| |
Abstract: | An almost Moore digraph G of degree d>1, diameter k>1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u∈V(G) there exists a vertex v∈V(G), called repeat of u and denoted by r(u)=v, such that there are two walks of length ?k from u to v. The smallest positive integer p such that the composition rp(u)=u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k?3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex. |
| |
Keywords: | Almost Moore digraph Selfrepeat |
本文献已被 ScienceDirect 等数据库收录! |
|