Kantgraf

En kantgraf eller linjegraf är inom matematik, specifikt grafteori, en graf som konstrueras från en given graf så att kanter i den ursprungliga grafen blir hörn i kantgrafen.

Formellt definieras linjegrafen L(G) till grafen G så att varje hörn i L(G) representeras av en kant i G och att två hörn i L(G) binds samman med en kant om och endast om motsvarande kanter i G har en gemensam ändpunkt.

Exempel

Nedan visas ett exempel på hur en kantgraf L(G) (längst till höger) konstrueras från en given graf G (längst till vänster). Hörnen i kantgrafen får här namn efter hörnen i G som kanten binder ihop. Exempelvis fås hörnet $(1,4)$ i L(G) från kanten som binder ihop hörnen 1 och 4 i G.

• 
  Grafen G.
• 
  Hörn i L(G) konstrueras från kanterna i G.
• 
  Kanter i L(G) läggs till.
• 
  När hörnen i G tas bort får man kantgrafen L(G).

Egenskaper

Egenskaper hos en graf G som endast beror på närhet av kanter kan översättas till egenskaper i L(G) som endast beror på närhet av hörn. Exempelvis motsvaras en matchning i G av en oberoende mängd i L(G).

• En sammanhängande graf har en kantgraf som är sammanhängande. I en sammanhängande graf finns det en väg mellan alla par av hörn, vilket blir en väg som binder samman varje par av hörn i kantgrafen. En graf som har några isolerade hörn, och därför inte är sammanhängande, kan dock ha en sammanhängande kantgraf.
• En största oberoende mängd i en kantgraf motsvaras av en största matchning i den ursprungliga grafen.
• En hörntransitiv grafs kantgraf är en kanttransitiv graf.
• Om grafen G har en Eulercykel så har L(G) en Hamiltoncykel.
• Alla linjegrafer är klofria.

Karaktärisering

En graf som inte är en kantgraf. Kanterna som går uppåt, vänster och höger från noden i mitten har inga klickar gemensamt, så varje partionering av grafens noder i klickar måste ha en klick var för dessa kanter, som alla måste ha med mittnoden, vilket bryter mot villkoret att varje nod ligger i högst två klickar.

En graf G kan fås som en kantgraf ur en annan graf om och endast om det finns en samling av klickar i G som partionerar kanterna i G sådan att varje hörn tillhör högst två klickar. Om G inte är en triangel finns det högst ett sätt att bilda en sådan partition. Om en sådan partitionering finns kan man återskapa grafen som har G som linjegraf genom att skapa ett hörn för varje klick och skapa en kant mellan två hörn om det i G finns ett hörn som ligger i båda klickarna. Så, om man bortser från den kompletta grafen K₃ och den kompletta bipartita grafen $K_{1,3}$, så är två sammanhängande grafer isomorfa om deras kantgrafer är isomorfa.

De nio minimala graferna som inte är kantgrafer.

En annan karaktärisering utgörs av att det finns nio minimala grafer (se bild till vänster) som inte är linjegrafer, dvs om en graf innehåller någon av dessa minimala icke-kantgrafer som inducerad delgraf, är det inte en kantgraf. Exempelvis innehåller grafen till höger en klo (den komplett bipartita grafen $K_{1,3}$) som är en av de förbjudna graferna, och kan därför inte vara en kantgraf.

För grafer med minimal grad 5 eller högre behövs endast de sex graferna i den vänstra och den högra kolumnen.

Referenser

• Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1 
• Diestel, Reinhard (2005). Graph Theory. Springer Verlag. ISBN 3-540-26182-6 

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Line graph, 9 oktober 2009.