| Název: | On digraphs of excess one |
| Další názvy: | Digrafy s excesem 1 |
| Autoři: | Millerová, Miroslava Miret, Josep M. Sillasen, Anita A. |
| Citace zdrojového dokumentu: | 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. |
| Datum vydání: | 2018 |
| Nakladatel: | Elsevier |
| Typ dokumentu: | článek article |
| URI: | 2-s2.0-85026783991 http://hdl.handle.net/11025/34828 |
| ISSN: | 0166-218X |
| Klíčová slova: | k-geodetický digraf;Mooreova mez;digraf s excesem 1;diregularita;characteristický polynom |
| Klíčová slova v dalším jazyce: | k-geodetic digraph;Moore bound;excess one digraph;diregularity;characteristic polynomial |
| Abstrakt: | 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. |
| Abstrakt v další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. |
| Práva: | Plný text není přístupný. © Elsevier |
| 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 |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/34828Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.