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

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2009

Confidentiality

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

Name of the periodical

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Volume of the periodical

157

Issue of the periodical within the volume

9

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

9

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—