Title: On digraphs of excess one
Other Titles: Digrafy s excesem 1
Authors: Millerová, Miroslava
Miret, Josep M.
Sillasen, Anita A.
Citation: MILLEROVÁ, M., MIRET, J. M., SILLASEN, A. A. On digraphs of excess one. DISCRETE APPLIED MATHEMATICS, 2018, roč. 238, č. MAR 31 2018, s. 161-166. ISSN 0166-218X.
Issue Date: 2018
Publisher: Elsevier
Document type: článek
article
URI: 2-s2.0-85026783991
http://hdl.handle.net/11025/34828
ISSN: 0166-218X
Keywords: k-geodetický digraf;Mooreova mez;digraf s excesem 1;diregularita;characteristický polynom
Keywords in different language: k-geodetic digraph;Moore bound;excess one digraph;diregularity;characteristic polynomial
Abstract: Digraf, ve kterém pro každou dvojici (ne nutně různých) vrcholů u, v existuje nejvýše jeden sled délky nejvýše k z u do v se nazývá k-geodetický digraf. Počet vrcholů N(d,k) k-geodetického digrafu s minimálním výstupním stupněm d je větší nebo roven Mooreově mezi M(d,k) a rovnost zde nastává, právě když digraf je silně geodetický, tj. jeho průměr je roven k. Silně geodetické digrafy tedy existují pro d=1 nebo k=1. Pro d, k větší než 1 tedy chceme určit, zda existují k-geodetické digrafy s minimálním výstupním stupněm d a počtem vrcholů N(d,k)=M(d,k)+1. Takový digraf nazýváme (d,k,1)-digraf a říkáme, že má exces 1. V článku dokazujeme, že (d,k,1)-digrafy jsou vždy diregulární, a tedy (2,k,1)-digrafy neexistují. Dále studujeme faktorizaci v Q[x] charakteristického polynomu (d,k,1)-digrafu, z níž dokazujeme neexistenci takových digrafů pro k=2 když d je větší než 7, a pro k=3,4 když d je větší než 1.
Abstract in different language: 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.
Rights: Plný text není přístupný.
© Elsevier
Appears in Collections:Články / Articles (KMA)
OBD

Files in This Item:
File SizeFormat 
1-s2.0-S0166218X17303025-main.pdf309,87 kBAdobe PDFView/Open    Request a copy


Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/34828

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

search
navigation
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD