On digraphs of excess one
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F18%3A43955271" target="_blank" >RIV/49777513:23520/18:43955271 - isvavai.cz</a>
Result on the web
<a href="https://www.sciencedirect.com/science/article/pii/S0166218X17303025" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0166218X17303025</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2017.06.016" target="_blank" >10.1016/j.dam.2017.06.016</a>
Alternative languages
Result language
angličtina
Original language name
On digraphs of excess one
Original language description
A digraph in which, for every pair of vertices u and v (not necessarily distinct), there is at most one walk of length at most k from u to v is called a k-geodetic digraph. The order N(d,k) of a k-geodetic digraph of minimum out-degree d is at least the Moore bound M(d,k), which is attained if and only if the digraph is strongly geodetic, that is, if its diameter is k. Thus, strongly geodetic digraphs only exist for d=1 or k=1. Hence, for d, k greater than 1 we wish to determine if there exist k-geodetic digraphs with minimum out-degree d and order N(d,k)=M(d,k)+1. Such a digraph is denoted as a (d,k,1)-digraph or said to have excess 1. In this paper, we prove that (d,k,1)-digraphs are always diregular and thus that no (2,k,1)-digraphs exist. Furthermore, we study the factorization in Q[x] of the characteristic polynomial of a (d,k,1)-digraph, from which we show the non-existence of such digraphs for k=2 when d is greater than 7 and for k=3,4 when d is greater than 1.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
DISCRETE APPLIED MATHEMATICS
ISSN
0166-218X
e-ISSN
—
Volume of the periodical
238
Issue of the periodical within the volume
MAR 31 2018
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
6
Pages from-to
161-166
UT code for WoS article
000427218900017
EID of the result in the Scopus database
2-s2.0-85026783991