I grafteorin är en tröskelgraf en graf som kan byggas från en graf med en enda vertex genom att sekventiellt utföra följande två operationer:
Till exempel är grafen i figuren en tröskelgraf. Det kan byggas från ett hörn (topp 1) och lägga till svarta hörn som isolerade hörn och röda hörn som dominanta hörn i numerisk ordning.
Tröskelgrafer introducerades av Chvatal och Hammer [1] . Kapitlet om grafer dök upp i Golumbiks bok [2] , medan Mahadev och Peleds bok [3] helt och hållet ägnas åt tröskeldiagram.
En ekvivalent definition är följande: en graf är tröskel om det finns ett reellt tal och för varje hörn ges en vikt så att för två hörn , är en kant om och endast om .
En annan ekvivalent definition: en graf är tröskel om det finns ett reellt tal och för varje vertex ges en vikt så att för varje uppsättning av hörn är oberoende om och endast om
Namnet "tröskeldiagram" kommer från definitionen: S är ett "tröskelvärde" för att egenskapen ska ha en kant, eller motsvarande, T är en tröskel för att en mängd ska vara oberoende.
Från definitionen som använder sekventiell addition av hörn, kan man få ett alternativt sätt att unikt beskriva tröskeldiagrammet i betydelsen av en teckensträng. fungerar alltid som det första tecknet i strängen och representerar grafens första hörn. Varje efterföljande tecken kommer antingen att vara , vilket betyder en isolerad vertex, eller , vilket betyder att man lägger till en dominant vertex. Till exempel representerar en sträng en stjärna med tre blad, men representerar en bana med tre hörn. Grafen i figuren kan representeras av linjen
Tröskelgrafer är ett specialfall av kografer , delade grafer och trivialt perfekta grafer [4] . Varje graf som är både en kograf och en delad graf är en tröskelgraf. Varje graf som är både en trivialt perfekt graf och komplementet till en trivialt perfekt graf är en tröskelgraf. Tröskeldiagram är också ett specialfall av intervallgrafer . Alla dessa samband kan förklaras i termer av deras karaktärisering av förbjudna genererade subgrafer. En kograf är en graf utan genererade banor med fyra hörn, P 4 , och tröskeldiagram är grafer av baser av genererade subgrafer P 4 , C 4 eller 2K 2 [5] . C 4 är en cykel av fyra hörn, och 2K 2 är dess komplement, det vill säga två separata kanter. Detta förklarar också varför tröskeldiagram är komplementstängda. P 4 är självkomplementär, och därför, om grafen inte innehåller genererade subgrafer P 4 , C 4 och 2K 2 , kommer dess komplement inte heller att ha dem [6] .
Heggernes et al har visat att tröskelgrafer kan kännas igen i linjär tid. Om grafen inte är tröskelvärde indikeras ett hinder i form av P 4 , C 4 , eller 2K 2 .