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 journalArticlepeer-review

34 Citations (Scopus)

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ć 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.

Original languageEnglish
Pages (from-to)83-102
Number of pages20
JournalMatch
Volume58
Issue number1
Publication statusPublished - 2007
Externally publishedYes

ASJC Scopus subject areas

  • General Chemistry
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the randić index'. Together they form a unique fingerprint.

Cite this