Lägsta rankning av en graf

I matematik är den lägsta rangordningen en grafparameter $\operatorname {mr} (G)$ för en graf G . Det motiverades av Colin de Verdière grafen invariant .

Definition

Närliggande matris för en oriktad graf är en symmetrisk matris vars rader och kolumner båda motsvarar grafens hörn. Dess element är alla 0 eller 1, och elementet i rad i och kolumn j är icke-noll närhelst vertex i ligger intill vertex j i grafen. Mer allmänt är en generaliserad närliggande matris vilken symmetrisk matris som helst av reella tal med samma mönster av icke-noll från diagonalen (de diagonala elementen kan vara vilka reella tal som helst). Minsta rankning av $G$ definieras som den minsta rankningen av någon generaliserad närliggande matris i grafen; den betecknas med $\operatorname {mr} (G)$ .

Egenskaper

Här är några elementära egenskaper.

Minsta rankning av en graf är alltid högst lika med n − 1, där n är antalet hörn i grafen.
För varje inducerad subgraf H i en given graf G är minimigraden för H högst lika med minimigraden G .
Om en graf är frånkopplad är dess lägsta rankning summan av lägsta rankningar av dess anslutna komponenter .
Minsta rang är en grafinvariant : isomorfa grafer har nödvändigtvis samma minimirankning.

Karakterisering av kända graffamiljer

Flera familjer av grafer kan karakteriseras i termer av deras lägsta rangordning.

För ${\displaystyle n\geq 2} har$ hela grafen K _n på n hörn minsta rang etta. De enda graferna som är anslutna och har minsta rang etta är de kompletta graferna.
En väggraf P _n på n hörn har minsta rang n − 1. De enda n -vertexgraferna med minsta rang n − 1 är väggraferna.
En cykelgraf C _n på n hörn har minsta rang n − 2.
Låt $G$ vara en 2-kopplad graf. Då $\operatorname {mr} (G)=|G|-2$ om och endast om $G$ är ett linjärt 2-träd.
En graf $G$ har $\operatorname {mr} (G)\leq 2$ om och endast om komplementet till $G$ har formen ${\displaystyle (K_{s_{1}}\cup K_{s_{2}}\cup K_{ p_{1},q_{1}}\cup \cdots \cup K_{p_{k},q_{k}})\vee K_{r}} för lämpliga icke-negativa$ heltal $k,s_{1},s_{2},p_{1},q_{1},\ldots ,p_{k},q_{k} ,r$ med $p_{i}+q_{i}>0$ för alla $i=1,\ldots ,k$ .

Anteckningar

Fallat, Shaun; Hogben, Leslie , "Minsta rankning av symmetriska matriser som beskrivs av en graf: En undersökning", Linear Algebra and its Applications 426 (2007) (PDF) , s. 558–582 .