Universal toppunkt - Universal vertex
I grafteorin är en universell toppunkt en toppunkt för en oriktad graf som ligger intill alla andra toppar i diagrammet. Det kan också kallas ett dominerande toppunkt , eftersom det bildar en dominerande uppsättning med ett element i diagrammet. (Det ska inte förväxlas med ett universellt kvantifierat toppunkt i grafiklogiken .)
En graf som innehåller ett universellt toppunkt kan kallas en kon . I detta sammanhang kan det universella toppunktet också kallas konens topp . Denna terminologi strider emellertid mot terminologin för toppdiagram , där en topp är ett toppunkt vars avlägsnande lämnar en plan subgraf.
I speciella familjer med grafer
De stjärnor är exakt träden som har en universell vertex och kan konstrueras genom att tillsätta en universell vertex till en oberoende uppsättning . De hjul grafer , på liknande sätt, kan bildas genom tillsats av en universell vertex till en cyklisk graf . I geometri har de tredimensionella pyramiderna hjuldiagram som sina skelett , och mer generellt har grafen för alla högre dimensionella pyramider ett universellt topp som pyramidens topp .
De trivialt perfekta graferna ( jämförbarhetsdiagrammen för ordningsteoretiska träd ) innehåller alltid en universell topp, trädets rot, och starkare kan de karakteriseras som graferna i vilka varje ansluten inducerad subgraf innehåller en universell topp. De anslutna tröskeldiagrammen bildar en underklass av de trivialt perfekta graferna, så de innehåller också ett universellt toppunkt; de kan definieras som graferna som kan bildas genom upprepad tillsats av antingen ett universellt toppunkt eller ett isolerat toppunkt (ett utan infallande kanter).
Varje graf med en universell topp är en demonterbar graf , och nästan alla demonterbara grafer har en universell topp.
Andra egenskaper
I ett diagram med n hörn är ett universellt hörn ett hörn vars grad är exakt n - 1 . Därför, liksom de delade graferna , kan grafer med ett universellt toppunkt kännas igen rent av deras gradssekvenser utan att titta på grafens struktur.