Spectra of Orders for k-Regular Graphs of Girth g
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F21%3A10247654" target="_blank" >RIV/61989100:27240/21:10247654 - isvavai.cz</a>
Result on the web
<a href="https://www.dmgt.uz.zgora.pl/publish/bbl_view_pdf.php?ID=64196" target="_blank" >https://www.dmgt.uz.zgora.pl/publish/bbl_view_pdf.php?ID=64196</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.7151/dmgt.2233" target="_blank" >10.7151/dmgt.2233</a>
Alternative languages
Result language
angličtina
Original language name
Spectra of Orders for k-Regular Graphs of Girth g
Original language description
A (k, g)-graph is a k-regular graph of girth g. Given k >= 2 and g >= 3, infinitely many (k, g)-graphs of infinitely many orders are known to exist. Our goal, for given k and g, is the classification of all orders n for which a (k, g)-graph of order n exists; we choose to call the set of all such orders the spectrum of orders of (k, g)-graphs. The smallest of these orders (the first element in the spectrum) is the order of a (k, g)-cage; the (k, g)-graph of the smallest possible order. The exact value of this order is unknown for the majority of parameters (k, g). We determine the spectra of orders for (2, g), g >= 3, (k, 3), k >= 2, and (3, 5)-graphs, as well as the spectra of orders of some families of (k, 4)-graphs. In addition, we present methods for obtaining (k, g)-graphs that are larger then the smallest known (k, g)-graphs, but are smaller than (k, g)-graphs obtained by Sauer. Our constructions start from (k, g)-graphs that satisfy specific conditions derived in this paper and result in graphs of orders larger than the original graphs by one or two vertices. We present theorems describing ways to obtain 'starter graphs' whose orders fall in the gap between the well-known Moore bound and the constructive bound derived by Sauer and are the first members of an infinite sequence of graphs whose orders cover all admissible orders larger than those of the 'starter graphs'.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discussiones Mathematicae - Graph Theory
ISSN
1234-3099
e-ISSN
—
Volume of the periodical
41
Issue of the periodical within the volume
4
Country of publishing house
PL - POLAND
Number of pages
11
Pages from-to
"1115–1125"
UT code for WoS article
000667233200016
EID of the result in the Scopus database
2-s2.0-85079613491