Algebraic connectivity of connected graphs

edit · history · discussion · files · long url · combinatorics eigenvalue

Numbers

$G$

$a(G)$

A_:

comment: This is the complete graph $K_2$, also the path $P_2$, also the complete bipartite graph $K_{1,1}$.

BW:

comment: This is the path $P_3$, also the complete bipartite graph $K_{1,2}$.

Bw:

comment: This is the complete graph $K_3$, also the cycle $C_3$.

CF:

comment: This is the complete bipartite graph $K_{1,3}$.

CL:

0.5857864376269049511983112757903019214303281246230519268233202620092675215378929611496124656723584273

comment: This is the path $P_4$.

CN:

C]:

comment: This is the cycle $C_4$, also the complete bipartite graph $K_{2,2}$.

C^:

C~:

comment: This is the complete graph $K_4$.

D?{:

comment: This is the complete bipartite graph $K_{1,4}$.

D@s:

0.5188056959079843773664627587831428194472547830015232716041068591861630776132349469867088174521460752

D@{:

DBg:

0.3819660112501051517954131656343618822796908201942371378645513772947395371810975502927927958106088625

comment: This is the path $P_5$.

DBk:

0.6972243622680053534403893662647520268743517130773768936447734718864165258534947773976904589907546412

DB{:

DFw:

comment: This is the complete bipartite graph $K_{2,3}$.

DF{:

DIk:

0.8299135133739662772967442355746290745798603701766900463312725936131549498292526103243458158164240174

DJk:

0.8299135133739662772967442355746290745798603701766900463312725936131549498292526103243458158164240174

DJ{:

DK[:

0.5188056959079843773664627587831428194472547830015232716041068591861630776132349469867088174521460752

DK{:

DLo:

1.381966011250105151795413165634361882279690820194237137864551377294739537181097550292792795810608863

comment: This is the cycle $C_5$.

DL{:

1.585786437626904951198311275790301921430328124623051926823320262009267521537892961149612465672358427

DNw:

DN{:

D]{:

D^{:

Dbk:

1.381966011250105151795413165634361882279690820194237137864551377294739537181097550292792795810608863

D~{:

comment: This is the complete graph $K_5$.

E?Bw:

comment: This is the complete bipartite graph $K_{1,5}$.

E?Fg:

0.4858630706647089273062251330377825219475236992545954077783286057906583427082264092419295912037834966

E?Fw:

E?NG:

0.4384471871911697250892950720129614874264003873131897828006832134525228268311892032060681745946578517

E?NW:

0.6313506281127614942307907930556584673161638665482843255733428546619816086953749319880814297505906256

E?Nw:

E?]o:

0.5857864376269049511983112757903019214303281246230519268233202620092675215378929611496124656723584273

E?]w:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

E?^o:

0.9138698023485059087503783627614001230200121724232700486182668688897714229210952500574037380081130923

E?^w:

E?~o:

comment: This is the complete bipartite graph $K_{2,4}$.

E?~w:

E@FG:

0.3248691294333539291103782018499395191919674723226272673878461301585579570095006802577938999683472230

E@JW:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

E@NW:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

E@Nw:

E@QW:

0.3819660112501051517954131656343618822796908201942371378645513772947395371810975502927927958106088625

E@Rw:

E@UW:

0.6972243622680053534403893662647520268743517130773768936447734718864165258534947773976904589907546412

E@Vw:

E@YO:

0.2679491924311227064725536584941276330571947461896193719441930205480669830911999629188538132427514243

comment: This is the path $P_6$.

E@YW:

0.6570769172228297919451409890188583665984643550110148926036023902211686301874657969771140615072405258

E@]o:

0.5857864376269049511983112757903019214303281246230519268233202620092675215378929611496124656723584273

E@]w:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

E@^W:

0.8850924585232442014843859392914560318762437366128237913410128881604287970407926570575241541137027116

E@^o:

0.9138698023485059087503783627614001230200121724232700486182668688897714229210952500574037380081130923

E@^w:

E@`w:

0.4858630706647089273062251330377825219475236992545954077783286057906583427082264092419295912037834966

E@ow:

0.4384471871911697250892950720129614874264003873131897828006832134525228268311892032060681745946578517

E@vw:

1.518805695907984377366462758783142819447254783001523271604106859186163077613234946986708817452146075

E@~o:

E@~w:

EAMw:

0.6972243622680053534403893662647520268743517130773768936447734718864165258534947773976904589907546412

EA]o:

0.7215863905035550236443008372852981943616992313632918591537653575209284974056613235092668923280508224

EBYW:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

EBYw:

0.8929036232745221478278292191010386510761981045245772868275753239477481845168229350079168526921978486

EBZw:

EB]w:

0.8929036232745221478278292191010386510761981045245772868275753239477481845168229350079168526921978486

EB^w:

EBhw:

0.7311853096719155876518630487921012220232577676948872664559871848048156948532982310905679489513055032

EBjW:

1.381966011250105151795413165634361882279690820194237137864551377294739537181097550292792795810608863

EBjw:

1.381966011250105151795413165634361882279690820194237137864551377294739537181097550292792795810608863

EBnW:

1.697224362268005353440389366264752026874351713077376893644773471886416525853494777397690458990754641

EBn_:

1.585786437626904951198311275790301921430328124623051926823320262009267521537892961149612465672358427

EBnw:

1.697224362268005353440389366264752026874351713077376893644773471886416525853494777397690458990754641

EB~o:

EB~w:

ECXw:

0.4858630706647089273062251330377825219475236992545954077783286057906583427082264092419295912037834966

EC\w:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

EENg:

1.438447187191169725089295072012961487426400387313189782800683213452522826831189203206068174594657852

EFz_:

comment: This is the complete bipartite graph $K_{3,3}$.

EFzw:

EF~w:

EGNW:

0.8817161344229549425187509084421912249159137143248718725453922345788571269294060638149631717841507359

EGcw:

0.4130940157074780223065129840810436148397727216576998963568977028848796222804775562118448846715484363

EGdo:

0.3248691294333539291103782018499395191919674723226272673878461301585579570095006802577938999683472230

EGdw:

0.6313506281127614942307907930556584673161638665482843255733428546619816086953749319880814297505906256

EHQW:

0.6972243622680053534403893662647520268743517130773768936447734718864165258534947773976904589907546412

EHUW:

0.6972243622680053534403893662647520268743517130773768936447734718864165258534947773976904589907546412

EHuw:

1.607243752804893091642039128885912405634019012054308303840629468371525942829875040828092874024782397

EI]w:

0.9138698023485059087503783627614001230200121724232700486182668688897714229210952500574037380081130923

EI_w:

0.4384471871911697250892950720129614874264003873131897828006832134525228268311892032060681745946578517

EIe_:

comment: This is the cycle $C_6$.

EImo:

1.438447187191169725089295072012961487426400387313189782800683213452522826831189203206068174594657852

EImw:

1.438447187191169725089295072012961487426400387313189782800683213452522826831189203206068174594657852

EIno:

1.785680256622464812584502299151419511092080362780500565668617683490871953566733725204028749658035648

EInw:

1.829913513373966277296744235574629074579860370176690046331272593613154949829252610324345815816424017

EJYW:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

EJ]w:

0.9138698023485059087503783627614001230200121724232700486182668688897714229210952500574037380081130923

EJ^w:

EJeg:

EJmw:

1.438447187191169725089295072012961487426400387313189782800683213452522826831189203206068174594657852

EJnW:

1.697224362268005353440389366264752026874351713077376893644773471886416525853494777397690458990754641

EJnw:

1.829913513373966277296744235574629074579860370176690046331272593613154949829252610324345815816424017

EJqw:

1.438447187191169725089295072012961487426400387313189782800683213452522826831189203206068174594657852

EJ~o:

EJ~w:

EKNG:

EK\w:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

EK]w:

1.186393497351669184558772437639319757815718795234963944673455822777711163295860559593055870343196514

EK^w:

1.518805695907984377366462758783142819447254783001523271604106859186163077613234946986708817452146075

EK`w:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

EK~o:

EK~w:

ELpw:

1.697224362268005353440389366264752026874351713077376893644773471886416525853494777397690458990754641

ELrw:

2.381966011250105151795413165634361882279690820194237137864551377294739537181097550292792795810608863

ELv_:

EL~o:

2.585786437626904951198311275790301921430328124623051926823320262009267521537892961149612465672358427

EL~w:

2.585786437626904951198311275790301921430328124623051926823320262009267521537892961149612465672358427

ENzw:

EN~w:

EPTW:

0.4384471871911697250892950720129614874264003873131897828006832134525228268311892032060681745946578517

ER^W:

1.785680256622464812584502299151419511092080362780500565668617683490871953566733725204028749658035648

E]~o:

E]~w:

E^~w:

E_Nw:

E_]o:

1.267949192431122706472553658494127633057194746189619371944193020548066983091199962918853813242751424

E_]w:

1.267949192431122706472553658494127633057194746189619371944193020548066983091199962918853813242751424

E`Lw:

0.4858630706647089273062251330377825219475236992545954077783286057906583427082264092419295912037834966

E`NG:

0.4384471871911697250892950720129614874264003873131897828006832134525228268311892032060681745946578517

E`NW:

0.7639320225002103035908263312687237645593816403884742757291027545894790743621951005855855916212177250

E`Nw:

E`]o:

1.267949192431122706472553658494127633057194746189619371944193020548066983091199962918853813242751424

E`]w:

1.267949192431122706472553658494127633057194746189619371944193020548066983091199962918853813242751424

EaMw:

1.108780151289706483403071476985876502198648078082504817392456610619660769835922179107341306583912866

Ebnw:

2.381966011250105151795413165634361882279690820194237137864551377294739537181097550292792795810608863

Ejmw:

Ek]w:

2.267949192431122706472553658494127633057194746189619371944193020548066983091199962918853813242751424

EoLW:

Es\w:

E~~w:

comment: This is the complete graph $K_6$.

Definition

The algebraic connectivity $a(G)$ of a finite simple connected undirected unweighted graph $G$ on $n\geq2$ vertices is the second-smallest eigenvalue of its combinatorial Laplacian $L=D-A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree matrix [1].

Parameters

$G$

— graph (a finite simple connected undirected unweighted graph with at least two vertices, identified by its Sage canonical graph6 string)

Formulas

(1)

$a(G)$ is the least positive root of the Laplacian polynomial $\det(xI-L)$.

(2)

$a(K_n)=n$ for the complete graph on $n\geq2$ vertices [1].

(3)

$a(P_n)=2-2\cos(\pi/n)$ for the path on $n\geq2$ vertices [1].

(4)

$a(C_n)=2-2\cos(2\pi/n)$ for the cycle on $n\geq3$ vertices [1].

(5)

$a(K_{a,b})=\min(a,b)$ for the complete bipartite graph with positive part sizes $a,b$ and $a+b\geq3$ [1]. The remaining case is $a(K_{1,1})=2$.

Comments

(6)

The adjacency matrix $A$ has entry $1$ for adjacent vertices and $0$ otherwise, and $D=\operatorname{diag}(d_v)$ contains the vertex degrees. Write the Laplacian eigenvalues as $\mu_1\geq\cdots\geq\mu_n=0$, counting algebraic multiplicity. Then $a(G)=\mu_{n-1}>0$.

(7)

Each identifier is the graph6 encoding [2] of G.canonical_label(algorithm='sage'), computed with SageMath 10.9. Decode it with Graph(key, format='graph6'), preserving literal backslashes. The identifiers agree with the adjacency characteristic polynomial table, the Laplacian polynomial table, the adjacency spectral radius table and the Kirchhoff index table.

(8)

Entries are ordered by vertex count and then by ASCII order of graph6 strings. The connected graph counts at orders $2,3,4,5,6$ are $1,2,6,21,112$, respectively [3]. Complete graphs, paths, cycles and complete bipartite graphs are named in entry comments.

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.rings.qqbar import AA
from sage.rings.rational_field import QQ
from sage.rings.real_mpfi import RealIntervalField

G = Graph('CL', format='graph6')  # the path on four vertices
roots = G.laplacian_matrix().charpoly().roots(ring=AA)
a = min(root for root, multiplicity in roots if root > 0)
value = QQ(a) if a.minpoly().degree() == 1 else RealIntervalField(numberdb.bits(100, losing=80))(a)
value

References

[1]

Miroslav Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23 (1973), 298–305. (doi)

Links

[2]

Brendan McKay: graph6 specification

[3]

Brendan McKay: connected graph catalogues

Similar tables

Laplacian polynomials of connected graphs — Its least positive root is the algebraic connectivity.

Kirchhoff indices of connected graphs — Uses the same nonzero Laplacian spectrum to obtain the total effective resistance.

Spectral radii of connected graphs — Uses the same graph identifiers for the largest adjacency eigenvalue.

Estrada indices of connected graphs — Uses the same graph identifiers for the sum of exponentials of adjacency eigenvalues.

Graph energies of connected graphs — Uses the same graph identifiers for the sum of absolute adjacency eigenvalues.

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds all $142$ isomorphism classes of connected simple graphs with $2\leq|V(G)|\leq6$. This exhaustive small-order census covers trees and cyclic graphs, bipartite and non-bipartite graphs, and regular and irregular graphs, including varied small bottlenecks. Six is a practical, noncanonical boundary independent of numerical notation; order seven would add $853$ classes. No separate application is claimed for every graph)

How they were obtained:

The generator computes the integer characteristic polynomial of $L=D-A$, isolates its real roots in Sage's AA, and selects the least positive root exactly. The minimal polynomial proves whether this root is rational; all 59 rational entries are integers and are stored exactly. The 83 irrational entries are converted to certified RealIntervalField enclosures at numberdb.bits(100, losing=80), or 413 bits. Every enclosure has width less than $1.891\times10^{-124}$ and fits wholly inside its written interval of 100 significant digits.

An independent graph6 decoder and a determinant expanded over permutations reproduce every corresponding polynomial in the Laplacian polynomial table. Exact rational Sturm counts certify that each written interval contains the least positive root and that there is no smaller positive root. Independent mpmath symmetric diagonalization at 150 decimal digits agrees on every graph. This numerical comparison is an agreement check; the proof comes from exact root isolation and rational root counts.

The checks first test the graph6 specification's worked example, the known spectrum of $K_2$, an edgeless graph, a repeated-root polynomial and intentionally incorrect intervals. A separate endpoint-conversion control confirms a positive enclosure width for $1/3$. The graph census agrees as a set with McKay's catalogue files [3], and every key agrees with the order-two-through-six subsets of T237, T238, T397 and T400 and with T545 and T546. All five complete graphs, five paths, four cycles and nine complete-bipartite part-size pairs satisfy the stated formulas. The attached checks.py repeats these comparisons on values read from the database, while generate.py verifies all entries. The attached argument-selection.md explains the parameter and its finite extent.