Adjacency algebra

I algebraisk grafteori är angränsande algebra för en graf G algebra för polynom i angränsande matris A ( G ) i grafen. Det är ett exempel på en matrisalgebra och är mängden av linjära kombinationer av potenser av A .

Vissa andra liknande matematiska objekt kallas också "adjacency algebra".

Egenskaper

G :s närliggande algebra är förknippade med olika spektrala , närliggande och anslutningsegenskaper hos G.

Uttalande . Antalet promenader med längd d mellan hörn i och j är lika med ( i , j )-te elementet i A ^d .

Uttalande . Dimensionen på närliggande algebra för en sammankopplad graf med diametern d är minst d + 1.

Följd . En sammankopplad graf med diameter d har åtminstone d + 1 distinkta egenvärden .