On the existence of radial Moore graphs for every radius and every degree

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F15%3A43924762" target="_blank" >RIV/49777513:23520/15:43924762 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ejc.2015.01.004" target="_blank" >http://dx.doi.org/10.1016/j.ejc.2015.01.004</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2015.01.004" target="_blank" >10.1016/j.ejc.2015.01.004</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the existence of radial Moore graphs for every radius and every degree

Popis výsledku v původním jazyce

The degree/diameter problem is to determine the largest graphs of given maximum degree and given diameter. General upper bounds - called Moore bounds - for the order of such graphs are attainable only for certain special graphs, called Moore graphs. Moore graphs are scarce and so the next challenge is to find graphs which are somehow ''close'' to the nonexistent ideal of a Moore graph by holding fixed two of the parameters, order, diameter and maximum degree, and optimising the third parameter. In thispaper we consider the existence of graphs that have order equal to Moore bound for given radius and maximum degree and as the relaxation we require the diameter to be at most one more than the radius. Such graphs are called radial Moore graphs. In this paper we prove that radial Moore graphs exist for every diameter and every sufficiently large degree, depending on the diameter.

Název v anglickém jazyce

On the existence of radial Moore graphs for every radius and every degree

Popis výsledku anglicky

The degree/diameter problem is to determine the largest graphs of given maximum degree and given diameter. General upper bounds - called Moore bounds - for the order of such graphs are attainable only for certain special graphs, called Moore graphs. Moore graphs are scarce and so the next challenge is to find graphs which are somehow ''close'' to the nonexistent ideal of a Moore graph by holding fixed two of the parameters, order, diameter and maximum degree, and optimising the third parameter. In thispaper we consider the existence of graphs that have order equal to Moore bound for given radius and maximum degree and as the relaxation we require the diameter to be at most one more than the radius. Such graphs are called radial Moore graphs. In this paper we prove that radial Moore graphs exist for every diameter and every sufficiently large degree, depending on the diameter.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/ED1.1.00%2F02.0090" target="_blank" >ED1.1.00/02.0090: NTIS - Nové technologie pro informační společnost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

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

EUROPEAN JOURNAL OF COMBINATORICS

ISSN

0195-6698

e-ISSN

—

Svazek periodika

47

Číslo periodika v rámci svazku

Neuveden

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

15-22

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—