Calculating the extremal number ex(v;{C_3,C_4,...,C_n})

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F09%3A00503075" target="_blank" >RIV/49777513:23520/09:00503075 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Calculating the extremal number ex(v;{C_3,C_4,...,C_n})

Popis výsledku v původním jazyce

By the extremal number ex(v;{C_3,C_4,...,C_n}) we denote the maximum number of edges in a graph of order v and girth at least g greaTER OR EQUAL TO n+1. The set of such graphs is denoted by EX(v;{C_3,C_4,...,C_n}). In 1975, Erdos mentioned the problem ofdetermining extremal numbers ex(v;{C_3,C_4}) in a graph of order v and girth at least five. In this paper, we consider a generalized version of the problem for any value of girth by using the hybrid simulated annealing and genetic algorithm (HSAGA). Using this algorithm, some new results for n greater or equal to 5 have been obtained. In particular, we generate some graphs of girth 6; 7 and 8 which in some cases have more edges than corresponding cages. Furthermore, future work will be described regarding the investigation of structural properties of such extremal graphs and the implementation of HSAGA using parallel computing.

Název v anglickém jazyce

Calculating the extremal number ex(v;{C_3,C_4,...,C_n})

Popis výsledku anglicky

By the extremal number ex(v;{C_3,C_4,...,C_n}) we denote the maximum number of edges in a graph of order v and girth at least g greaTER OR EQUAL TO n+1. The set of such graphs is denoted by EX(v;{C_3,C_4,...,C_n}). In 1975, Erdos mentioned the problem ofdetermining extremal numbers ex(v;{C_3,C_4}) in a graph of order v and girth at least five. In this paper, we consider a generalized version of the problem for any value of girth by using the hybrid simulated annealing and genetic algorithm (HSAGA). Using this algorithm, some new results for n greater or equal to 5 have been obtained. In particular, we generate some graphs of girth 6; 7 and 8 which in some cases have more edges than corresponding cages. Furthermore, future work will be described regarding the investigation of structural properties of such extremal graphs and the implementation of HSAGA using parallel computing.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2009

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

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

157

Číslo periodika v rámci svazku

9

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

9

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—