| 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 | Size | Format | |
|---|---|---|---|
| 1-s2.0-S0166218X17303025-main.pdf | 309,87 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/34828Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.