Spectra of Orders for k-Regular Graphs of Girth g

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Spectra of Orders for k-Regular Graphs of Girth g

Popis výsledku v původním jazyce

A (k, g)-graph is a k-regular graph of girth g. Given k &gt;= 2 and g &gt;= 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 &gt;= 3, (k, 3), k &gt;= 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 &apos;starter graphs&apos; 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 &apos;starter graphs&apos;.

Název v anglickém jazyce

Spectra of Orders for k-Regular Graphs of Girth g

Popis výsledku anglicky

A (k, g)-graph is a k-regular graph of girth g. Given k &gt;= 2 and g &gt;= 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 &gt;= 3, (k, 3), k &gt;= 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 &apos;starter graphs&apos; 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 &apos;starter graphs&apos;.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discussiones Mathematicae - Graph Theory

ISSN

1234-3099

e-ISSN

—

Svazek periodika

41

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

PL - Polská republika

Počet stran výsledku

11

Strana od-do

"1115–1125"

Kód UT WoS článku

000667233200016

EID výsledku v databázi Scopus

2-s2.0-85079613491