Enumerations of vertex orders of almost Moore digraphs with selfrepeats

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F08%3A00501447" target="_blank" >RIV/49777513:23520/08:00501447 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

Original language description

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 there exists a vertex v, called repeat of u and denoted by r(u) = v, such that there are two walks of length at most 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 almostMoore digraph of diameter k greater or equal to 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.

Czech name

Enumerace počtů vrcholů almost Mooreovských orientovaných grafů se selfrepeat vrcholy

Czech description

Almost Mooreovský orientovaný graf G stupně d >1 a průměru k>1 je pravidelný orientovaný graf s počtem vrcholů o jednu menším než je Mooreova mez. Je-li G almost Mooreovský orientovaný graf, pak pro každý vrchol u existuje vrchol v, nazývaný repeat uzluu, a označovaný r(u) = v, takový, že existují dva sledy délky nejvýše k z u do v. Nepmenší přirozené číslo p pro které rp(u) = u se nazývá řád u. Je-li řád u roven 1, pak se u nazývá selfrepeat. Je známo, že je-li G almost Mooreovský orientovaný graf průměru k většího nebo rovného 3, pak G obsahuje buďto přesně k selfrepeat vrcholů, nebo žádný. V článku prezentujeme přesný vzorec pro stanovení počtu všech možných velikostí almost Mooreovských orientovaných grafů G se selfrepeat vrcholy, založený na velikosti výstupních okolí selfrepeat vrcholů.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Discrete Mathematics

ISSN

0012-365X

e-ISSN

—

Volume of the periodical

308

Issue of the periodical within the volume

1

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

6

Pages from-to

—

UT code for WoS article

000251879500010

EID of the result in the Scopus database

—