Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the randić index

Mustapha Aouchiche; Pierre Hansen; Maolin Zheng

Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the randić index

Mustapha Aouchiche, Pierre Hansen, Maolin Zheng

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

Abstract

Using the AutoGraphiX 2 system (AGX2), we study further relations between graph invariants of the form lb_n ≤ R ⊕ i ≤ ub_n where R denotes the Randić index of a graph G = (V, E), i another invariant, ⊕ denotes one of the four operations +, -, x, /, lb_n and ub_n lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). Here i is in turn maximum, minimum and average degree, Δ, δ and d, diameter D, girth g, algebraic and node connectivity, a and v, Conjectures are obtained in 51 out of 56 cases, 28 of which are proved automatically, 19 are proved by hand, 7 remain open and only one is refuted.

Original language	English
Pages (from-to)	83-102
Number of pages	20
Journal	Match
Volume	58
Issue number	1
Publication status	Published - 2007
Externally published	Yes

ASJC Scopus subject areas

Chemistry(all)
Computer Science Applications
Computational Theory and Mathematics
Applied Mathematics

Cite this

@article{370c8ce3b2784de5a701108d4ce18705,

title = "Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the randi{\'c} index",

abstract = "Using the AutoGraphiX 2 system (AGX2), we study further relations between graph invariants of the form lbn ≤ R ⊕ i ≤ ubn where R denotes the Randi{\'c} index of a graph G = (V, E), i another invariant, ⊕ denotes one of the four operations +, -, x, /, lbn and ubn lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). Here i is in turn maximum, minimum and average degree, Δ, δ and d, diameter D, girth g, algebraic and node connectivity, a and v, Conjectures are obtained in 51 out of 56 cases, 28 of which are proved automatically, 19 are proved by hand, 7 remain open and only one is refuted.",

author = "Mustapha Aouchiche and Pierre Hansen and Maolin Zheng",

year = "2007",

language = "English",

volume = "58",

pages = "83--102",

journal = "Match",

issn = "0340-6253",

publisher = "University of Kragujevac, Faculty of Science",

number = "1",

}

TY - JOUR

T1 - Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the randić index

AU - Aouchiche, Mustapha

AU - Hansen, Pierre

AU - Zheng, Maolin

PY - 2007

Y1 - 2007

N2 - Using the AutoGraphiX 2 system (AGX2), we study further relations between graph invariants of the form lbn ≤ R ⊕ i ≤ ubn where R denotes the Randić index of a graph G = (V, E), i another invariant, ⊕ denotes one of the four operations +, -, x, /, lbn and ubn lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). Here i is in turn maximum, minimum and average degree, Δ, δ and d, diameter D, girth g, algebraic and node connectivity, a and v, Conjectures are obtained in 51 out of 56 cases, 28 of which are proved automatically, 19 are proved by hand, 7 remain open and only one is refuted.

AB - Using the AutoGraphiX 2 system (AGX2), we study further relations between graph invariants of the form lbn ≤ R ⊕ i ≤ ubn where R denotes the Randić index of a graph G = (V, E), i another invariant, ⊕ denotes one of the four operations +, -, x, /, lbn and ubn lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). Here i is in turn maximum, minimum and average degree, Δ, δ and d, diameter D, girth g, algebraic and node connectivity, a and v, Conjectures are obtained in 51 out of 56 cases, 28 of which are proved automatically, 19 are proved by hand, 7 remain open and only one is refuted.

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

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

M3 - Article

AN - SCOPUS:34547614984

SN - 0340-6253

VL - 58

SP - 83

EP - 102

JO - Match

JF - Match

IS - 1

ER -

Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the randić index

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this