En universell vertex är en vertex av en oriktad graf som ligger intill alla andra hörn i grafen. Den kan också kallas en dominant nod eftersom den bildar en singleton dominant uppsättning i grafen.
En graf som innehåller en universell vertex kan också kallas en kon . I detta sammanhang kan en universell vertex kallas spetsen av en kon [1] , men detta strider mot terminologin för spetsgrafer , där spetsen ibland kallas en spets vars borttagande gör grafen plan.
Stjärnor är exakt träd som har en universell vertex och kan byggas genom att lägga till en universell vertex till en oberoende uppsättning . Hjul kan på liknande sätt bildas genom att lägga till en universell vertex till cykeln [2] . Inom geometri har tredimensionella pyramider hjul som sina skelett , och mer allmänna grafer av vilken pyramid som helst i rymden av vilken dimension som helst har en universell vertex som toppen (spetsen) av pyramiden.
Trivialt perfekta grafer ( jämförbarhetsgrafer av träd från mängdteorin ) innehåller alltid en universell vertex, nämligen trädets rot, och kan beskrivas som grafer där vilken som helst genererad subgraf innehåller en universell vertex [3] . Perfekta tröskelgrafer bildar en underklass av trivialt perfekta grafer, så de innehåller en universell vertex. De kan definieras som grafer som kan bildas genom att upprepade gånger lägga till antingen en universell vertex eller en isolerad vertex (det vill säga en vertex utan kanter) [4] .
Varje graf med en universell vertex är parserbar , och nästan alla parserbara grafer har en universell vertex [5] .
I en graf med n hörn är en universell vertex en vertex vars grad är exakt n − 1 . Därför, precis som delade grafer , kan universella vertexgrafer identifieras enbart genom sin gradsekvens utan att titta på grafernas struktur.