Distance Estrada indices of connected graphs

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

Numbers

$G$

$\operatorname{DEE}(G)$

A_:

3.086161269630487556955811241514123365203058224731727409474804429421538126098447397928529452871086071

comment: This is the complete graph $K_2$.

BW:

15.98062106977042375057082809489108821161682674849701995126753205004485511246927153533782085494150776

comment: This is the path $P_3$.

Bw:

8.124814981273534870421475000897929548071937832615382993102801425917496787568857370098607033770961082

comment: This is the complete graph $K_3$.

CF:

104.9365181929889927958468098276271895456062108959116811150647094128856405638320476321899306007797364

comment: This is the star $K_{1,3}$.

CL:

175.4639383067344962489316396768200439766588421227751903581091971793356896222334257071466066083257718

comment: This is the path $P_4$.

CN:

61.26764791115747562437093605785095423836743255627883924506306041940296394947161538544619125696395942

C]:

55.86882059961746446189826019280584720960600013043322048876291170386180884813884486155117680692604824

comment: This is the cycle $C_4$.

C^:

36.29137891902769446831171514050725280098901944475375545382649094874239887324372088560526396015941124

comment: This is the diamond graph.

C~:

21.18917524670199470571510096506610049932534123164945364790244463479123036532667314127593898329077663

comment: This is the complete graph $K_4$.

D?{:

740.1390320287034460941666742634856479754055314406149312736876415936413332097925535820224483453343557

comment: This is the star $K_{1,4}$.

D@s:

1737.016217792652681289673509796859786210824754652700507338010362358439844699853470605450134741199440

D@{:

482.3844509738899418167922560072862102922130421921294971676288513318215177953855466691478111518938923

DBg:

3977.953213670659586321467988963604676167625668603249362080363168448001539195829333034652649127799788

comment: This is the path $P_5$.

DBk:

764.3874258021335471482632729916093816196706546878658052860923592038629021977201236038796689662790250

comment: This is the bull graph.

DB{:

318.4669443907120633829313084362739363583900033604748376592217693065320309025444115175466999989884363

comment: This is the dart graph.

DFw:

284.9172775131309382452539683134928077743288113490558022256235434463147672743382716195972018852226036

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

DF{:

216.6813092555594938464563578062285417005815340219033543443346543937305083582572811275513530049695082

DIk:

692.5014592056168161300806647509637089909758032505931131687566683751517350935367613979709891153244505

DJk:

502.0777202792142142584341708502316217887720171868026073372025431953093050837653425208314557476840570

DJ{:

210.6687426668196416571370416438388408090102726982607937713490145147155996839658256428694859680460854

DK[:

1107.369635575373552471662235349859248585313725488643779987246534396341523562542326574162667387539143

DK{:

300.6159883030068430320958689230189405329492637655407420257375572672802600282962350588964722011646549

comment: This is the butterfly graph.

DLo:

404.9397222639734216223495085158231868552988342954011977100617883191589791965711910616296268597024564

comment: This is the cycle $C_5$.

DL{:

200.3050661192779489996401079213728423584745087455161663090305134108452956533475664426514121118943097

DNw:

187.4191441454300667414668476377139644516972241266757911721477065561184677097738818775466742878979386

DN{:

135.9582449210763215791408893727953893470174868198435454946870686773275869252899010126976869839237242

comment: This is the house X graph.

D]{:

126.7215804776497176194648670288342060459341383501232369880838744728710754363647079646363012061165675

comment: This is the wheel $W_5$.

D^{:

87.09231113578144277003639168415013602479535217064748588958946915426179123470424787183537921855454236

Dbk:

281.6974367870896967660724570224676227278070584281452065771240738014822221542977056925487453888023353

comment: This is the house graph.

D~{:

56.06966779783000836449235628350672187257398156274114006385794116534350808291546869510556965932841272

comment: This is the complete graph $K_5$.

E?Bw:

5338.936272056536891806300916033921698439467102570399075278023517751140773223659017855425238402206889

comment: This is the star $K_{1,5}$.

E?Fg:

15839.94846300674487695908782920188892111507321506188410414957484462809685296107621971163182679158140

E?Fw:

3752.026112850319582145824305168195531993772868534718502308873500633210548244553712542938656762600955

E?NG:

22027.75982790624056429695148312012926417494652573148518178589720463102121862364581332942138999669190

E?NW:

8031.048227455407433164623527485809584700603556170441649678539650145905359717635270328260364009442815

E?Nw:

2668.640414147000215857723461783426918049955083488841560542025899840050326276928886960865765562552216

E?]o:

15630.34098506027157671493794930072156654980988224243102373739970459511988547322714085370493569964684

E?]w:

3978.206966829842914536652041988731229378536632927661511306442287879912916203308513098386853229885741

E?^o:

3454.473365218972049445269284936300423320284180537302411603107998779336036148015878777099918439945507

E?^w:

1935.393964830938006121947214178882898358511499071085496893642360561586936885391709410505179946500051

E?~o:

1746.538126361112822663672666439278093627493408449610508480191167786144052403858508312316207617326369

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

E?~w:

1445.165200253118182493252824872633321828779859896151662599559953318106663779758918748533524753097705

E@FG:

63500.77439677117064129840522527701731548418049718152809646168098738504107226056481479455636862748182

E@JW:

7326.190941961713424633983793288498396124990989756029428565159557652462582580074395305907436819056805

E@NW:

5642.192859588359720943739309031800138204026734948087843666656708712218175054462937487486891990292191

E@Nw:

1910.893218119807050673341365497338255011462672436922097600081242364288864342700444270708695243598402

E@QW:

46278.61132461993734097323232875393810595323057583854714826949311540375671784077079378257855211538470

E@Rw:

2573.954424077091662774568342479748591723121976865398714599409039606328450228499733753189754290462612

E@UW:

11911.80036306997335287637681705699391103940098131755796064440190282075275391372297985516384026255106

E@Vw:

1850.228615972263651385651457063086055043031621841498796816158069657512172751373849291536968339556549

E@YO:

181556.1102617632977481881539720419638994634975869017354261721686537504891742638798118416766279361030

comment: This is the path $P_6$.

E@YW:

10517.04417838890892522238796837218649376434839440844126758822435628993890739282436185112735430596333

E@]o:

12388.95164604071043860567560493486679311350947057101773778928675043782581223878581183457318158987116

E@]w:

2916.655620037573065275622034384779997956963167807190115889323435993596160647998676167085576602628283

E@^W:

2739.952737706901738673724917328910093850842499898863431293630878102557692342616654244411239349646587

E@^o:

2534.639615845742776071575179008836342446331053587005733908399604428627084423234113508273673289699601

E@^w:

1348.632665381208812107022767457340191430094572633709793469217721351637095820065792151519581105508884

E@`w:

11109.28957359692569569816913843641836870729755211921551399800027249519722719999857716183416294230012

E@ow:

14897.25766209238664366851496773833006905926631068082316638303706632230295267020325326629054895260645

E@vw:

1307.055224891452829405381207631450628116653819840863793839677932456853461274756637367533522041013599

E@~o:

1209.323337144857367373347227836983441415941931056710752559815073288646445938888870418287184327002483

E@~w:

979.9749118956918780836361287130042352187777524355235718072842726476609003595527802700579121093996350

EAMw:

5787.816128320897501443804475177308672467456599095525349367606935785771417065163855661989013712784550

EA]o:

5034.678625905491002206332037328484935211883826515398061997423878050091030892612100029183962743673201

EBYW:

5275.358694772996561803839131505554328040891550211224570755072496736377134838592150155877163512748618

EBYw:

2635.140913962500057058021829829716326092242159344445256012332899342206308024656889272385026569495095

EBZw:

1294.929820433222525616093711116456839706471341339170453850577036724525505501280651237598221845643896

EB]w:

2047.279677120054326946663928925332111163979920419610240460282280823118299907549767963329235987265221

EB^w:

955.1173957580200950282497523277857896543396471517409861023229202390808815830391724542716171916922013

EBhw:

3915.470339081033526755628220802569350446262533328229994433609007999408468491593010070211347773753071

EBjW:

1638.227643577834922590840158161131741905108621645369609375614917013584042830871300731860081287541737

EBjw:

1249.031253409427948814906460445039379430255979495841929836789046310191772400863152783912457964797616

EBnW:

1242.132551345918150269003717538909244488275474284112976868201221956106676898199763409950540743084897

EBn_:

1573.151856980934808919827158975331388368031961646593906882105843907290706333260795744513417599534490

EBnw:

925.9261727370066008083104968131578336403475961481875936618481207110556397789564439640770014644759016

EB~o:

851.2248620521815665450487666798153681310685833310608077482570549459101780968341502869034045105782828

EB~w:

674.2033558800885599553827237426074770307353315197862522519606139966752333374102153499882056230954189

ECXw:

7860.814461700763010907670357264677307020052200392370242574109573605282306830947419029778544241067207

EC\w:

4261.146889713286735485934396837653296226145100471708951399038847381878723022684441131514353660337322

EENg:

1647.670076196843591079886655347185928334628256216257430992928774239812637189803630589856487331806659

EFz_:

1099.892781389864095266656523739364032553606908110951406883578843894462139457992627376798343455737639

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

EFzw:

615.6118341186009504580938718728425710397654568964473982691707829252919004112669533903349238704590456

EF~w:

476.3642465987234945563231638263518860758608900552076651272769647178493319672691889504088295477171517

EGNW:

3578.347557759405590001110027654344679278921995460311663945916242627160778230662226850137525491049118

EGcw:

23268.21685147475775195422285761911637263347756165707185158628963210667744058937682003995899768664457

EGdo:

42958.93167856354008660459636029963328875114164340547115022550754600732759352597754808044216177016680

EGdw:

5398.546387367163061382601449177526976177731692397337806273431407533901411495170910253527933406342801

EHQW:

6782.677492232632286945325825381960920674513336090651043570816801263131951688834831648854341112264345

EHUW:

5190.934450975364990539465095346126321189712122564141174657644166609313455977305189985579297065217412

EHuw:

1194.224805725937996209485191201639762685994502166840822214879875922132576285814321646338069879749890

EI]w:

1894.100908271440046692174643267840619108534051057606012633660366266267352089704999079504139142780187

EI_w:

21404.22671316953528199591092487537962777181144599224225620526447763451606585103686284605800453540083

EIe_:

8105.488438294332918392179649245467908363345723097752181524206088834848478049565956735182978679065171

comment: This is the cycle $C_6$.

EImo:

2375.731960702656546177873997812792403620432873501271611049470271184373330864203165128131252199286924

EImw:

1841.029010508735435262540515043935612310929907433343303279120417951198822574618062745047990769478587

EIno:

1146.657551283605210473740319831868696462151128740709441395883245587305738656672538563137555497525565

EInw:

889.5544294419987162105817736637417922850373698778526361464601993092523456204780620059518358886977671

EJYW:

3656.495152074822081101204089748680513315043741948448506652907366098438482077069915742830695612991442

EJ]w:

1434.712379209954029062488127077491772931942326795463860029093026897207748808103667354015810210265776

EJ^w:

683.0904973705555460578170626962974284857027219791639631547448162326123757975774706085619363018340209

EJeg:

2375.201032721962241571571621779936895218083725532358609125162738249720022758738346917083593718659722

EJmw:

1399.593472069552901753728092673169846571817860741615868021058829185119980981762401741237170045006858

EJnW:

844.5489072001694550870242916563431757423767172824758147250844356506525834608327317412482040790936324

EJnw:

636.0797884521548413483339100519749527173858924194550939439039587845660544165166119951515781735282900

EJqw:

1145.599024162821092878542784613545932552919120929583074621319260928089662749589495828569514023052169

EJ~o:

605.0928687304603853134918024163473104877213048117016697297736767264805467516590138251404965250669669

EJ~w:

466.9813842017171169536690035594699571114859226034317988854049455244944141186388517126497738353316263

EKNG:

4559.350261355855904188180119743014062709621685668405368489638927625958011278064019346213916328815148

EK\w:

2887.600634820668066100033713809506238476602771017453127146074343422169686730650217443203962053719126

EK]w:

1840.052389441299226363521967571550213530728510601767936214246132643338472158664211230059019522741672

EK^w:

884.5548329535525208705932282614865850941907083446246047244568080417889399586397546298462846388456355

EK`w:

4901.751024261227629505635857803858610012909159950920886912191405703790890154329193657442692331798638

EK~o:

815.9445242990311448635842129434337636267779290382998730486129734054634575805024451945699318557614130

EK~w:

643.4697470287548356137380118018205775757376711832277643141483812003121076539003746479826626189528187

ELpw:

1140.297135948647527155729844577470412012132312003753985821854934791570976268915460139589013815224973

ELrw:

848.9505716009353782179697958747051288244005173908741250146171586516586921352419961425168396340444203

comment: This is the wheel $W_6$.

ELv_:

1098.953616063299688590487579693716463025666097517620718761243186249035976747166303952506819276467791

EL~o:

583.2820762342502749771922080292858678188268049623847369952639568518428254697669362447056517526231509

EL~w:

448.3000081001955380186845037111542505673857440565708369616863418302710380663520524717160276119049165

ENzw:

425.4409137823095588973010963534599381758693724713757568390306206187356621174452394984179501585495938

EN~w:

318.1590442413553749833209853949898667185920156400015212021415890930147868750839117884980630406974427

EPTW:

16260.23864817584769976344963351101003416777084007815319117604948964144421767916683441505930905122227

ER^W:

841.1000247098061043845877594480410857653433008387522376734954586664561454792909601126126324735992952

E]~o:

405.8347993424449606840691790283057328161227919948579302583716649431134007562979613749901810186846359

E]~w:

301.4689923599407621513090017271523866956870161341397027385984104832848846130241110852594669275634161

E^~w:

217.2817328546657657977534058515789790320655247380573141318821691244713579756455930443285494311706904

E_Nw:

1785.126955451363729732622343782499185989922565393790483061438845548978809186024070488790157323553054

E_]o:

2199.822201729650921560542878864119855120864860297005973014487525196123885683180160800996992701733966

E_]w:

1707.612530876357897210212841369570672844980268865561297953433335651271642605028551133038294087648301

E`Lw:

5586.926756369160120158257769474816773880142986590601205752812500883446162841609905664335652125447105

E`NG:

9860.741321840017072906209578700693775979999562797753574955491779683615564650740650437618607646134838

E`NW:

3705.027998501286553819943892339147047497754099113954794566055296814798522073279459056554202628540837

E`Nw:

1243.783069204762823491119745692047075409478099841912427082850211225033431875572109500275077529418712

E`]o:

1566.516976036622516881119928352348587289192424654051656424011388117825616990130463616337619255948667

E`]w:

1183.614173638173284405231042125891833881285873998829741198101046762410968181333144832375290765436724

EaMw:

2453.212319164162917296592061668622055482017310728099945978312282128402633201860023187841286403403226

Ebnw:

610.8061425422281707776824660014152667343495332382607980497762590002213155762641747556638593811923887

Ejmw:

580.0429259146185535890306822355353344551765027317196697815497162514257071981339605060444192150749935

Ek]w:

810.8780388757483514896305222418515627954503225198815740973964167812281301604737535706897129646988731

EoLW:

3212.036923481435148783759837995323370012518996360144104058832186527141780243257704933991344198173252

Es\w:

811.9653566535364688218387157993962514770910323822106635269255977860135044886151978428510306755593887

E~~w:

150.2525563084338150290931988913595839607167232490378282192920291193993722996830750964741458316286194

comment: This is the complete graph $K_6$.

Definition

The distance Estrada index of a connected simple graph $G$ is $\operatorname{DEE}(G)=\sum_{i=1}^{|V(G)|}e^{\mu_i}$, where $\mu_i$ are the eigenvalues of its shortest-path distance matrix, counted with algebraic multiplicity [2].

Parameters

$G$

— graph (a connected simple graph on at least two vertices, identified by its graph6 string after Sage canonical_label(algorithm='sage'))

Formulas

(1)

$\operatorname{DEE}(G)=\operatorname{tr}(\exp(\mathcal D(G)))=\sum_{k=0}^{\infty}\operatorname{tr}(\mathcal D(G)^k)/k!$, where $\mathcal D(G)^0=I_n$ [2] [1].

(2)

For the complete graph $K_n$, $\operatorname{DEE}(K_n)=e^{n-1}+(n-1)e^{-1}$, since its distance eigenvalues are $n-1$ once and $-1$ with multiplicity $n-1$.

(3)

For the complete bipartite graph $K_{a,b}$ with $a,b\geq1$, put $s=\sqrt{a^2-ab+b^2}$. Then $\operatorname{DEE}(K_{a,b})=e^{a+b-2+s}+e^{a+b-2-s}+(a+b-2)e^{-2}$. The vectors constant on each part give the quotient matrix $\begin{pmatrix}2(a-1)&b\\a&2(b-1)\end{pmatrix}$; vectors summing to zero within a part have eigenvalue $-2$.

(4)

For a connected graph on $n\geq2$ vertices, $\operatorname{DEE}(G)>n$ and $e^{\rho_{\mathcal D}(G)}<\operatorname{DEE}(G)<n e^{\rho_{\mathcal D}(G)}$, where $\rho_{\mathcal D}(G)$ is the distance spectral radius. The first inequality follows from strict convexity of the exponential and $\operatorname{tr}\mathcal D(G)=0$.

Comments

(5)

The graph is finite, undirected and unweighted. With $n=|V(G)|$, its distance matrix is $\mathcal D(G)=(d_G(u,v))_{u,v\in V(G)}$, where $d_G(u,v)$ counts edges in a shortest path and $d_G(u,u)=0$.

(6)

Graphs are identified by their graph6 strings [3] after G.canonical_label(algorithm='sage'). Recover a graph with Graph(key, format='graph6'); use a raw string literal for a key containing a backslash. These identities agree with the adjacency characteristic polynomials and the Laplacian polynomials. Entries are ordered by vertex count and then by graph6 string.

(7)

The eigenvalues in the exponential sum are the signed roots of the distance characteristic polynomial, with their multiplicities. Their largest member is the distance spectral radius. The index uses the unscaled distance matrix and is neither centered nor divided by the number of vertices.

(8)

The one-vertex graph has distance Estrada index $1$. For a wheel $W_n$, $n$ is the total number of vertices, including its hub.

(9)

The selection is the complete connected-graph census on two through six vertices [4]. Common graph names annotate 26 entries; the other graphs are identified by their graph6 strings.

Programs

(P1)

Sage

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

G = Graph('CL', format='graph6')  # the path P4
p = G.distance_matrix().charpoly('x')
B = RealBallField(430)
I = RealIntervalField(430)
sum((B(I(r)).exp() * m for r, m in p.roots(ring=AA)), B(0))
# Stable graph identity:
G.canonical_label(algorithm='sage').graph6_string()

References

[1]

Ernesto Estrada, The many facets of the Estrada indices of graphs and networks, SeMA Journal 79 (2022), 57–125, Definition 23 and equation (16.6). (doi)

Links

[2]

A. D. Güngör and Ş. B. Bozkurt, On the Distance Estrada Index of Graphs, Hacettepe Journal of Mathematics and Statistics 38(3) (2009), 277–283, Definition 2.1

[3]

Brendan McKay: graph6 and sparse6 formats

[4]

Brendan McKay: connected graph catalogues

Similar tables

Distance characteristic polynomials of connected graphs — its roots, counted with multiplicity, are the exponents in the distance Estrada index

Distance spectral radii of connected graphs — stores the largest distance eigenvalue for the same graphs

Characteristic polynomials of connected graphs — uses the adjacency matrix with the same canonical graph6 identities

Laplacian polynomials of connected graphs — uses the combinatorial Laplacian with the same canonical graph6 identities

Data properties

Entries are of type: real number

How well the digits are known: proven

digits: 100 (Unknown key)

Table is complete: no (it holds all 142 connected simple graphs on two through six vertices, with counts 1, 2, 6, 21 and 112 by order. This complete small-order reference census covers trees, cyclic graphs, bipartite and non-bipartite graphs, and regular and irregular distance patterns for identifying shortest-path matrix-exponential calculations. Six vertices is a practical, noncanonical boundary; seven would add 853 graphs, mainly extending the census)

How they were obtained:

Each distance matrix and characteristic polynomial is computed over the integers. Certified real algebraic roots are converted to outward-rounded intervals, then exponentiated and summed with their algebraic multiplicities in Arb ball arithmetic. The generator uses 96 guard bits beyond the 100-digit target. The minimum measured relative accuracy was 424 bits, exceeding 127 decimal digits; each stored value claims only 100 significant digits.

An independent checker decodes graph6 directly, computes shortest paths by Floyd-Warshall, and sums $\operatorname{tr}(\mathcal D^k)/k!$ using exact integer powers and rational arithmetic. For $R=\max_v\sum_u d_G(u,v)$ and $N+2>R$, the tail after degree $N$ is bounded by $nR^{N+1}/((N+1)!(1-R/(N+2)))$. The tail is less than $10^{-125}$ for every graph, with degree at most 187. Zero-matrix, identity-matrix, $K_2$ and $P_3$ controls precede the comparison, which agrees on all 142 entries. Every enclosure is checked for finiteness and narrowness.

The complete-graph formula agrees on all 5 cases, the complete-bipartite formula on all 9 cases, and the spectral bounds on all 142 graphs. The distance characteristic polynomials agree exactly with the stored polynomials, and the largest roots agree with the stored distance spectral radii. Trace and squared-trace checks test the root multiplicities. The canonical graph identities agree with an independent nauty census, the adjacency and Laplacian tables, and McKay's counts. The attached generator, independent checks, argument-selection note and numerical evidence reproduce these results.