Estrada indices of connected graphs

edit · history · discussion · files · short url · combinatorics chemistry eigenvalue

Numbers

$G$

$\operatorname{EE}(G)$

A_:

3.086161269630487556955811241514123365203058224731727409474804429421538126098447397928529452871086071

comment: This is the complete graph $K_2$.

BW:

5.356367113217141727978444135640250566862588065843313865621631481899841878604121838336747886218078381

comment: This is the path $P_3$.

Bw:

8.124814981273534870421475000897929548071937832615382993102801425917496787568857370098607033770961082

comment: This is the complete graph $K_3$.

CF:

7.829154880351856321453561348748315280705142805978304503049574901984597222079296081468811200721353821

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

CL:

7.635733837560584232618734748797066389999967327203866788225204822094161228167997109155335151465061582

comment: This is the path $P_4$.

CN:

10.71922334838326856556082644875566275871475389459688080366710449366540418965097710712915519491850167

C]:

9.524391382167262919124426955547492216587947116461423205555286695176647170180545453321410607569778844

comment: This is the cycle $C_4$.

C^:

14.53360928563993644702444564032371556470738241504308412963188298254270037494319592452428181198500232

C~:

21.18917524670199470571510096506610049932534123164945364790244463479123036532667314127593898329077663

comment: This is the complete graph $K_4$.

D?{:

10.52439138216726291912442695554749221658794711646142320555528669517664717018054545332141060756977884

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

D@s:

10.11811961438857592338113169540602131478789877100323859109804473681224057565097407369254842256974952

D@{:

13.54365862727334544107706178392023248764321834849940821609027295732377930670987221239814309366620501

DBg:

9.915316149982343878409372590262438645908201030710031912524379331406135348177743479397340653592439892

comment: This is the path $P_5$.

DBk:

13.32724713275441411237211300672807346796823132671109131690834306524648564999350180418029569857737611

DB{:

17.51836841111039744417924313007212772160916185041469942217554545225070761694135310589218315101046956

DFw:

14.66877281966771709828577186935583464952038274704168682213052959404071109468983367959627407541071423

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

DF{:

22.58875164759572275441805291971566316784135051549549386035492990405038074793836122449874255708959439

DIk:

12.03649415431201854632529584467697497815488302878314281609108394229089562384641556646263959332250794

DJk:

17.18397966842046744498590822415399305902174415212021380093477668111905966691354408894973070538514483

DJ{:

24.38214864091084001195659688103747464116760198548022940769532726790825667065046477308113556963550805

DK[:

13.01184518629528721482467157703206943158420203546404986822292390651922314714012056644088240332863522

DK{:

16.61977055527042400398025688183783892991044063977481153910668741196423850104164332245281126485608839

DLo:

11.49618632188367214792025678286893843182083286044368382149185376660436667698752964007973426389096389

comment: This is the cycle $C_5$.

DL{:

21.74212739598649761061802648920620936134318103588086894678513696151532541794819033999123250849938053

DNw:

20.24846263534955320485033256716059781008161988882045025982726186959482866714947990031880519629332587

DN{:

30.10691981131641721354373678206182630288594914871899182600952138753681682258573110964292096630462096

D]{:

27.85937931278960767953929567103993346000240163465930676022991237280114439225686573452715803170536239

D^{:

40.24017241692083784527846402432138507782957173805633089917887083151354935554500018613529489677241737

Dbk:

15.39271790486097290819240308891259252957466846447872971636086572683873782228769933456668312353318557

D~{:

56.06966779783000836449235628350672187257398156274114006385794116534350808291546869510556965932841272

comment: This is the complete graph $K_5$.

E?Bw:

13.46334694226153310518279120099322409145298506080078926406446572123160557160425598692237176284859627

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

E?Fg:

12.82340951994918850593101649257048765449791737592576102028416652090099180837718922117119538728580394

E?Fw:

16.61978147272394395996579195304011874791146202778866706428216834211299229171331980583542497512554447

E?NG:

12.61055265179775047608023819706161558179100534119315061503009112459818529627899285124994006044086491

E?NW:

16.16588970756802754558502470359736357070193744985670275940573639533890308263095364667236008666065786

E?Nw:

20.76411837826513896480832409225798600386434018008832562350556079591805330962524873235637860559154976

E?]o:

14.54950821189202066213860244250734745665604328553251667353927015065314369770270338485090121571968234

E?]w:

20.52231117963449926096721042252939681513277383773956626126579699997526460422311539793141569296612198

E?^o:

17.45887481086908134093882217069306188058273662156920580302656851782177836597514656533444150417797592

E?^w:

26.03957803875271406201435039467034983337067846973637778376017763240845636536501995509591991771993297

E?~o:

20.97793442511985293429772254085126216584881792438352200843973722293473972984631027473229101250951725

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

E?~w:

32.60608745520732130714979463687499304131176582560428541334302484743293536044158372642822016056546653

E@FG:

12.39792349471645699081221733376361769893087711304214000927108833790894693529667424522574177193388986

E@JW:

14.77289280886884584300554045370531575322925365532445964546080142277109266975716313697888042576278247

E@NW:

20.06678233940091130752663933640521157681988497322874736074233647946639323856771893326635030781259383

E@Nw:

27.84728519635428099817722969966866185636319910452240310674403989154385167298521508433038706398485870

E@QW:

12.40730594338017770025227458667166823134224639238401184288725928010381047938622463454659928631787789

E@Rw:

19.83553760559361991811844222406290526090508378532408160437287664012112020635860607099020246157491401

E@UW:

15.94896378490776646475673211397106381740574891995784706285703578379143558463142450040101323027165958

E@Vw:

25.16538279516859122506527861317258155601864492609983525136458881759191320711287983768306040074259342

E@YO:

12.19490142544047709565033714635637015425558002296267929792299698556659318695775512320140978062719597

comment: This is the path $P_6$.

E@YW:

14.55912149922621897083737078292067797956901742043958360047890513390973138188134133357461897524012279

E@]o:

19.83553760559361991811844222406290526090508378532408160437287664012112020635860607099020246157491401

E@]w:

27.59610969658923273849266233296579278793560804014007876876824511068725410397120891879385056729959375

E@^W:

24.79675280179572535856626423274672786528119290503889511052112065354345972712791896044013296115422392

E@^o:

23.19402908172612024843674287175211614239809192455325124449088858563755482807335043056428553458353487

E@^w:

33.79260548256291412893716421371480749008730316620231077769023811298749130543380052188810090862964739

E@`w:

15.84646044928252834270168346792530476986853253206079333947731009914366775550676993626755713505047164

E@ow:

15.50805976786615983806164465568278134436073834687813078651616804053040464144204528719727475318963200

E@vw:

30.72522677972065688718951441177069328541611983929598545135213674006420683028307256915554160493418336

E@~o:

27.19894020269397741777401799571595449624860879401606509989955640617736387655095839307078744625322758

E@~w:

41.09683347966262298143010755178708338526317660481303342891948393943102551507091924974903636761089741

EAMw:

20.18372160990258107253773089795655831107557640345654559119788131498316422735879322259789163362491003

EA]o:

17.92334309787181297326870509616321021733783450350566370842340505199490852167042142432532738293677592

EBYW:

17.22398724660431252085645467223751614045882958769215480178233356283356169085357042771349969568854120

EBYw:

23.29447682190561707432670485471748172721532520947265929461813119359715632208427882735346816182130013

EBZw:

31.50649621221014526224668873671138897140195843256503203846200665679596720519741919286572454010343872

EB]w:

33.38596242204729382531106353957498969149068285839823409881055897249382139038591383488398952391311109

EB^w:

44.21541048980560955380531543738815791071309344785706197558592578900560736789481243984937023738893003

EBhw:

24.41824490628354175490574467284757092317163538260212947282143604642842991438210712147806259435946658

EBjW:

21.85027964789562652176413533377210936906739840482005303298036522533959143572369613028490805846263583

EBjw:

29.68315081148842552199630041578537981770426654384336401734298475069000776575621221751617131954216920

EBnW:

29.83117425250601690833512549836137967523528737864156737616647944422886389906384992128548168802654743

EBn_:

20.49395165527650016152673387923654221749369875399106274065300799948372959933662987776760847350019513

EBnw:

40.09613615880421914271860270998941528286343678513453872216169864573206594084209435760944847055748322

EB~o:

35.60933805806481704713898860876877563173088872582101167390569438240798337530230962620562286670917771

EB~w:

52.42690962648518739654400742359652075494828593634303439061353015472571895685942908072728488034871000

ECXw:

19.82557822845731806583353234150560944944370188080500339976895212623911032181754773527404689438041247

EC\w:

25.30069669217371051293988963324876798465656939834541480393432768399546838238185897710153512683971658

EENg:

21.12178740249197333207601498780385282024002031216543177442133042617842459786620504906736270070132730

EFz_:

24.13532399155553168390787207023177967361960743074257335994656195730490654582217328135855140448965105

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

EFzw:

46.58640574678656328069933391265552136865831517414045840086071274565067587648257721044270289895113321

EF~w:

67.06844370506354668095484057647331125300192382817348284997701795117586529363630576169426360926389878

EGNW:

18.26673742363964622632717346768968632855710867418439024843192538211937864996013730036809978626151951

EGcw:

15.62015659557727120860956936146943306555286348813414524932804245015659806952122010371646981790292594

EGdo:

15.29171061836624070108105073159143682562097385042103276511954033911340678992622476688961309886730806

EGdw:

19.24706315851003064372045994887708768437826079625715868910642886255201897077252784247063280610362373

EHQW:

13.99182645748094729877395773463487354359876676195065275673449582210582152245294658564906793949372395

EHUW:

18.01934695616415205268320883648740159842644992362085175155917268122338888365333140567561483865490615

EHuw:

28.14201477894107567876799632154819853428825345920502877491573772208535354505663402566974495304583304

EI]w:

30.99909217747435916785399757269271068311861564686344505729398339187723064483320527868756127580054323

EI_w:

14.32635766478533173751735603542793621268471856553753643850969344715673421550842723992326175193973439

EIe_:

13.69671392142823803303604943857573894699406356592487802450489555401972342237744024917846951331195099

comment: This is the cycle $C_6$.

EImo:

19.98971202641943769115288089196607754122001369166298497269941279259684981472127137527907300047145533

EImw:

28.55528417471351834652583974903774151860621690435018411836332660109546509566179854187873649043229013

EIno:

26.40034473705925898683359458916294873874692956471984757715406864282646113475270784881337948233865451

EInw:

37.46852805493222336847477727061575633884409047576470267901650998026953683992397823700727048994941947

EJYW:

22.81994169259164923515113482168475154727762372412029750760227709611147290508127525767845915654526537

EJ]w:

43.63279813769479491239077260130484186009454717545736303129775932650031060752709171931374196574627748

EJ^w:

60.41612083325100826264428586888690705733095254220827270141893751370015228049253762748364123451264469

EJeg:

21.33698818298756547854927223053133877847941481434033381688916353194469699107339337367456874115958614

EJmw:

39.37754018865818202526752638202137616619207766948548286330129537816393699934216828353379341303049731

EJnW:

36.35231114395283316985861176275164928691349001923772495790961935257064299736263138322758714703854010

EJnw:

51.04427106002366658511951247720673382675860517562792053570651984825590277609949045289399403759154171

EJqw:

26.98958383521723091835554254086270924041831060085312236539737288947469391802531948790563057981034620

EJ~o:

49.02944863285200034433089915312327661624596049903937980190069935573945244306740087159367781359570552

EJ~w:

69.78737162698521262142701553518156957230878523664423462259363457678817409292391462866331763446198371

EKNG:

16.53061273073320360314153484416136710367111659746301774009424313110023060821163319452398062654257834

EK\w:

32.84085642162487728006956989363262446851791826640278570746988209861249087746140529909584877921702892

EK]w:

29.13572910598148718252857107954817649258518590793404270943789870398912354578303257926124476486134502

EK^w:

38.66483722921701877205712499316739727933010147683114916277668278214323980655936379794614093395988383

EK`w:

17.80755456648987379016467134244455725569149274381499709482091029576999990340553785713808862905192889

EK~o:

33.69224872483780886410560587838911640651482405033601282281782927685447348654003112435674961343655260

EK~w:

49.97273078454593505759150576262690774682688316273205843591097877295947555488995240943558763450132564

ELpw:

27.25140317602135512051224133235176242732660827294830313764938722189744634301003906579440341544454475

ELrw:

35.82614333907259287257502541600035567916009235109287333372818164242763082219584369125083194954636978

ELv_:

25.07448931811993836007681611587934920156041802407326148228221960273106925664849670565007558375949823

EL~o:

44.77854864086905495081868397255061673909177601142408878781414795661379633291256473414097625636619366

EL~w:

64.75525033301492372006726967845256650696778467088152184329829911816165945247874605206651602241476298

ENzw:

61.63157148096888473231916484993454975683064376182186660833810862884136603439899719763618775807029953

EN~w:

86.47788631925013656956812285834191826467675651178400902692774961946849108976813420345278954578892700

EPTW:

19.47777036590806522405243511770136293246126850877862048715644024616906419136844048333622514441687051

ER^W:

37.06649006102879756995476665447427813921659934273312612415335089589844903306637928110225787376605137

E]~o:

57.86882059961746446189826019280584720960600013043322048876291170386180884813884486155117680692604824

E]~w:

81.98090426566741387924491566952661054717401684357759540508358597782154382846968507720853449032807677

E^~w:

112.4050939022633663779273387904011014294132731580345155708912404719698692287346194809576000190094357

E_Nw:

24.05038643267256966421063196673588711111153477498916128128025948013671258563279596522086176519995737

E_]o:

16.26295642048483179264337430833774049289370811348800939925864646714617508930273528572597885270012348

E_]w:

22.78802175290305718888874946597476069662661449797969730219089547203791494613940011032077784148659492

E`Lw:

26.69464300649055905155411841815312454411413035723878169613634522560481095780614865630142914083310885

E`NG:

18.40674732464948550871151168074837021436199669810785073751755834508916291729204831188869720087301060

E`NW:

23.16353891945850650848323507913523086853143016140714980134432819261481552484372084623807826720007519

E`Nw:

31.22029660243527291400492183426539869214453286142936793906295724453504451010189320126747668878838965

E`]o:

21.60847244926498681792302166404352018033583206247129367074060142939680273032156279585994514583720805

E`]w:

29.94554058242009523649510691255405682520545985939103416970471680222268251835531313245568748457644846

EaMw:

22.32442444693333416342760664701302508305497062012640664307266107474621061005274232822004472653759882

Ebnw:

47.51292179429161374904550587651745647948160123098256645892037650990501828412538734101730873535437195

Ejmw:

45.41032920176610479692696434088890956476438458858066310778301746115886534066699024107768598718015018

Ek]w:

33.94367187813522733671807211932433799146943644693968612543938710905342668011524979616652586858964823

EoLW:

17.24216166690282471357015565801550191665639486698990030744766336573036841520274315905546560919022566

Es\w:

33.55406416749252290052532486501762561169413211202124322549855113845739913924833615589241354626220498

E~~w:

150.2525563084338150290931988913595839607167232490378282192920291193993722996830750964741458316286194

comment: This is the complete graph $K_6$.

Definition

For a graph $G$ on $n$ vertices, its Estrada index is $\operatorname{EE}(G)=\sum_{i=1}^{n}e^{\lambda_i}$, where the $\lambda_i$ are its adjacency eigenvalues, counted with multiplicity [1].

Parameters

$G$

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

Formulas

(1)

$\operatorname{EE}(G)=\operatorname{tr}(\exp(A))=\sum_{k=0}^{\infty}\operatorname{tr}(A^k)/k!$, where $A$ is the adjacency matrix [1].

(2)

$\operatorname{EE}(K_n)=e^{n-1}+(n-1)e^{-1}$ for the complete graph $K_n$ on $n\geq2$ vertices.

(3)

$\operatorname{EE}(K_{a,b})=2\cosh(\sqrt{ab})+a+b-2$ for the complete bipartite graph with parts of sizes $a,b\geq1$.

Comments

(4)

The adjacency matrix $A$ has entry $1$ for adjacent vertices and $0$ otherwise. Its real eigenvalues are ordered $\lambda_1\geq\cdots\geq\lambda_n$ and counted with algebraic multiplicity.

(5)

Each graph is identified by its graph6 encoding [2] after Sage's canonical_label(algorithm='sage'). Decode it with Graph(key, format='graph6'), keeping backslashes literal. The canonicalization was run with SageMath 10.9. The identifiers agree with the adjacency characteristic polynomial table, the Laplacian polynomial table, the adjacency spectral radius table and the Kirchhoff index table.

(6)

Entries are ordered by the number of vertices and then by ASCII order of the graph6 strings. Common names are given for complete graphs, paths, cycles and complete bipartite graphs.

(7)

The quantity $\operatorname{tr}(A^k)$ counts closed walks of length $k$ with a specified starting vertex. Formula (1) gives each such walk weight $1/k!$, including the $n$ walks of length zero [1].

(8)

The connected-graph counts at orders $2,3,4,5,6$ are $1,2,6,21,112$, respectively [3].

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.rings.qqbar import AA
from sage.rings.real_arb import RealBallField

G = Graph('BW', format='graph6')  # the path on three vertices
B = RealBallField(numberdb.bits(100, losing=80))
spectrum = G.adjacency_matrix().charpoly().roots(ring=AA)
EE = sum((multiplicity * B(root).exp() for root, multiplicity in spectrum), B(0))
EE

References

[1]

E. Estrada, The many facets of the Estrada indices of graphs and networks, SeMA Journal 79 (2022), 57–125. (doi)

Links

[2]

Brendan McKay: graph6 and sparse6 formats

[3]

Brendan McKay: connected simple graph catalogues

Similar tables

Characteristic polynomials of connected graphs — its polynomial roots, with multiplicity, are the adjacency eigenvalues used in this sum

Spectral radii of connected graphs — stores the largest adjacency eigenvalue of the same graphs

Laplacian polynomials of connected graphs — uses the same graph identifiers for the characteristic polynomials of the combinatorial Laplacian

Kirchhoff indices of connected graphs — uses the same graph identifiers for the total effective resistance

Data properties

Entries are of type: real number

digits: 100 (Unknown key)

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$, covering branching trees, cyclic graphs, bipartite and non-bipartite graphs, and regular and irregular degree patterns for comparison of their closed-walk sums. Six is a practical, noncanonical boundary independent of numerical notation; order seven would add $853$ classes. The selection is an exhaustive small-order census, and does not assert a separate application for every graph)

How they were obtained:

The generator computes the adjacency characteristic polynomial exactly over $\mathbb{Z}$, isolates its real algebraic roots in Sage's AA, and sums their exponentials with multiplicity in RealBallField. The initial precision is numberdb.bits(100, losing=80), or 413 bits. Every result retained at least 408 accuracy bits, so the initial precision sufficed for all 142 entries. The written values carry 100 significant digits with the interval convention of one unit in the last place.

An independent check decodes graph6 directly and counts closed walks with integer arithmetic. It sums $\operatorname{tr}(A^k)/k!$ over exact rationals through degree $N$. With maximum degree $d$, the remaining positive tail is at most $n d^{N+1}/((N+1)!(1-d/(N+2)))$ for $N+2>d$. The bound was less than $10^{-120}$ for every graph, with $N\leq124$. Controls used $K_2$, $K_3$ and an edgeless graph before checking the census. Both enclosures fit inside each written 100-digit interval.

The graph census agrees with McKay's catalogues [3]. The canonical keys agree with the order-two-through-six subsets of T237, T238, T397 and T400; the exact characteristic polynomials agree with T237. The complete-graph and complete-bipartite formulas were checked for all five complete graphs and all nine unordered positive part-size pairs present. The attached generator, independent checks and argument-selection note reproduce these decisions.