Uniformly dissociated graphs

angleški

2017

letnik 13, številka 2

disociacijsko število   dobro pokriti grafi   Moore-ovi grafi   ožina   polarnostni grafi

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Množica vozlišč ?$D$? grafa ?$G$? se imenuje disociacijska množica, če ima vsako vozlišče množice ?$D$? največ enega soseda iz ?$D?$. Pravimo, da je graf enakomerno disociiran, če imajo vse njegove maksimalne disociacijske množice isto moč. V članku dokažemo karakterizacije enakomerno disociiranih grafov z majhnimi močmi disociacijskih množic; tako so grafi, v katerih imajo vse maksimalne disociacijske množice dva elementa, natanko polni grafi na vsaj dveh vozliščih, iz katerih so lahko odstranjene tudi povezave kakega prirejanja, medtem ko so grafi, v katerih so vse maksimalne disociacijske množice moči 3, natanko komplementi geodetskih grafov z diametrom 2, ki nimajo induciranih podgrafov izomorfnik ?$K_4$?. Predstavimo tudi splošno konstrukcijo, s katero lahko poljuben graf vložimo kot induciran podgraf v nek enakomerno disociiran graf. Glavni rezultat je karakterizacija enakomerno disociiranih grafov, v katerih so vsi cikli dolžine vsaj 7, kot grafov, ki so bodisi izomorfni grafu ?$C_7$? ali pa jih lahko dobimo iz poljubnega grafa ?$H$?, v katerem so vsi cikli dolžine vsaj 7, tako da identificiramo vsako vozlišče grafa ?$H$? z listom kopije grafa ?$P_3$?.

29.05.2020