Laplacian energies of connected graphs

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

Numbers

$G$

$\operatorname{LE}(G)$

A_:

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

BW:

10/3

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:

4.828427124746190097603377448419396157139343750753896146353359475981464956924214077700775068655283145

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?{:

34/5

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

D@s:

6.562388608184031245267074482433714361105490433996953456791786281627673844773530106026582365095707850

D@{:

DBg:

6.072135954999579392818347337462552470881236719223051448541794490821041851275609798828828816757564550

comment: This is the path $P_{5}$.

DBk:

7.841619252963778989528394936201772181691914933456771936981350301637687873930815344619033490397272993

DB{:

42/5

DFw:

32/5

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

DF{:

44/5

DIk:

6.340172973252067445406511528850741850840279259646619907337454812773690100341494779351308368367151965

DJk:

7.940172973252067445406511528850741850840279259646619907337454812773690100341494779351308368367151965

DJ{:

46/5

DK[:

6.962388608184031245267074482433714361105490433996953456791786281627673844773530106026582365095707850

DK{:

38/5

DLo:

6.472135954999579392818347337462552470881236719223051448541794490821041851275609798828828816757564550

comment: This is the cycle $C_{5}$.

DL{:

8.028427124746190097603377448419396157139343750753896146353359475981464956924214077700775068655283145

DNw:

36/5

DN{:

44/5

D]{:

36/5

D^{:

42/5

Dbk:

6.872135954999579392818347337462552470881236719223051448541794490821041851275609798828828816757564550

D~{:

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

E?Bw:

26/3

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

E?Fg:

8.361607192003915478720883067257768289438285934824142517776676121752016647916880514849474150925766340

E?Fw:

E?NG:

8.456438958950993883154743189307410358480532558706953767731966906428287679670954926921196984144017630

E?NW:

9.789613948303991027650917559516928014519914099707057084116225642783509318073256233471354030214935582

E?Nw:

32/3

E?]o:

8.292528739883944684658270131431140891024954258374657402464973434885330990741814151863067442169780297

E?]w:

10.60290423680400064653990668714096387143351389351047937132007511639157455175987653965778785693872837

E?^o:

8.838927061969654849165909941143866420626642321820126569430132928887123820824476166551859190650440482

E?^w:

34/3

E?~o:

28/3

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

E?~w:

E@FG:

7.761972820088403708164328735030494311149172607772332201996097966351589426199865882925275834017262037

E@JW:

8.472135954999579392818347337462552470881236719223051448541794490821041851275609798828828816757564550

E@NW:

10.47213595499957939281834733746255247088123671922305144854179449082104185127560979882882881675756455

E@Nw:

E@QW:

7.841619252963778989528394936201772181691914933456771936981350301637687873930815344619033490397272993

E@Rw:

E@UW:

9.211102550927978586238442534940991892502593147690492425420906112454333896586020890409238164036981435

E@Vw:

10.82842712474619009760337744841939615713934375075389614635335947598146495692421407770077506865528315

E@YO:

7.464101615137754587054892683011744733885610507620761256111613958903866033817600074162292373514497151

comment: This is the path $P_{6}$.

E@YW:

8.685846165554340416109718021962283266803071289977970214792795219557662739625068406045771876985518948

E@]o:

10.29252873988394468465827013143114089102495425837465740246497343488533099074181415186306744216978030

E@]w:

11.93623757013733397987324002047429720476684722684381270465340844972490788509320987299112119027206170

E@^W:

10.83536635841750089015044938888758388249880910061959863002842727990630935421142513108957077379108529

E@^o:

10.17226039530298818249924327447719975395997565515345990276346626222045715415780949988519252398377382

E@^w:

E@`w:

9.028273858670582145387549733924434956104952601490809184443342788418683314583547181516140817592433007

E@ow:

9.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

E@vw:

10.96238860818403124526707448243371436110549043399695345679178628162767384477353010602658236509570785

E@~o:

E@~w:

EAMw:

10.32716298168739606589089362920143894068697857899730884351627826147668684132357723767537935431420624

EA]o:

9.191688434954841334000599958088537435893160330236880994896402687062374139651169785852916278911606541

EBYW:

8.472135954999579392818347337462552470881236719223051448541794490821041851275609798828828816757564550

EBYw:

9.789613948303991027650917559516928014519914099707057084116225642783509318073256233471354030214935582

EBZw:

EB]w:

11.78961394830399102765091755951692801451991409970705708411622564278350931807325623347135403021493558

EB^w:

EBhw:

10.26710402081131519320377596446761267654224348648012664814236735166379618100093014062769427761155734

EBjW:

9.841619252963778989528394936201772181691914933456771936981350301637687873930815344619033490397272993

EBjw:

10.47213595499957939281834733746255247088123671922305144854179449082104185127560979882882881675756455

EBnW:

11.21110255092797858623844253494099189250259314769049242542090611245433389658602089040923816403698144

EBn_:

8.828427124746190097603377448419396157139343750753896146353359475981464956924214077700775068655283145

EBnw:

11.84161925296377898952839493620177218169191493345677193698135030163768787393081534461903349039727299

EB~o:

EB~w:

ECXw:

9.028273858670582145387549733924434956104952601490809184443342788418683314583547181516140817592433007

EC\w:

10.47213595499957939281834733746255247088123671922305144854179449082104185127560979882882881675756455

EENg:

9.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

EFz_:

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

EFzw:

EF~w:

EGNW:

9.335283969129787997753184532308777441194571558576941107248608330720024157796491004294276481816537172

EGcw:

8.899946076330061743071031800989002859126776590333782481668008957932782931449494692554548818582887039

EGdo:

8.428639486755070374830995401697160977815839274438998868662764633018256092866532549591942500683928704

EGdw:

9.789613948303991027650917559516928014519914099707057084116225642783509318073256233471354030214935582

EHQW:

7.841619252963778989528394936201772181691914933456771936981350301637687873930815344619033490397272993

EHUW:

8.605551275463989293119221267470495946251296573845246212710453056227166948293010445204619082018490718

EHuw:

10.18100559204788778296914644214106027683740158437804555499558441562623014713881484477427111456144744

EI]w:

10.17226039530298818249924327447719975395997565515345990276346626222045715415780949988519252398377382

EI_w:

7.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

EIe_:

comment: This is the cycle $C_{6}$.

EImo:

7.789772292284327216488076522640743691813865892040287101065300239761621013004288260254530317477350963

EImw:

9.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

EIno:

8.428639486755070374830995401697160977815839274438998868662764633018256092866532549591942500683928704

EInw:

10.34017297325206744540651152885074185084027925964661990733745481277369010034149477935130836836715197

EJYW:

9.138802621666246059485014004129219137547903385889718115208461157487708517942276465495495483424231217

EJ]w:

11.50559372863632151583257660781053308729330898848679323609679959555379048749114283321852585731710715

EJ^w:

38/3

EJeg:

26/3

EJmw:

11.12310562561766054982140985597407702514719922537362043439863357309495434633762159358786365081068430

EJnW:

9.938884608797322626452554600803829279584629907178579546043786389560500281626343778537952415351824051

EJnw:

11.00683963991873411207317819551740851750694592631328657400412147944035676700816144601797503503381863

EJqw:

9.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

EJ~o:

32/3

EJ~w:

EKNG:

EK\w:

10.47213595499957939281834733746255247088123671922305144854179449082104185127560979882882881675756455

EK]w:

9.627213005296661630882455124721360484368562409530072110653088354444577673408278880813888259313606972

EK^w:

10.34017297325206744540651152885074185084027925964661990733745481277369010034149477935130836836715197

EK`w:

8.472135954999579392818347337462552470881236719223051448541794490821041851275609798828828816757564550

EK~o:

28/3

EK~w:

32/3

ELpw:

9.841619252963778989528394936201772181691914933456771936981350301637687873930815344619033490397272993

ELrw:

10.47213595499957939281834733746255247088123671922305144854179449082104185127560979882882881675756455

ELv_:

EL~o:

9.495093791412856764270044115086062823806010417420562813020026142648131623590880744367441735321949812

EL~w:

10.82842712474619009760337744841939615713934375075389614635335947598146495692421407770077506865528315

ENzw:

EN~w:

34/3

EPTW:

9.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

ER^W:

10.42863948675507037483099540169716097781583927443899886866276463301825609286653254959194250068392870

E]~o:

E]~w:

E^~w:

32/3

E_Nw:

E_]o:

8.130768281804421253721559349678411400552277174287427922778280625570532700484266740828959040181163818

E_]w:

9.625862073217278017991603464764474224358287591707990735798306768218664324075147485196400775503113630

E`Lw:

10.17226039530298818249924327447719975395997565515345990276346626222045715415780949988519252398377382

E`NG:

8.456438958950993883154743189307410358480532558706953767731966906428287679670954926921196984144017630

E`NW:

9.138802621666246059485014004129219137547903385889718115208461157487708517942276465495495483424231217

E`Nw:

E`]o:

9.464101615137754587054892683011744733885610507620761256111613958903866033817600074162292373514497151

E`]w:

10.29252873988394468465827013143114089102495425837465740246497343488533099074181415186306744216978030

EaMw:

9.191688434954841334000599958088537435893160330236880994896402687062374139651169785852916278911606541

Ebnw:

10.47213595499957939281834733746255247088123671922305144854179449082104185127560979882882881675756455

Ejmw:

Ek]w:

9.464101615137754587054892683011744733885610507620761256111613958903866033817600074162292373514497151

EoLW:

8.828427124746190097603377448419396157139343750753896146353359475981464956924214077700775068655283145

Es\w:

26/3

E~~w:

comment: This is the complete graph $K_{6}$.

Definition

The Laplacian energy of a graph $G$ with $n$ vertices and $m$ edges is $\operatorname{LE}(G)=\sum_{i=1}^{n}|\mu_i-2m/n|$, where $\mu_i$ are the combinatorial Laplacian eigenvalues, counted with multiplicity [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)

$\operatorname{LE}(G)=2\sum_{\mu_i>2m/n}(\mu_i-2m/n)$, since $\sum_i\mu_i=2m$. The eigenvalues are the roots, with multiplicity, of the Laplacian polynomial $\det(xI-L)$.

(2)

For a regular graph, $\operatorname{LE}(G)=\mathcal E(G)$, where $\mathcal E(G)$ is the graph energy [1].

(3)

$\operatorname{LE}(K_n)=2(n-1)$ for the complete graph on $n\geq2$ vertices.

(4)

$\operatorname{LE}(K_{a,b})=a+b+(a-1)|b-d|+(b-1)|a-d|$, where $a,b\geq1$ are the part sizes of the complete bipartite graph and $d=2ab/(a+b)$ is its average degree.

(5)

$\operatorname{LE}(P_n)=\sum_{j=0}^{n-1}|2-2\cos(\pi j/n)-2(n-1)/n|$ for the path on $n\geq2$ vertices.

(6)

$\operatorname{LE}(C_n)=2\sum_{j=0}^{n-1}|\cos(2\pi j/n)|$ for the cycle on $n\geq3$ vertices.

Comments

(7)

The combinatorial Laplacian is $L=D-A$. The adjacency matrix $A$ has entry $1$ for an edge 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$. The centering term $2m/n$ is the average vertex degree.

(8)

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

(9)

Entries are ordered by vertex count and then by ASCII graph6 order. 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
mean_degree = QQ(2 * G.size()) / QQ(G.order())
I = RealIntervalField(numberdb.bits(100, losing=80))
spectrum = G.laplacian_matrix().charpoly().roots(ring=AA)
LE = sum((multiplicity * abs(I(root) - I(mean_degree))
          for root, multiplicity in spectrum), I(0))
LE

References

[1]

Ivan Gutman and Bo Zhou, Laplacian energy of a graph, Linear Algebra and its Applications 414 (2006), 29–37. (doi)

Links

[2]

Brendan McKay: graph6 specification

[3]

Brendan McKay: connected graph catalogues

Similar tables

Laplacian polynomials of connected graphs — Its roots, counted with multiplicity, are the eigenvalues used in Laplacian energy.

Graph energies of connected graphs — Graph energy uses absolute adjacency eigenvalues and agrees with Laplacian energy on regular graphs.

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

Algebraic connectivity of connected graphs — Uses the least positive eigenvalue of the same combinatorial Laplacian.

Kirchhoff indices of connected graphs — Uses the reciprocals of the nonzero eigenvalues of the same Laplacian.

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds every isomorphism class of connected simple graphs with $2\leq n\leq6$, a census of $142$ graphs covering irregular degree patterns, trees and cyclic graphs, bipartite and non-bipartite graphs, and regular controls. Six is a practical, noncanonical cutoff independent of numeral notation; order seven would add $853$ graphs. No separate application is claimed for every member)

How they were obtained:

The generator computes the integer characteristic polynomial of $L=D-A$ and factors it over $\mathbb Q$. Its real roots in Sage's AA are compared exactly with $2m/n$. Complete groups of conjugate roots are summed by their rational traces. This proves all 57 rational values exactly; the other 85 values use certified RealIntervalField arithmetic at numberdb.bits(100, losing=80), which is 413 bits. The largest resulting enclosure width is less than $3.782\times10^{-123}$. Each enclosure supports the stored 100 significant digits. The attached generator explains the rationality criterion without constructing a field containing all roots.

A separate graph6 decoder and a determinant expanded over permutations reproduce the polynomial in the Laplacian polynomial table for every graph. Exact rational Sturm counts and bisection then enclose every root independently of AA; the sum of absolute deviations lies wholly inside each written interval. Independent symmetric matrix diagonalization with mpmath at 150 decimal digits agrees on all 142 graphs. The proof comes from rational and interval arithmetic; this matrix comparison is an additional agreement check.

Controls check the graph6 specification's worked example, the spectrum and energy of $K_2$, an edgeless matrix, root isolation and positive interval width under exact endpoint conversion. The checks validate the trace and second moment on every graph, the positive-eigenvalue sum, all five complete graphs, five paths, four cycles and nine complete-bipartite part-size pairs. All 11 regular graphs agree with the graph energy table. The census agrees with McKay's complete catalogues [3], and all keys agree with the order-two-through-six subsets of the existing graph tables. The attached checks.py can repeat these comparisons on stored entries. The attached argument-selection.md explains the parameter and finite extent.