Desargues grafiek

In grafentheorie, de Desargues grafiek is een symmetrische kubieke grafiek met 20 hoekpunten en 30 randen. Het is vernoemd Girard Desargues.

Gebouw

De Desargues grafiek is isomorf met de tweeledige grafiek van Kneser en gegeneraliseerde Petersen grafiek GP. Het is ook de incidentie grafiek configuratie Desargues.

De Desargues grafiek is Hamiltoniaan en kan worden beschreven door de notatie CFL.

Properties

Algemene eigenschappen

De diameter van Desargues grafiek, de maximale excentriciteit van haar hoekpunten is 5, de radius, de minimale excentriciteit van haar hoekpunten is 5 en het gaas, de lengte van de kortste cyclus 6. Deze wordt een 3-vertex verbonden grafiek en een 3-edge-samenhangende graaf, dat wil zeggen het is verbonden en losgekoppeld te maken moet ten minste 3 of 3 pieken ontnemen randen.

Desargues grafiek is niet vlak. In feite te tekenen op de kaart is het noodzakelijk dat meer randen samenkomen. Het is mogelijk om tekenen met slechts 6 kruisen en dit aantal is minimaal. Met 20 pieken, het is de kleinste kubieke grafiek kruisen 6 die worden getrokken over het plan.

Kleur

Het chromatische aantal grafiek Desargues 2. Dat wil zeggen, het is mogelijk te kleuren met twee kleuren zodat twee hoekpunten verbonden door een rand zijn steeds verschillende kleuren maar het aantal is minimaal. Er is geen geldige grafiek-1 kleuring.

De chromatische index Desargues grafiek 3. Er is dus een 3-kleuring van de randen van de grafiek zodanig dat geen twee randen incident dezelfde vertex steeds verschillende kleuren. Dit aantal is minimaal.

Algebraïsche eigenschappen

De grafiek van Desargues symmetrisch, dat wil zeggen dat de automorfismegroep werkt transitieve op de richels, pieken en bogen. Haar automorfismegroep heeft oog 240 × S5 is isomorf aan Z / 2Z, het directe product van de symmetrische groep S5 met de unieke groep van orde 2. Slechts twee symmetrische kubieke grafieken bestaan ​​pieken op 20 en 20 is de kleinere volgorde waarin er twee verschillende symmetrische kubieke grafieken: F20A en F20B volgens de rating van Foster Census. F20A is de dodecaëdervorm grafiek, F20B is de grafiek van Desargues. Orders 4, 6, 8, 10, 14, 16 en 18 is een symmetrische kubieke grafiek.

De karakteristieke polynoom van de nabijheid matrix van de Desargues grafiek is :. De Desargues grafiek is een integraal grafiek, een grafiek waarbij het spectrum bestaat uit gehele getallen.

Galerij