On digraphs of excess one

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On digraphs of excess one

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On digraphs of excess one

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

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

Název periodika

DISCRETE APPLIED MATHEMATICS

ISSN

0166-218X

e-ISSN

—

Svazek periodika

238

Číslo periodika v rámci svazku

MAR 31 2018

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

6

Strana od-do

161-166

Kód UT WoS článku

000427218900017

EID výsledku v databázi Scopus

2-s2.0-85026783991