Gráfok Laplace-spektruma
Bevezetés

Egy irányított vagy irányítatlan gráf (G) spekrtumán a gráfhoz rendelt mátrix sajátértékeinek halmazát értjük. A gráfokhoz többféle mátrixokat redelhetünk: a legegyszerűbb a szomszédossági mátrix (jele A), amely egy n×n méretű mátrix, amely főátlójában 0-k vannak, és az i.sor j.eleme egyenlő 1-gyel ha az i. és j.csúcs között él fut, egyébként 0. (n a gráf csúcsainak száma). Mi a gráfok Laplace-mátrixával fogunk foglalkozni, (jele L), amelyet a következőképpen definiálhatunk: L=D-A, ahol D egy diagonális mátrix, amelynek főátlóiban az egyes csúcsok fokszámai állnak. A gráfokat a szomszédossági mátrixukkal adjuk meg, és ebből állítunk elő gráf objektumot.

l={{0,1,1,0,1},{1,0,0,0,1},{1,0,0,1,1},{0,0,1,0,1},{1,1,1,1,0}}

AdjacencyGraph[l]

Laplace[g_]:=DiagonalMatrix[VertexDegree[g]]-AdjacencyMatrix[g]//MatrixForm

Laplace[CompleteGraph[5]]

Az L mátrix sajátértékeit fogjuk vizsgálni: jelöljük ezeket (Subscript[λ, 1])≤(Subscript[λ, 2])≤...(Subscript[λ, n]) módon. Mivel L minden sorában az elemek összege 0, így a mátrixnak sajátértéke a 0, és a hozzá tartozó sajátvektor a csupa 1-est tartalmazó vektor.

Laplace2[g_]:=DiagonalMatrix[VertexDegree[g]]-AdjacencyMatrix[g]

Spektrum[g_]:=Sort[Eigenvalues[Laplace2[g]],#1<#2 &]

Svektor[g_]:=Reverse[Eigenvectors[Laplace2[g]]]

A Laplace-mátrix második legkisebb sajátértékére (Subscript[λ, 2])-re fogunk fókuszálni, és ezen sajátérték alapján szeretnék a gráfokat jellemző paraméterekről mondani valamit. Először megjegyezzük, hogy (Subscript[λ, 2]) értéke mindig kisebb egyenlő, mint a gráfbeli maximális fokszám, kivéve a teljes gráfot, amikor (Subscript[λ, 2]) értéke a maximális fokszámnál eggyel nagyobb.

Spektrum[CompleteGraph[5]]

Néhány nevezetes gráftípusra (Subscript[λ, 2]) értéke:

sertek={CompleteGraph[7],CycleGraph[6],PathGraph[{1,2,3,4,5,6}],StarGraph[6],CompleteGraph[{3,5}]}

Map[Spektrum,sertek][[All,2]]

Általánosságban a következőt mondhtajuk n pontú gráf esetén (Subscript[λ, 2]) értékéről ezeknél a gráftípusoknál:

n csúcsú út - (Subscript[P, n])                                           (Subscript[λ, 2])((Subscript[P, n]))=2*(1-cos(π/n))

n csúcsú kör - (Subscript[C, n])                                         (Subscript[λ, 2])((Subscript[C, n]))=2*(1-cos(2π/n))

n  csúcsú teljes gráf - (Subscript[K, n])                              (Subscript[λ, 2])((Subscript[K, n]))=n

n+m  csúcsú teljes páros gráf - (Subscript[K, n,m])         (Subscript[λ, 2])((Subscript[K, n,m]))=min (n,m)

n csúcsú csillag - (Subscript[S, n])                                     (Subscript[λ, 2])((Subscript[S, n]))=1

A gráf Laplace-mátrixának és sajátértékeinek vizsgálatát - pusztán az érdekessége mellett - az is motiválhatja, hogy a (Subscript[λ, 2])-ről gyűjtött információkat, tulajdonságokat összehasonlíthassuk a folytonos Laplace-operátorról  (Δ) ismert állításokkal.

Laplace-mátrix és összefüggőség

Azt már láttuk, hogy a Laplace-mátrix legkisebb sajátértéke 0. Felmerül kérdés, hogy mit jelent, ha a 0 többszörös sajátérték. Erre a következőképpen kaphatunk választ: hagyjuk el L-ből az i.sort és a j.oszlopot. Jelölje az így kapott mátrixot (Subscript[L, [i,j]]). Ekkor (((-1))^(i+j))*det((Subscript[L, [i,j]]))=t(G), ahol t(G) jelöli a G gráf feszítőfáinak számát.

t[g_]:=Det[Drop[Laplace2[g],{1},{1}]]

Ebből rögtön következik, hogy (∏_(i=2)^n)(Subscript[λ, i ])=n*t(G), és így (Subscript[λ, 2])pontosan akkor 0, ha a gráf nem összefüggő.

t2[g_]:=Times@@Drop[Sort[Eigenvalues[Laplace2[g]]],1]/Dimensions[Laplace2[g]][[1]]

Összefüggő[g_]:=If[Spektrum[g][[2] ]==0,False,True]

Így a gráf összefüggősége és (Subscript[λ, 2]) értéke között erős kapcsolat van: szemléletesen, ha (Subscript[λ, 2]) értéke nagy akkor a gráfot nehéz nem összefüggővé tenni, és fordítva ugyanígy: kis (Subscript[λ, 2]) esetén könnyen komponensekre bontható a gráf. Továbbá az is igaz, hogy a gráf összefüggő komponenseinek száma megegyezik a Laplace-mátrixában a 0 sajátérték multiplicitásával.

Komponensszam[g_]:=Count[Spektrum[g],0]

rg1=RandomGraph[{10,5}]

Komponensszam[rg1]

Az összefüggőség vizsgálatakor érdemes foglalkozni a gráf komplementerével is: ha G komplementerét (G^c)-vel jelöljük, akkor L(G)+L((G^c))=n*I-J, ahol I a megfelelő méretű egységmátrixot, míg J a csupa 1-esekből álló mátrixot jelöli. Így ha x sajátvektora L(G)-nek λ sajátértékkel, akkor x sajátvektora L((G^c))-nek is n-λ sajátértékkel. Így a következő összefüggés teljesül a gráf és komplementerének sajátértékeire: (Subscript[λ, j])((G^c)) = n-(Subscript[λ, n+2-j])(G), minden 2≤j≤n esetén. Ebből az is következik, hogy (Subscript[λ, n])≤n egyenlőség pedig pontosan akkor áll fenn, ha (G^c) nem összefüggő.

Izoperimetrikus szám

Egy gráf izoperimetrikus számát ( jele h )  a következőképpen definiáljuk: h=min ( |σX|/|X| ), ahol a minimumot minden olyan X ⊆V(G) halmazra vesszük, ahol X mérete legfeljebb a csúcsszám fele, σX pedig azon élek halmaza, amelyeknek pontosan egy végpontja X-beli. Rögtön adódik, hogy h - (Subscript[λ, 2])-höz hasonlóan - pontosan akkor 0 , ha a gráf nem összefüggő. Figyeljük meg azonban, hogy h  -t erősen befolyásolhatják a gráf lokális tulajdonságai: a gráf legnagyobb része lehet “erősen-összefüggő”, de ha a gráfban találunk olyan csúcsot, vagy csúcsokat, amelyek kevésbé kötődnek a gráf többi részéhez, akkor h értéke erre a “gyenge pontra” fog utalni. Például, ha két n csúcsú teljes gráfot egy éllel összekötünk, akkor az izoperimetrikus szám értéke 1/n lesz az így kapott gráfon, ez megegyezik az n csúcsú út izoperimetrikus számával.

Izoperimetrikusszam[G_]:=Module[{i,j,l,m,n},
      n={};
      l=Select[Subsets[VertexList[G]],Length[Subsets[VertexList[G]][[#]]]<=Length[VertexList[G]]/2&];
      m=Drop[l,1];
                          For[i=1,i≤Length[m],i++,AppendTo[n,(1/Length[m[[i]]])*(Sum[VertexDegree[G,j],{j,m[[i]]}]-2*Length[EdgeList[Subgraph[G,{m[[i,All]]}]]])]];Min[n]]

Bizonyos gráfokra az izoperimetrikus szám értéke:

hertekei={CompleteGraph[6],CycleGraph[6],PathGraph[{1,2,3,4,5,6}],StarGraph[6],CompleteGraph[{3,5}]}

Map[Izoperimetrikusszam,hertekei]

Általánosságban a következőt mondhatjuk h értékeiről bizonyos gráftípusoknál:

n csúcsú út - (Subscript[P, n])                                           h((Subscript[P, n]))=1/⌊n/2⌋

n csúcsú kör - (Subscript[C, n])                                         h((Subscript[C, n]))=2/⌊n/2⌋

n  csúcsú teljes gráf - (Subscript[K, n])                              h((Subscript[K, n]))=⌈n/2⌉

n+m  csúcsú teljes páros gráf - (Subscript[K, n,m])         h((Subscript[K, n,m]))=⌈m*n/2⌉/⌊(m+n)/2⌋

n csúcsú csillag - (Subscript[S, n])                                     h((Subscript[S, n]))=1

Könnyen látható, hogy h értéke felülről becsülható a minimális fokszámmal és a csúcsszám felének felső egészrészével, továbbá, ha a gráf összefüggő, akkor h értéke legalább 1/⌊n/2⌋.  Intuitívan úgy sejtjük, hogy (Subscript[λ, 2]) és h  értékei hasonlóan változnak: mindkettő növekszik, ha a gráf “jobban” összefüggő, és mindkettő csökken, ha a gráf  ”kevésbé” összefüggő. Ezt a sejtést a következő állítások igazolják: Minden G gráfra (Subscript[λ, 2])/2 ⩽ h(G), továbbá, ha G nem egyezik meg (Subscript[K, 1]),(Subscript[K, 2]),(Subscript[K, 3]) egyikével sem, akkor h(G)⩽(Sqrt[(Subscript[λ, 2])(2*Δ-(Subscript[λ, 2]))]), ahol Δ jelöli a gráf maximális fokszámát. Ez azt eredményezi, hogy kis (Subscript[λ, 2]) értékek esetén a gráfban található a gráf többi részéhez kevéssé kötődő csúcshalmaz, míg olyan gráfok esetén, ahol nincs ilyen jellegú csúcshalmaz, ott (Subscript[λ, 2]) értéke nagy. Megjegyezzük még, hogy egy tetszőleges gráfra h megkomponálása nehéz feladat - párhuzamos élekkel rendelkező gráfokra NP-nehéz. Így leginkább (Subscript[λ, 2])-vel tudjuk könnyen felülről becsülni h-t.

Az összefüggőség kapcsán még megjegyezzük, hogy (Subscript[λ, 2]) értéke legfeljeb akkora, mint azon miniális csúcsok száma, amelyeket elhagyva a gráf már nem lesz  összefüggő. Ez abból a tulajdonságból következik, hogy (Subscript[λ, 2]) értéke nem növekszik, ha a gráfból éleket hagyunk el.  Például egy korábban már látott gráfra (Subscript[λ, 2]) értéke 3 - (Sqrt[2]), ami kisebb, mint 2, és a gráfból legalább ennyi csúcsot kell elhagyni, hogy ne maradjon összefüggő. Továbbá éleket elhagyva (Subscript[λ, 2]) értéke csak csökkenhet, és ha egy élt elhagyva a gráf több komponensre esik szét, akkor (Subscript[λ, 2])=0 fog teljesülni.

l={{0,1,1,0,1},{1,0,0,0,1},{1,0,0,1,1},{0,0,1,0,1},{1,1,1,1,0}}

AdjacencyGraph[l]

Spektrum[AdjacencyGraph[l]]

Spektrum[EdgeDelete[AdjacencyGraph[l],{1<->5,3<->5,2<->1}]]

Spektrum[EdgeDelete[AdjacencyGraph[l],{1<->5,3<->5,2<->1,2<->5}]]

EdgeDelete[AdjacencyGraph[l],{1<->5,3<->5,2<->1,2<->5}]

Laplace sajátértékek és a gráfokon végzett műveletek kapcsolata

Azzal fogunk foglalkozni, hogy hogyan változik egy gráf Laplace-sajátértékeinek halmaza, az egyes sajátértékek mulitplicitása, ha a gráfon különböző műveleteket hajtunk végre (éleket hagyunk el, két diszjunkt gráfot egy éllel összekötünk,stb. ), vagy, hogy éppen milyen műveletekre invariáns a Laplace spektrum. Először megjegyezzük, hogy a felsorolt tulajdonságok egy része a mátrixhoz tartozó sajátérték és sajátvektor foszámokhoz kapcsolódó összefüggéséből adódik, miszerint ha λ sajátértéke L-nek x pedig egy ehhez tartozó sajátvektor, akkor ((Subscript[d, j])-λ)*(Subscript[x, j])=(∑_(i∼j))(Subscript[x, i]), ahol (Subscript[d, j]) jelöli a j. csúcs fokszámát, (Subscript[x, j]) a sajátvektor j. komponensét, i∼j pedig azt, hogy a gráfban az i. és j. csúcs között él fut.

Tekintsünk először két diszjunkt G1 és H1 gráfokat, és vegyük ezeknek az összegét (G1+H1), mely gráf csúcsainak és éleinek halmaza a két diszjunkt gráf csúcs és élhalmazának uniója.

g1=AdjacencyGraph[{{0,1,0,1,0},{1,0,0,0,1},{0,0,0,1,1},{1,0,1,0,0},{0,1,1,0,0}}]

h1=AdjacencyGraph[{{0,1,1},{1,0,0},{1,0,0}}]

l1=GraphDisjointUnion[h1,g1];
GraphPlot[l1]

Map[Spektrum, {g1,h1,l1}]//MatrixForm

Vagyis a diszjunkt unió során keletkezett gráf spektruma egyszerűen úgy adódik, hogy külön-külön vesszük a két gráf spekrtumát, és ezen sajátértékek összessége lesz az új gráf spektruma.

Tekintsük most (Subscript[S, k])-t, azaz a k csúcsú csillagot. Ennek a gráfnak a legnagyobb sajátértéke k, és ez egyszeres sajátérték. Legyen G egy tetszőleges gráf, és képezzük a G' gráfot úgy, hogy egy éllel összekötjük G egy tetszőleges csúcsát (Subscript[S, k]) egy tetszőleges csúcsával. Mit mondhatunk ekkor G és G'  k sajátértékéről, és annak multiplicitásáról. Tekintsük a következő példákat:

g2=StarGraph[5];
h2=CompleteGraph[5];
l2=EdgeAdd[GraphDisjointUnion[g2,h2],2<->8]

Spektrum[h2]

Spektrum[l2]

Tehát, ha G-nek m -szeres sajátértéke a k, akkor ha G-he hozzácsatolunk egy (Subscript[S, k])-t, akkor az így keletkezett gráfnak is m -szeres sajátétéke lesz k. Ha pedig G- nek knem volt sajátértéke, akkor a fenti módon képezett G' -nek sem lesz az, ahogy ezt az alábbi példa mutatja.

h3=AdjacencyGraph[{{0,0,0,0,0},{0,0,1,0,0},{0,1,0,1,1},{0,0,1,0,1},{0,0,1,1,0}}];
l3=EdgeAdd[GraphDisjointUnion[h3,g2],3<->7]

Spektrum[h3]

Spektrum[l3]

Hogyan tudjuk ezt hasznosítani? Tekintsük a következő gráfot:

l4=Graph[{1<->2,2<->4,3<->4,4<->5,5<->6,6<->8,8<->7,5<->7,7<->9,8<->10,9<->11,10<->12,12<->14,14<->13,13<->15,14<->16}]

Sajátértéke-e a 2 ennek a gráfnak, és ha igen, mekkora a multiplicitása?  Ezt önmagában nehéz megállapítani, de az elősző tulajdonság miatt a gráfból elhagyhatunk (Subscript[S, 2]) gráfokat anélkül, hogy a 2 sajátérték multiplicitása megváltozna. Így a fenti gráfból a következőt kapjuk.

h4=VertexDelete[l4,_?(#≤4||#≥9&)]

Ez pedig a négypontú kör, aminek a sajátértékeit már könnyebben meghatározhatjuk:

Spektrum[h4]

És valóban:

Select[Spektrum[l4],IntegerQ[#]&]

Tekintsük most (Subscript[P, 3])-at, azaz a 3 pontú utat. Ezen gráf sajátértékei a 0,1 és a 3. Legyen G egy tetszőleges gráf, és képezzük G' -t úgy, hogy G -nek egy tetszőleges csúcsát összekötjük (Subscript[P, 3]) egy levelével. Mit mondhatunk ekkor az 1 sajátértékről illetve annak multiplicitásáról G-ben és G'-ben? Tekintsük a következő példákat.

g5=Graph[{1<->2,1<->4,2<->3,1<->3,1<->5,1<->6}];
h5=EdgeAdd[GraphDisjointUnion[g5,PathGraph[{1,2,3}]],6<->7]

Spektrum[g5]

Count[Spektrum[h5],1]

Tehát, ha egy gráfnak k- szoros sajátértéke volt az 1, akkor ha a gráfhoz hozzácsatolunk vagy tőle elvonunk (Subscript[P, 3]) gráfokat, akkor a keletkező gráfnak is k-szoros sajátértéke lesz az 1, és ez igaz a k=0 esetre is. Ezeket felhasználva már könnyedén meg tudjuk határozni, hogy a következő gráfnak az 1 és a 3 hányszoros sajátértéke. ( (Subscript[P, 3])-ak törlésével egy hat csúcsú kört kapunk)

g6=Graph[{1<->2,2<->3,4<->5,5<->6,6<->9,9<->8,8<->7,6<->10,3<->10,10<->11,11<->12,12<->15,15<->14,14<->13,13<->10,15<->16,16<->17,17<->18,18<->19,19<->20,20<->21}]

h6=VertexDelete[g6,_?(#≤9||#≥16&)]

Spektrum[h6]
Select[Spektrum[g6],IntegerQ[#]&]

Megjegyezzük, hogy ha egy tetszőleges G gráf egy csúcsát (Subscript[P, 3]) egyetlen nem levelével kötjük össze, akkor az így keletkező gráfra igaz, hogy ha G-ben az 1 k-szoros sajátérték, akkor az új gráfban az 1 sajátérték multiplicitása k és k+2 között van, és mindhárom lehetőség előfordulhat.

Tekintsünk most egy λ sajátértékhez tartozó x sajátvektort, és tegyük fel, hogy x-nek van két olyan komponense, amik megegyeznek. Mit mondhatunk arról a gráfról, amit úgy kapunk, hogy az ennek a két komponensnek megfelelő két csúcsot egy éllel összekötjük, vagy a köztük lévő élet töröljük, attól függően, hogy eredetileg be volt-e húzva ez az él. Tekintsük a következő példát:

g5

Spektrum[g5]
Svektor[g5]

Látható, hogy béldául a  λ =6 sajátértékhez tartozó x sajátvektorra (Subscript[x, 2])=(Subscript[x, 4]). Kössük össze ezt a két csúcsot.

gg5=EdgeAdd[g5,2<->4]
Spektrum[gg5]
Svektor[gg5]

Tehát az így kapott gráfnak x szintén sajátvektora lesz, és ugyanazon  λ sajátértékhez fog tartozni. A sajátértékek és sajátvektorok ezen kapcsolatából arra következtethetünk, hogy ha egy adott G gráf két másolatának megfelelő csúcsait összekötjük, akkor az így kapott  G' gráfra a következők igazak: ha  λ k-szoros sajátértéke G-nek, akkor  λ legalább k-szoros sajátértéke G'-nek, és G minden x sajátvektora kiterjeszthető G' sajátvektorává úgy, hogy x- et kétszer egymás után írjuk. Nézzük erre a következő példát:

g6=AdjacencyGraph[{{0,0,1,1,0,1},{0,0,0,1,1,1},{1,0,0,1,0,1},{1,1,1,0,1,0},{0,1,0,1,0,1},{1,1,1,0,1,0}}]
Spektrum[g6]
Svektor[g6]

h6=EdgeAdd[GraphDisjointUnion[g6,g6],3<->9]
Select[Spektrum[h6],IntegerQ[#]&]
Svektor[h6]//N

Ehhez hasonló tulajdonság a következő: legyen λ a G gráf olyan sajátértéke, amihez tartozó x sajátvektornak van olyan j komponense, hogy (Subscript[x, j])=0. Legyen G' egy tetszőleges gráf, és kössük össze ennek egy csúcsát G j csúcsával. Az így kapott gráfról a következőket mondhatjuk: a gráfnak sajátértéke lesz λ és a hozzá tartozó sajátvektor az x-nek kiterjesztése lesz úgy, hogy a hozzácsatolt gráf csúcsain x 0-t vesz fel.  A példában a λ=3 sajátértéket vizsgáljuk, és a 3-as csúcshoz csatolunk egy gráfot.

g7=AdjacencyGraph[{{0,1,0,0,1,1},{1,0,1,1,0,0},{0,1,0,1,0,0},{0,1,1,0,1,0},{1,0,0,1,0,1},{1,0,0,0,1,0}}]
Spektrum[g7]
Svektor[g7]

h7=AdjacencyGraph[{{0,1,0,0,1},{1,0,1,1,1},{0,1,0,0,1},{0,1,0,0,1},{1,1,1,1,0}}]

l7=EdgeAdd[GraphDisjointUnion[g7,h7],3<->9]
Spektrum[l7][[6]]
Svektor[l7][[6]]

Ennél az előző tulajdonságnál kihasználtuk, hogy G egy olyan csúcsához csatolunk egy tetszőleges gráfot, amely csúcshoz van olyan sajátvektor, amelyben a csúcsnak megfelelő komponens 0. Mit mondhatunk akkor, ha G tetszőleges tulajdonsűgú csúcsához csatolunk egy gráfot? Ekkor kevesebbet álíthatunk: ha λ G-nek k-szoros sajátértéke, akkor egy tetszőleges H gráf G tetszőleges csúcsához való hozzácsatolása során keletkezett  G' gráfra az teljesül, hogy λ legalább k-1-szeres sajátértéke G'-nek, és a hozzá tartozó sajátvektorokat úgy kaphatjuk, hogy a G-beli sajátvektort kiegészítjük nullákkal a H-nak megfelelő csúcsokon. Ehhez hasonlít a következő tulajdonság: ha most λ egyszeres sajátértéke egy H gráfnak, és  a hozzá tartozó sajátvektornak (x) van olyan komponense, hogy (Subscript[x, u])≠0, akkor ha egy tetszőleges G gráfot H-nak u csúcsához kötjük, akkor az így keletkezett gráfban és G-ben meg fog egyezni a λ sajátérték multiplicitása.

Tekintsük most a következőt: legyen G tetszőleges gráf és X csúcsainak tetszőleges nem üres részhalmaza. Legyen (Subscript[G, X])a következő gráf: a csúcsai legyenek X csúcsai, és azok a G-beli csúcsok, amelyekből él vezet egy X-beli csúcsba; élei pedig G  azon élei legyenek, amiknek van X-beli végpontja. Tegyük fel, hogy x sajátvektora (Subscript[G, X])λ sajátértékének úgy, hogy x csak X-beli csúcsokon nem nulla. Ekkor x kiterjeszthető G sajátvektorává - x a többi csúcson 0- t vesz fel - és a λ sajátértékhez fog tartozni. Vizsgáljuk ezt a  következő gráfon: alkossa az X halmazt az 1.és a 3. csúcs. Ekkor (Subscript[G, X]).et az eredeti gráf {1,3,4,6} csúcsai fogják alkotni, és köztük minden él be lesz húzva, ami G-ben be van húzva.

GraphPlot[g6,VertexLabeling->True]

g66=VertexDelete[g6,{2,5}]
Spektrum[g66]
Svektor[g66]

Így ebben az esetben (Subscript[G, X])sajátvektorai között csak egy olyan van amely csak X-beli csúcsokon nem nulla, ez a (-1,1,0,0), ami a 4 sajátértékhez tartozik. Tekintsük most az eredeti gráf spektrumát:

Spektrum[g6]
Svektor[g6]

Látható, hogy a 4 itt is sajátérték, és a hozzá tartozó sajátvektor (-1,0,1,0,0,0) éppen a (Subscript[G, X])-beli sajátvektor kiterjesztése.

Fokszámsorozatok

A következőt fogjuk vizsgálni: legyen G egy n csúcsú gráf, (Subscript[p, 1]),(Subscript[p, 2]),...,(Subscript[p, n]) pedig egy pozitív egész számokból álló nem csökkenő sorozat. A kérdés az, hogy ez a sorozat mikor lehet egy gráfbeli csúcsok fokszámainak sorozata, és ennek ismeretében mit mondhatunk a gráf Laplace-sajátértékeiről.
Definiáljuk egy ilyen p=[(Subscript[p, 1]),(Subscript[p, 2]),...,(Subscript[p, n])] sorozat (SuperStar[p]) transzponáltját, mely sorozat i. eleme legyen azon p-beli elemek száma, amelyek nagyobbak i-nél. Így a gráfokra vonatkozóan a p sorozat i. eleme a gráf i. csúcsának fokszámát adja, míg a (SuperStar[p]) sorozat i. eleme megadja, hogy hány olyan csúcs van a gráfban, aminek a fokszáma legalább i. Egy p sorozat nyoma legyen a következő: tr(p)=|{ i | (Subscript[p, i])⩾ i }|.  Tekintsünk egy példát:

tp[p_]:=Module[{k,l,i},
                 l={};
                For[i=1,i≤Length[p],i++,AppendTo[l,Length[Select[p,#≥i&]]]];Select[l,#>0&]]

tr[p_]:=Module[{s,i},
           s=0;
            For[i=1,i≤Length[p],i++,If[p[[i]]≥i,s++]];s]

p={5,4,3,3,2,1}

tp[p]

tr[p]

Világos, hogy ahhoz, hogy egy p sorozat valóban egy gráf csúcsainak a  fokszámsorozata legyen, a sorozatban szereplő számok összegének párosnak kell lennie, és a sorozat első tagja nem lehet nagyobb, mint az utána következő elemek száma. Az előbbi definíciók segítségével többet is mondhatunk: egy p=[(Subscript[p, 1]),(Subscript[p, 2]),...,(Subscript[p, n])]  sorozat egy egyszerű hurokélmentes gráf fokszámainak felel meg pontosan akkor, ha ∀ 1⩽k⩽tr(p) esetén (∑_(i=1)^k)(Subscript[p, i]^( * ))⩾(∑_(i=1)^k)((Subscript[p, i])+1). Így láthatjuk, hogy az előbbi p=[5,4,3,3,2,1] sorozat valóban egy gráfhoz tartozik, sőt az állításban szereplő egyenlőségek mindegyike egyenlőséggel teljesül. Mit mondhatunk az ilyen gráfokról? Az állításban szereplő első egyenlőtlenség miatt ezen gráfokban a maximális fokszám csúcsszám -1-gyel egyezik meg, így az ilyen gráfok mindig összefüggők. Vizsgáljuk meg a Laplace-sajátértékeit:

pp=AdjacencyGraph[{{0,1,1,1,1,1},{1,0,1,1,1,0},{1,1,0,1,0,0},{1,1,1,0,0,0},{1,1,0,0,0,0},{1,0,0,0,0,0}}]

VertexDegree[pp]

tp[p]

Spektrum[pp]

Vagyis ezen gráfok esetén a gráf nemnulla sajátértékei megegyeznek a fokszámsorozatának transzponáltjával. Így az ilyen gráfok egyértelműen meghatározottak a fokszámsorozatuk  - és így a Laplace sajátértékeik- által. Tehát az ilyen gráfok speciálisak ebből a szempontból, mert általában nem ez a helyzet - a gráf fokszámsorozata, vagy sajátértékei nem határozzák meg egyértelműen a gráfot. Tekintsük erre a következő példákat:

s=GraphDisjointUnion[CompleteGraph[{2,3}],CompleteGraph[{2,3}]];
s1=EdgeAdd[s,{5<->10,3<->8,4<->9}];
s11=VertexAdd[s1,11]

t1=GraphDisjointUnion[CompleteGraph[{2,3}],GraphComplement[VertexAdd[CompleteGraph[{2,3}],6]]]

Spektrum[t1]
Spektrum[s11]

VertexDegree[t1]
VertexDegree[s11]

Így konstruáltunk két olyan gráfot, amiknek a Laplace spektruma megegyezik, de a két gráf nem izomorf egymással. Most megmutatjuk, hogy a fokszámsorozat mennyire nem határozza meg a gráfot: azonos fokszámsorozathoz két nem izomorf gráfot adunk meg, amik Laplace spektruma is különbözik.

s2=AdjacencyGraph[{{0,1,1,0,0,1},{1,0,1,0,0,1},{1,1,0,0,1,0},{0,0,0,0,1,1},{0,0,1,1,0,0},{1,1,0,1,0,0}}]

s22=AdjacencyGraph[{{0,1,1,1,0,0},{1,0,0,1,0,1},{1,0,0,0,1,1},{1,1,0,0,0,0},{0,0,1,0,0,1},{0,1,1,0,1,0}}]

VertexDegree[s2]
VertexDegree[s22]

Spektrum[s2]
Spektrum[s22]
IsomorphicGraphQ[s2,s22]