Prime graf

Den här artikeln handlar om grafer definierade från ändliga grupper. För de grafer som inte kan dekomponeras som en produkt av mindre grafer, se Kartesisk produkt av grafer .

I matematiken för grafteorin och finita grupper är en primtalsgraf en oriktad graf definierad från en grupp . Dessa grafer introducerades i en artikel från 1981 av JS Williams, krediterad till opublicerat arbete från 1975 av KW Gruenberg och O. Kegel.

Definition

En grupps primtalsgraf har en vertex för varje primtal som delar ordningen (antalet element) för den givna gruppen, och en kant som förbinder varje par av primtal $p$ och $q$ för där det finns ett gruppelement med ordningen $pq$ .

På motsvarande sätt finns det en kant från $p$ till $q$ närhelst den givna gruppen innehåller pendlingselement av ordningen $p$ och av ordningen $q$ , eller närhelst den givna gruppen innehåller en cyklisk grupp av ordningen $pq$ som en av dess undergrupper.

Egenskaper

Vissa ändliga enkla grupper kan kännas igen på graderna av hörnen i deras primtalsgrafer. De anslutna komponenterna i ett primtalsdiagram har högst fem diameter och högst tre för lösbara grupper . När en primtalsgraf är ett träd har den högst åtta hörn och högst fyra för lösbara grupper.

Relaterade grafer

Variationer av primtalsgrafer som ersätter förekomsten av en cyklisk undergrupp av ordningen ${\displaystyle pq} ,$ i definitionen för angränsning i ett primtalsdiagram, genom att det finns en undergrupp av en annan typ, har också studerats. Liknande resultat har också erhållits från en besläktad familj av grafer, erhållna från en ändlig grupp genom graderna av dess tecken snarare än genom ordningen av dess element.