SKDM sazetak 20180405

Izvor: KiWi

Skoči na: orijentacija, traži

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(Gw) za svaki vrh w \in 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 \geq 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.

Osobni alati