Stručni rad

Petersenov graf

Snježana Majstorović orcid.org/0000-0002-3083-0932 ; Odjel za matematiku, Sveučilište Josipa Jurja Strossmayera u Osijeku
Luka Boras ; Odjel za matematiku, Sveučilište Josipa Jurja Strossmayera u Osijeku

Sažetak

Petersenov graf je malen graf sa nizom posebnih svojstava
koja ga svrstavaju u jedno od ključnih otkrića na području
teorije grafova. U radu su opisana i analizirana razna svojstva
tog grafa. Posebno su iskazane i dokazane tvrdnje koje se tiču
ekstremalnosti Petersenova grafa u odnosu na promatrana
svojstva: on je najmanji 3-regularan graf bez reznih bridova
koji nema Hamiltonov ciklus, najmanji hipohamiltonov graf,
najmanji 3-regularan graf bez reznih bridova čiji bridno
kromatski broj iznosi 4 te najveći 3-regularan graf dijametra 2
i ujedno najmanji 3-regularan graf struka . Svakom
navedenom svojstvu pridružen je povijesni okvir koji
upotpunjuje sliku o utjecaju Petersenova grafa na razvoj
različitih grana moderne teorije grafova.

Ključne riječi

Petersenov graf; teorija grafova; kromatski broj

Hrčak ID:

144150

URI

https://hrcak.srce.hr/144150

Datum izdavanja:

31.8.2015.

Posjeta: 1.660 *