Linjär arboricitet

Uppdelning av grafen för en rombisk dodekaeder i två linjära skogar , vilket visar att dess linjära arboricitet är två

I grafteorin , en gren av matematiken, är den linjära arboriciteten för en oriktad graf det minsta antal linjära skogar som dess kanter kan delas in i. Här är en linjär skog en acyklisk graf med maximal grad två; det vill säga, det är en osammanhängande förening av kurvdiagram . Linjär arboricitet är en variant av arboricity , det minsta antalet skogar som kanterna kan delas in i.

Den linjära arboriciteten för varje graf med maximal grad $\Delta$ är känd för att vara minst $\lceil \Delta /2\rceil$ och antas vara högst $\lceil (\Delta +1)/2\rceil$ . Denna gissning skulle bestämma den linjära arboriciteten exakt för grafer av udda grad, eftersom båda uttrycken i så fall är lika. För grafer av jämn grad skulle det innebära att den linjära arboriciteten måste vara ett av endast två möjliga värden, men att bestämma det exakta värdet bland dessa två val är NP-komplett .

Förhållande till examen

Olöst problem i matematik :

Har varje graf med maximal grad $\Delta$ linjär arboricitet som mest $\lceil (\Delta +1)/2\rceil$ ?

(fler olösta problem i matematik)

Den linjära arboriciteten för en graf $G$ med maximal grad $\Delta$ är alltid minst ${\displaystyle \lceil \Delta /2\rceil } ,$ eftersom varje linjär skog kan använda endast två av kanterna vid en maximigradspunkt. Den linjära arboricitetsförmodan av Akiyama, Exoo & Harary (1981) är att denna nedre gräns också är snäv: enligt deras gissning har varje graf som mest linjär arboricitet $\lceil (\ Delta +1)/2\rceil$ . Detta förblir dock obevisat, med den bästa bevisade övre gränsen för den linjära arboriciteten är något större, $\Delta /2+O(\Delta ^{2/3 -c})$ för någon konstant $c>0$ på grund av Ferber, Fox och Jain.

För att den linjära arboriciteten för en graf ska vara lika med ${\displaystyle \Delta /2} ,$ måste $\Delta$ vara jämn och varje linjär skog måste ha två kanter som faller in mot varje vertex av grad ${\ displaystyle \Delta }$ . Men vid en vertex som är i slutet av en bana, har skogen som innehåller den banan bara en infallande kant, så graden vid den vertexen kan inte vara lika med $\Delta$ . Således måste en graf vars linjära arboricitet är lika med $\Delta /2$ ha några hörn vars grad är mindre än maximum. I en vanlig graf finns inga sådana hörn, och den linjära arboriciteten kan inte vara lika med $\Delta /2$ . Därför, för vanliga grafer, innebär den linjära arboriciteten att den linjära arboriciteten är exakt $\lceil (\Delta +1)/2\rceil$ .

Relaterade problem

Linjär arboricitet är en variant av arboricitet , det minsta antalet skogar som kanterna på en graf kan delas in i. Forskare har också studerat linjär k -arboricitet, en variant av linjär arboricitet där varje stig i den linjära skogen kan ha högst k kanter.

Ett annat relaterat problem är Hamiltons sönderdelning , problemet med att bryta ned en vanlig graf av jämn grad $\Delta$ till exakt $\Delta /2$ Hamiltonska cykler . En given graf har en Hamiltonsk nedbrytning om och endast om subgrafen som bildas genom att ta bort en godtycklig vertex från grafen har linjär arboricitet $\Delta /2$ .

Beräkningskomplexitet

Till skillnad från arboricitet, som kan bestämmas i polynomtid , är linjär arboricitet NP-hård . Även att känna igen graferna för linjär arboricitet två är NP-komplett . Men för kubiska grafer och andra grafer med maximal grad tre är den linjära arboriciteten alltid två, och en nedbrytning till två linjära skogar kan hittas i linjär tid med hjälp av en algoritm baserad på djup-först-sökning .