Recherche à voisinage variable de graphes extrémaux 13. À propos de la maille

Mustapha Aouchiche; Pierre Hansen

doi:10.1051/ro:2006006

Recherche à voisinage variable de graphes extrémaux 13. À propos de la maille

Translated title of the contribution: Variable neighborhood search for extremal graphs. 13. About the network

Mustapha Aouchiche, Pierre Hansen

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

The AutoGraphiX system (AGX1 et AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form b_n ≤ g ⊕ ≤ b̄_n where g denotes the girth (or length of the smallest cycle) of a graph G = (V, E), i another invariant among independence number, radius,iameter, minimum, average or maximum degree, b_n and b̄ best possible functions of the order n of G, and ⊕ denotes one of the four operations +, -, x, /. 48 such conjectures are obtained : the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.

Translated title of the contribution	Variable neighborhood search for extremal graphs. 13. About the network
Original language	French
Pages (from-to)	275-293
Number of pages	19
Journal	RAIRO - Operations Research
Volume	39
Issue number	4
DOIs	https://doi.org/10.1051/ro:2006006
Publication status	Published - 2005
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science Applications
Management Science and Operations Research

Access to Document

10.1051/ro:2006006

Cite this

@article{de52e08d0b694f6ba3d6f361a6253b8f,

title = "Recherche {\`a} voisinage variable de graphes extr{\'e}maux 13. {\`A} propos de la maille",

abstract = "The AutoGraphiX system (AGX1 et AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form bn ≤ g ⊕ ≤ {\=b}n where g denotes the girth (or length of the smallest cycle) of a graph G = (V, E), i another invariant among independence number, radius,iameter, minimum, average or maximum degree, bn and {\=b} best possible functions of the order n of G, and ⊕ denotes one of the four operations +, -, x, /. 48 such conjectures are obtained : the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.",

author = "Mustapha Aouchiche and Pierre Hansen",

year = "2005",

doi = "10.1051/ro:2006006",

language = "French",

volume = "39",

pages = "275--293",

journal = "RAIRO - Operations Research",

issn = "0399-0559",

publisher = "EDP Sciences",

number = "4",

}

TY - JOUR

T1 - Recherche à voisinage variable de graphes extrémaux 13. À propos de la maille

AU - Aouchiche, Mustapha

AU - Hansen, Pierre

PY - 2005

Y1 - 2005

N2 - The AutoGraphiX system (AGX1 et AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form bn ≤ g ⊕ ≤ b̄n where g denotes the girth (or length of the smallest cycle) of a graph G = (V, E), i another invariant among independence number, radius,iameter, minimum, average or maximum degree, bn and b̄ best possible functions of the order n of G, and ⊕ denotes one of the four operations +, -, x, /. 48 such conjectures are obtained : the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.

AB - The AutoGraphiX system (AGX1 et AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form bn ≤ g ⊕ ≤ b̄n where g denotes the girth (or length of the smallest cycle) of a graph G = (V, E), i another invariant among independence number, radius,iameter, minimum, average or maximum degree, bn and b̄ best possible functions of the order n of G, and ⊕ denotes one of the four operations +, -, x, /. 48 such conjectures are obtained : the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.

UR - http://www.scopus.com/inward/record.url?scp=33646555434&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646555434&partnerID=8YFLogxK

U2 - 10.1051/ro:2006006

DO - 10.1051/ro:2006006

M3 - Article

AN - SCOPUS:33646555434

SN - 0399-0559

VL - 39

SP - 275

EP - 293

JO - RAIRO - Operations Research

JF - RAIRO - Operations Research

IS - 4

ER -

Recherche à voisinage variable de graphes extrémaux 13. À propos de la maille

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this