Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity

Slim Belhaiza; Nair Maria Maia De Abreu; Pierre Hansen; Carla Silva Oliveira

doi:10.1007/0-387-25592-3_1

Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity

Slim Belhaiza
, Nair Maria Maia De Abreu
, Pierre Hansen
, Carla Silva Oliveira

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

24 Scopus citations

Abstract

The algebraic connectivity a(G) of a graph G = (V, E) is the second smallest eigenvalue of its Laplacian matrix. Using the AutoGraphiX (AGX) system, extremal graphs for algebraic connectivity of G in function of its order n = |V| and size m = |E| are studied. Several conjectures on the structure of those graphs, and implied bounds on the algebraic connectivity, are obtained. Some of them are proved, e.g., if G ≠ K_n which is sharp for all m ≥ 2.

Original language	English
Title of host publication	Graph Theory and Combinatorial Optimization
Publisher	Springer US
Pages	1-16
Number of pages	16
ISBN (Print)	0387255915, 9780387255910
DOIs	https://doi.org/10.1007/0-387-25592-3_1
State	Published - 2005
Externally published	Yes

ASJC Scopus subject areas

General Economics, Econometrics and Finance
General Business, Management and Accounting

Access to Document

10.1007/0-387-25592-3_1

Cite this

@inbook{bfa03c4cdeac4917a6fa7ad0f82e4fd7,

title = "Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity",

abstract = "The algebraic connectivity a(G) of a graph G = (V, E) is the second smallest eigenvalue of its Laplacian matrix. Using the AutoGraphiX (AGX) system, extremal graphs for algebraic connectivity of G in function of its order n = |V| and size m = |E| are studied. Several conjectures on the structure of those graphs, and implied bounds on the algebraic connectivity, are obtained. Some of them are proved, e.g., if G ≠ Kn which is sharp for all m ≥ 2.",

author = "Slim Belhaiza and \{De Abreu\}, \{Nair Maria Maia\} and Pierre Hansen and Oliveira, \{Carla Silva\}",

year = "2005",

doi = "10.1007/0-387-25592-3\_1",

language = "English",

isbn = "0387255915",

pages = "1--16",

booktitle = "Graph Theory and Combinatorial Optimization",

publisher = "Springer US",

address = "United States",

}

TY - CHAP

T1 - Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity

AU - Belhaiza, Slim

AU - De Abreu, Nair Maria Maia

AU - Hansen, Pierre

AU - Oliveira, Carla Silva

PY - 2005

Y1 - 2005

N2 - The algebraic connectivity a(G) of a graph G = (V, E) is the second smallest eigenvalue of its Laplacian matrix. Using the AutoGraphiX (AGX) system, extremal graphs for algebraic connectivity of G in function of its order n = |V| and size m = |E| are studied. Several conjectures on the structure of those graphs, and implied bounds on the algebraic connectivity, are obtained. Some of them are proved, e.g., if G ≠ Kn which is sharp for all m ≥ 2.

AB - The algebraic connectivity a(G) of a graph G = (V, E) is the second smallest eigenvalue of its Laplacian matrix. Using the AutoGraphiX (AGX) system, extremal graphs for algebraic connectivity of G in function of its order n = |V| and size m = |E| are studied. Several conjectures on the structure of those graphs, and implied bounds on the algebraic connectivity, are obtained. Some of them are proved, e.g., if G ≠ Kn which is sharp for all m ≥ 2.

UR - https://www.scopus.com/pages/publications/34247101737

U2 - 10.1007/0-387-25592-3_1

DO - 10.1007/0-387-25592-3_1

M3 - Chapter

AN - SCOPUS:34247101737

SN - 0387255915

SN - 9780387255910

SP - 1

EP - 16

BT - Graph Theory and Combinatorial Optimization

PB - Springer US

ER -

Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity

Abstract

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this