Mycket oregelbunden graf

I grafteorin är en mycket oregelbunden graf en graf där, för varje vertex, alla grannar till den vertex har distinkta grader .

Historia

Oregelbundna grafer karakteriserades initialt av Yousef Alavi , Gary Chartrand , Fan Chung , Paul Erdős , Ronald Graham och Ortrud Oellermann . De var motiverade att definiera "motsatsen" till en vanlig graf , ett koncept som har studerats grundligt och väl förstått.

Lokalitet och regelbundenhet

Att definiera en "oregelbunden graf" var inte direkt självklart. I en k -regelbunden graf har alla hörn grad k . I varje graf G med mer än en vertex måste två hörn i G ha samma grad, så en oregelbunden graf kan inte definieras som en graf med alla hörn av olika grader. Man kan då vara frestad att definiera en oregelbunden graf som att den har alla hörn av distinkta grader utom två, men dessa typer av grafer är också väl förstådda och därför inte intressanta.

Grafteoretiker vände sig alltså till frågan om lokal regelbundenhet. En graf är lokalt regelbunden vid en vertex v om alla hörn intill v har grad r . En graf är alltså lokalt oregelbunden om för varje vertex v av G grannarna till v har distinkta grader, och dessa grafer kallas därför mycket oregelbundna grafer.

Egenskaper för oregelbundna grafer

Några fakta om mycket oregelbundna grafer som beskrivs av Alavi et al. :

• Om v är en vertex med maximal grad d i en mycket oregelbunden graf H , så ligger v intill exakt en vertex av grad 1, 2, ..., d .
• Den största graden i en mycket oregelbunden graf är högst hälften av antalet hörn.
• Om H är en mycket oregelbunden graf med maximal grad d , kan man konstruera en mycket oregelbunden graf av grad d +1 genom att ta två kopior av H och lägga till en kant mellan de två hörnen av grad d .
• H ( n )/ G ( n ) går till 0 när n går till oändlighet exponentiellt snabbt, där H ( n ) är antalet (icke-isomorfa) mycket oregelbundna grafer med n hörn, och G ( n ) är det totala antalet av grafer med n hörn.
• För varje graf G finns det en mycket oregelbunden graf H som innehåller G som en inducerad subgraf .

Denna sista observation kan betraktas som analog med ett resultat av Dénes Kőnig , som säger att om H är en graf med störst grad r , så finns det en graf G som är r -regular och innehåller H som en inducerad subgraf.

Ansökningar om oegentligheter

Definitioner av oegentligheter har varit viktiga i studiet av nätverksheterogenitet, vilket har implikationer i nätverk som finns inom biologi, ekologi, teknik och ekonomi. Det har föreslagits flera grafstatistik, varav många är baserade på antalet hörn i en graf och deras grader. Karakteriseringen av mycket oregelbundna grafer har också tillämpats på frågan om heterogenitet, men alla dessa misslyckas med att kasta tillräckligt ljus över verkliga situationer. Ansträngningar fortsätter att göras för att hitta lämpliga sätt att kvantifiera nätverkets heterogenitet.