Distance spectral radii of connected graphs

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

Numbers

$G$

$\rho_{\mathcal D}(G)$

A_:

comment: This is the complete graph $K_2$.

BW:

2.732050807568877293527446341505872366942805253810380628055806979451933016908800037081146186757248576

comment: This is the path $P_3$.

Bw:

comment: This is the complete graph $K_3$.

CF:

4.645751311064590590501615753639260425710259183082450180368334459201068823230283627760392886474543611

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

CL:

5.162277660168379331998893544432718533719555139325216826857504852792594438639238221344248108379300295

comment: This is the path $P_4$.

CN:

4.099647729675863158675706515466927602319390690346127273803750827689158883277832141800557412376273377

C]:

comment: This is the cycle $C_4$.

C^:

3.561552812808830274910704927987038512573599612686810217199316786547477173168810796793931825405342148

comment: This is the diamond graph.

C~:

comment: This is the complete graph $K_4$.

D?{:

6.605551275463989293119221267470495946251296573845246212710453056227166948293010445204619082018490718

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

D@s:

7.459294270913428162433205013554037487795044817926997559974706940831408777556070525950059733540536784

D@{:

6.176436314473940161400052549570315708794081228551998666981668935370174219918156562654580826816612427

DBg:

8.288215751900178950371746248678562671344866133244798081722290871373455831531987299124399967819960068

comment: This is the path $P_5$.

DBk:

6.637519478750677316156696280583774841913522961674326189403940151469115887764029425768788465127360627

comment: This is the bull graph.

DB{:

5.759554956003028132093414842872558986575440473758742381839594459818255139180555632039823391844505605

comment: This is the dart graph.

DFw:

5.645751311064590590501615753639260425710259183082450180368334459201068823230283627760392886474543611

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

DF{:

5.372281323269014329925305734109464659110132228991396183849938735282950360728702313513562682798394061

DIk:

6.538120588189747960021694933395472939464804936318637666068341087169715470546716525799027254611097423

DJk:

6.216093478037556083123107398743380015589001798356771276356918801906444630229964359527550111414434658

DJ{:

5.344101953856734878344645526995957078769595652192982726544581295970003080172280804128246391599700512

DK[:

7.008607590101196064398798693505261146041916386456766158552076972131312213525592252405542238541492250

DK{:

5.701562118716424343244108837310906632260210066310509442764636313334091379098438037144677151124934982

comment: This is the butterfly graph.

DLo:

comment: This is the cycle $C_5$.

DL{:

5.292579941397382988462873482806539078290757213908552043130256646814500014700555254282946181667201384

DNw:

5.223861091336562290712446137350899199853715513366496509967119589905337488351075154918039518654610235

DN{:

4.901799616122767589724438396507893410073196227938872470547867866464590020260870190406101946069017205

comment: This is the house X graph.

D]{:

4.828427124746190097603377448419396157139343750753896146353359475981464956924214077700775068655283145

comment: This is the wheel $W_5$.

D^{:

4.449489742783178098197284074705891391965947480656670128432692567250960377457315026539859433104640235

Dbk:

5.635128415952847683392628140931560746756809197267229533769751009289379978389996138031317081911266247

comment: This is the house graph.

D~{:

comment: This is the complete graph $K_5$.

E?Bw:

8.582575694955840006588047193728008488984456576767971902607242123906868425547770886604361559493445033

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

E?Fg:

9.670211018734627189228617714528282628234663854278607846356762400771157566469275270689222319567798188

E?Fw:

8.229715652120553373467794397941149509198491240148617129252458453796052353354843446254494038403950360

E?NG:

E?NW:

8.990900305708534201682537819141873414188355327914355847197855129765655045969610028581973813062396994

E?Nw:

7.888793405231792297363150391889215758177958270756000349894833698927500627537168790783908560826317915

E?]o:

9.656854249492380195206754896838792314278687501507792292706718951962929913848428155401550137310566291

E?]w:

8.288215751900178950371746248678562671344866133244798081722290871373455831531987299124399967819960068

E?^o:

8.146800595958766194490816839838282450465894536561965486208464511578214144547629288282298072338737691

E?^w:

7.567276711409522560638865940600100219492452075976280276012812367876058127367819645952942247081347434

E?~o:

7.464101615137754587054892683011744733885610507620761256111613958903866033817600074162292373514497151

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

E?~w:

7.274917217635374848618342403473058529111097352311690069149313452855360976958905597791226037073761986

E@FG:

11.05878486949216080547708779351584379966310305845069350967229464688083704469526902060289649616480594

E@JW:

8.898979485566356196394568149411782783931894961313340256865385134501920754914630053079718866209280470

E@NW:

8.637759361129662102148483197888900557899877717903538138926609387989050091045836853379650620030344859

E@Nw:

7.554564277386919362774449880271303396069502167737382725675635821475182316982946830625816662751923839

E@QW:

10.74240472910472916908291044199956316489767941661348617768463075654630879070548453925384739483275944

E@Rw:

7.852644393530912526622150298105355938395854109001691956865370786644459093497515401988188096639631198

E@UW:

9.385164807134504031250710491540329556295120161644788837680388670016645962827658692876633781679835484

E@Vw:

7.522196964570767434938017382530367343908765557314464055986180481639900169074654448493116624818980613

E@YO:

12.10931150391298370620983766694289660538155474524907660481956459561042424295026087351713470158328136

comment: This is the path $P_6$.

E@YW:

9.260584690415349079941152017645486242816527934321247053809457608026135454885875756191557845981223551

E@]o:

9.424428900898052360873105707458812240848068143721382085861577264918220291853839315046600392057712881

E@]w:

7.977672660429449279764716873787928499326969873639479215975105361487284104826134408415222711311780577

E@^W:

7.915087677135012970061129449056767430777656847485019486145990871358703197793844751966320615638428774

E@^o:

7.837008155390812238535733671293445267586836945407681360359152134571838306218350888119689783595255319

E@^w:

7.205654436332271207049080263375133036919551090641558966218863569096848957606463334664232094934194396

E@`w:

9.315409046419373184893656775502349769848285107512745154067090098118720941048426274100938186707398030

E@ow:

9.608834688648652451303067349132198607973923492343224453229248580100739725549206494105380553515431137

E@vw:

7.174195006007347579837472047308365407724499255754429636007715560469229558775606301306215631644203245

E@~o:

7.095932280272493380194238705409093674501781282808419785925260536923723757542568790887773730370803540

E@~w:

6.885832006687951845298617196510203419300208176888623062404017188422368780139538943149176038101651526

EAMw:

8.663246504856263300666169628885890720463144153810259657011094709904045947534893129106636025922194529

EA]o:

8.523734714584910083312132158013749129335582764326241938854043089645221103175034341964588604400868337

EBYW:

8.570406330223831502468254715068369576724559332781366595508513465679279688774753347040297470339196649

EBYw:

7.875941589600097236287382761030896550438626384597017222910468321248203970957311912559430830689098689

EBZw:

7.164771202832824124194327792461065992272902281879330224052727465413670664857358440064146620731333210

EB]w:

7.623457321061652831168424141965573978090931624940271961176694868303324707497069048982412131742461810

EB^w:

6.860059361327185542723613553731716743754134896076227544732572170000666315489887295959285164600450690

EBhw:

8.272250914089625927804783360695648020260392052565663416024697921683990861689299591897777375885917437

EBjW:

7.400194923348946833685658168794736823895494067313727301308503512736347822741996805631708297816311873

EBjw:

7.128692311208703592146714993807059432664591884595827086690476311597575623378057195364750153780587838

EBnW:

7.123105625617660549821409855974077025147199225373620434398633573094954346337621593587863650810684297

EBn_:

7.359439711938180839365460011361866893778914411980412204300563768562098985400345353122808968343431066

EBnw:

6.828864774980929667905794366396536913476902363142080109320691794241148731583231915837499324378793120

EB~o:

6.743961887574750560850726629333186485842192601379283958148378190662678590218497610697151982677103159

EB~w:

6.510884131908910698178790570255454006911758511258012788183871982313161967686961711815014791604588480

ECXw:

8.969444711075949187591803286832929014459689648044004886496686843344524801670762746775813160170800768

EC\w:

8.356914314274284520633788500018635632922613917502585330405527486544464846493156466246985726096092680

EENg:

7.405798995206611286163028458593608255754796110218969573393049779489386977560897877486859745398078716

EFz_:

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

EFzw:

6.418832675970042219334093825312152084961129431382511695838707815789712255468079795063241121849676217

EF~w:

6.162277660168379331998893544432718533719555139325216826857504852792594438639238221344248108379300295

EGNW:

8.182150654236994475006362564002466165452199282419406893340735957376894832171118493402620666659105014

EGcw:

10.05477840878375749098355587496485442082587932527640572682842509515272871544867374847162888288268477

EGdo:

10.66796298636623923883474149716228219201580045250911957964717992376108726071992101996794722852038977

EGdw:

8.593600650603732712488925120145674114913733798787511686783007464226811360797879460116751541191782581

EHQW:

8.821870029750567683240300058048975807445655340022576146673553738590704358882348733338351930605328784

EHUW:

8.554312326447793500058619371691290452220079633268971054563990788635106731198900620196099842691574506

EHuw:

7.083495513981662886264185120581187826780476885072403495674916912934891160035103909284072877382351144

EI]w:

7.545472388670554997381672416771862308001230594101176173834728808312117060172207142171041082468624519

EI_w:

9.971258158604132034753567894830528555021754610489722977025589796264347896530968473823813833624636135

EIe_:

comment: This is the cycle $C_6$.

EImo:

7.772001872658765583935824163119853217297227664766641120954325626885824409663649190540486015053504715

EImw:

7.516940184447188676915949294280308012351510067955662026145938301729999121467464606543094727642148027

EIno:

7.042503530717760831210248952032156402742408249401329556630938164777930363869253658043537069779915059

EInw:

6.788444596718009300536725196800827188355907389777955378449343898800245184514965516970038326243553744

EJYW:

8.203702666941517294362591787347178886893961463200912762026189940200631176450925847270379980556515645

EJ]w:

7.267499761734287857670893062963125654616131142707945966861439253323515806256439950589968973651262171

EJ^w:

6.524199596856449985769506149946415873052548914463208417599766061899525407490272084360285122282475577

EJeg:

7.772001872658765583935824163119853217297227664766641120954325626885824409663649190540486015053504715

EJmw:

7.242640687119285146405066172629094235709015626130844219530039213972197435386321116551162602982924718

EJnW:

6.736331326907798122051111778672633446835383700962481000533301932297189703849017417117537207264034748

EJnw:

6.452337379650123670663474484614945418139359611564221793583074680875098528145714518152341167915423020

EJqw:

7.041841636255810501233685160551103535020633327871181677084970773276739137817151795314216980947121903

EJ~o:

6.401723327102481564331370877475360917312881192494227122371657361676311148109009223467764063761012468

EJ~w:

6.142457360426860982974371175813316052427099711323624839031602935476764350819921712950679474132003467

EKNG:

8.424428900898052360873105707458812240848068143721382085861577264918220291853839315046600392057712881

EK\w:

7.967588056209378452379670823870465822647134502183696635589026556713721676837242005206601091069973303

EK]w:

7.516538485191787521369500838674010010643324846946545787137978201021031986419442426823993247805965004

EK^w:

6.783023515112379064477740252122012723352229914482963301860425766504531615296784490776230865593238407

EK`w:

8.496968025764426841840223787923295483248967624928648796254298262586636405124665244290543730447327654

EK~o:

6.701562118716424343244108837310906632260210066310509442764636313334091379098438037144677151124934982

EK~w:

6.464101615137754587054892683011744733885610507620761256111613958903866033817600074162292373514497151

ELpw:

7.037188190781964977296205363519877137417380080077899804807933069751966776283525037252604997699543249

ELrw:

6.741657386773941385583748732316549301756019807778726946303745467320035156306939027976809895194379572

comment: This is the wheel $W_6$.

ELv_:

EL~o:

6.364681864288780538128581263924837610260550074327576979431947169317669756172975378598305759821536095

EL~w:

6.101160353032533717661193469040595983297214967752215127390605539111030738594108655345324258820149902

ENzw:

6.047904976996737742163716383969281044161339546139485124629625582172482823319022836931898636505573337

EN~w:

5.756591308025603270998975945787073160501526529555139398775839250829654611721784750796198757384691739

EPTW:

9.696375622397740570346133988988181739717002740718336754927416262550646170989250684637466527806217463

ER^W:

6.732148054190623977865415792967958060083604475806641809284701122616795658404697927235856415729005485

E]~o:

E]~w:

5.701562118716424343244108837310906632260210066310509442764636313334091379098438037144677151124934982

E^~w:

5.372281323269014329925305734109464659110132228991396183849938735282950360728702313513562682798394061

E_Nw:

7.486354991477194587810544092582420298616950775046712703538138233020529789232377306834588110371089787

E_]o:

7.695199486633531488042820650897823521892277875555972800468500029050274437616837088363272588210083867

E_]w:

7.441739268043944811016935379813314111757068138723987060507981385917704801447787608776867850965759442

E`Lw:

8.627894657894644955633313621753252388763130899973028371585766424770653155835189940179749238994859170

E`NG:

9.196152422706631880582339024517617100828415761431141884167420938355799050726400111243438560271745727

E`NW:

8.216990566028301905660330188811320358491811316707560660331490724490011454792559029270513493445192052

E`Nw:

7.124597730399937290206538842323205202645868279920251608002838682507189555301569230878031761381501038

E`]o:

7.355350340869579713899483992555466160301405405663530334667860235581023044096891224821228503859471970

E`]w:

7.074673582515124999909700639207229149655768890305131583284462717931675053894483650282604193044552183

EaMw:

7.804345859672770990287182619046831708363517408070254310177462709533055198198415686981136961576371635

Ebnw:

6.411381821997608307153884791711556675941324540186737023031897559555320696387555301220295702281961248

Ejmw:

6.358898943540673552236981983859615659137003925232444936890344138159557328203158085656159155851944527

Ek]w:

6.695265165690463668457504628088737706837499318954419150171925630980501052614879528546353923469763702

EoLW:

8.074065501057913616329703499494772306880808815383812708551950813010665461034138872864632674844301072

Es\w:

6.696099695490513414298842649161240311132292160789810095310187181242567553034343850100182572849175248

E~~w:

comment: This is the complete graph $K_6$.

Definition

The distance spectral radius $\rho_{\mathcal D}(G)$ of a finite, simple, undirected, connected, unweighted graph $G$ is the largest eigenvalue of its distance matrix $\mathcal D(G)=(d_G(u,v))_{u,v\in V(G)}$, where $d_G(u,v)$ is the number of edges in a shortest path from $u$ to $v$ and $d_G(u,u)=0$ [1].

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)

$\rho_{\mathcal D}(G)$ is the largest real root of $\det(xI-\mathcal D(G))$.

(2)

Write $t_v=\sum_{u\in V(G)}d_G(u,v)$ for the transmission of vertex $v$. Then $\min_v t_v\leq\rho_{\mathcal D}(G)\leq\max_v t_v$. If every transmission equals $t$, then $\rho_{\mathcal D}(G)=t$ [2].

(3)

For the complete graph $K_n$, $\rho_{\mathcal D}(K_n)=n-1$. For the cycle $C_n$, $\rho_{\mathcal D}(C_n)=\lfloor n^2/4\rfloor$ for $n\geq3$ [2].

(4)

For the complete bipartite graph $K_{a,b}$ with $a,b\geq1$, $\rho_{\mathcal D}(K_{a,b})=a+b-2+\sqrt{a^2-ab+b^2}$. The two parts give the quotient matrix $\begin{pmatrix}2(a-1)&b\\a&2(b-1)\end{pmatrix}$, whose larger eigenvalue is this expression [2].

(5)

If $G$ is $r$-regular on $n$ vertices and has diameter at most two, then $\rho_{\mathcal D}(G)=2(n-1)-r$ [1].

(6)

Ordering the vertices of the path $P_n$ along the path gives $\mathcal D(P_n)_{ij}=|i-j|$. Thus $\rho_{\mathcal D}(P_n)$ equals the largest eigenvalue of the Fiedler matrix in the classical symmetric test matrices.

Comments

(7)

Each graph is identified by its graph6 string [3] after G.canonical_label(algorithm='sage'). Recover it with Graph(key, format='graph6'); quote literal graph6 strings as raw strings if they contain 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.

(8)

The matrix $\mathcal D(G)$ is nonnegative, symmetric and irreducible. Its largest eigenvalue is positive, simple, and equal to the maximum absolute value of its eigenvalues [1]. The eigenvalues themselves can include zero and more than one positive value. The one-vertex graph has distance spectral radius $0$.

(9)

The distance matrix uses shortest-path edge counts. It differs from the adjacency matrix used for adjacency spectral radii and from the resistance distances used for Kirchhoff indices. In a wheel $W_n$, $n$ is the total number of vertices, including its hub.

(10)

The selected graphs form 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.rational_field import QQ
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()
rho = max(p.roots(ring=AA, multiplicities=False))
QQ(rho) if rho in QQ else RealBallField(400)(RealIntervalField(400)(rho))
# Stable graph identity:
G.canonical_label(algorithm='sage').graph6_string()

References

[1]

Bo Zhou and Aleksandar Ilić, On distance spectral radius and distance energy of graphs (2011), Sections 1 and 2. (arXiv)

[2]

Leslie Hogben and Carolyn Reinhart, Spectra of variants of distance matrices of graphs and digraphs: a survey (2021), Sections 1, 2, 5 and 6. (arXiv)

Links

[3]

Brendan McKay: graph6 and sparse6 formats

[4]

Brendan McKay: connected graph catalogues

Similar tables

Spectral radii of connected graphs — stores the largest adjacency eigenvalue for graphs indexed by the same canonical graph6 strings

Characteristic polynomials of connected graphs — stores characteristic polynomials of the adjacency matrices for the same graph identities

Laplacian polynomials of connected graphs — stores characteristic polynomials of the combinatorial Laplacians for the same graph identities

Kirchhoff indices of connected graphs — sums resistance distances over unordered vertex pairs for graphs with the same identities

Eigenvalues of the classical symmetric test matrices — its largest Fiedler eigenvalues equal the distance spectral radii of paths

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 supports identification of shortest-path spectral calculations across trees, cyclic graphs, bipartite and non-bipartite graphs, and regular and irregular distance patterns. Six vertices is a practical, noncanonical boundary; seven would add 853 graphs, mostly extending the census)

How they were obtained:

The attached generator builds each integer distance matrix and its characteristic polynomial exactly, isolates all roots with multiplicities in Sage's algebraic real field, and selects the largest root exactly. The 12 rational radii are integers and are written exactly. The other 130 roots are enclosed in real intervals and converted to real balls at 397 bits, comprising the precision for 100 decimal digits and 64 guard bits. The smallest measured relative precision of these enclosures is at least 393 bits.

An independent checker decodes graph6 directly, computes shortest paths with Floyd-Warshall, and obtains exact rational Collatz-Wielandt bounds from positive integer power iterates. It requires relative width at most $10^{-115}$ and checks containment in every written decimal interval. Exact $K_2$ and $K_3$ controls and the value $1+\sqrt3$ for $P_3$ precede this check. All 142 characteristic polynomials also agree with direct permutation expansions. The tree determinant and inertia identities agree on all 13 trees. The complete-graph, cycle, complete-bipartite, constant-transmission and regular-diameter-at-most-two formulas agree on every applicable selected graph. The five paths agree with the stored largest Fiedler eigenvalues.

The selected canonical graph6 identities match the corresponding keys of the adjacency and Laplacian polynomial tables, an independent nauty enumeration, and McKay's connected graph catalogues. The attached argument-selection.md explains the discrete family and the finite reference boundary.