On digraphs of excess one

Millerová, Miroslava; Miret, Josep M.; Sillasen, Anita A.

Full metadata record

DC pole	Hodnota	Jazyk
dc.contributor.author	Millerová, Miroslava
dc.contributor.author	Miret, Josep M.
dc.contributor.author	Sillasen, Anita A.
dc.date.accessioned	2019-06-24T10:00:11Z	-
dc.date.available	2019-06-24T10:00:11Z	-
dc.date.issued	2018
dc.identifier.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.	en
dc.identifier.issn	0166-218X
dc.identifier.uri	2-s2.0-85026783991
dc.identifier.uri	http://hdl.handle.net/11025/34828
dc.description.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.	cs
dc.format	6 s.	cs
dc.format.mimetype	application/pdf
dc.language.iso	en	en
dc.publisher	Elsevier	en
dc.rights	Plný text není přístupný.	cs
dc.rights	© Elsevier	en
dc.subject	k-geodetický digraf	cs
dc.subject	Mooreova mez	cs
dc.subject	digraf s excesem 1	cs
dc.subject	diregularita	cs
dc.subject	characteristický polynom	cs
dc.title	On digraphs of excess one	en
dc.title.alternative	Digrafy s excesem 1	cs
dc.type	článek	cs
dc.type	article	en
dc.rights.access	closedAccess	en
dc.type.version	publishedVersion	en
dc.description.abstract-translated	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.	en
dc.subject.translated	k-geodetic digraph	en
dc.subject.translated	Moore bound	en
dc.subject.translated	excess one digraph	en
dc.subject.translated	diregularity	en
dc.subject.translated	characteristic polynomial	en
dc.identifier.doi	10.1016/j.dam.2017.06.016
dc.type.status	Peer-reviewed	en
dc.identifier.document-number	427218900017
dc.identifier.obd	43926270
Vyskytuje se v kolekcích:	Články / Articles (KMA) OBD

Soubory připojené k záznamu:

Soubor	Velikost	Formát
1-s2.0-S0166218X17303025-main.pdf	309,87 kB	Adobe PDF	Zobrazit/otevřít Vyžádat kopii

Zobrazit minimální záznam Zobrazit statistiky

Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/34828

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.

hledání

navigace