Seminar za kombinatornu i diskretnu matematiku
lokacija:
PMF Matematički odsjek
vrijeme:
05.04.2018 - 15:00 - 16:30
U četvrtak, 5. travnja 2018. u predavaonici 104 u 15 sati
u okviru Seminara za kombinatornu i diskretnu matematiku održat će se
predavanje:
Snježana Majstorović: Šoltesov problem
Pozivaju se članovi Seminara te svi zainteresirani da prisustvuju ovom
predavanju
Tajnik Seminara
Goran Igaly
Sažetak: Za povezan graf G Wienerov indeks W(G) definiran je kao suma udaljenosti
vrhova u G. Godine 1991. Šoltes je proučavao promjene Wienerova indeksa obzirom na neke
jednostavne unarne operacije na G kao što su uklanjanje vrha ili brida.
U svom radu [1] postavio je problem određivanja svih grafova G sa svojstvom
W(G) = W(G - w) za svaki vrh w ∈ V (G), pri čemu je dao primjer samo jednog takvog grafa:
ciklus C11. Do danas nije poznato postoji li još grafova s navedenim svojstvom
pa je Šoltesov problem i dalje na listi otvorenih problema iz područja teorije grafova.
Cilj predavanja je predstaviti rezultate relaksirane verzije Šoltesova
problema u kojoj zahtijevamo da tražena jednakost vrijedi za barem jedan vrh grafa.
Dokazat ćemo da postoji beskonačno mnogo grafova s vrhom v stupnja k ≥ 2
koji su rješenja relaksirane verzije problema. Specijalno ćemo se baviti unicikličkim
i gustim grafovima, a predstavit ćemo i rezultate
vezane za neke binarne operacije nad grafovima.
[1] L'. Šoltés, Transmission in graphs: A bound and vertex removing, Math.
Slovaca 41 (1991) 11-16.
