341 KB42 KB200820252017Brešar, BoštjanHartnell, Bert L.Rall, Douglas F.letnik:13številka:2str. 293-306COBISSID:18064729ISSN:1855-3966URN:URN:NBN:SI:doc-0COBRRGYenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadisociacijsko številodobro pokriti grafiMoore-ovi grafiožinapolarnostni grafiUniformly dissociated graphs|A set ?$D$? of vertices in a graph ?$G$? is called a dissociation set if every vertex in ?$D$? has at most one neighbor in ?$D$?. We call a graph ?$G$? uniformly dissociated if all maximal dissociation sets are of the same cardinality. Characterizations of uniformly dissociated graphs with small cardinalities of dissociation sets are proven; in particular, the graphs in which all maximal dissociation sets are of cardinality 2 are the complete graphs on at least two vertices from which possibly a matching is removed, while the graphs in which all maximal dissociation sets are of cardinality 3 are the complements of the ?$K_4$?-free geodetic graphs with diameter 2. A general construction by which any graph can be embedded as an induced subgraph of a uniformly dissociated graph is also presented. In the main result we characterize uniformly dissociated graphs with girth at least 7 to be either isomorphic to ?$C_7$?, or obtainable from an arbitrary graph ?$H$? with girth at least 7 by identifying each vertex of ?$H$? with a leaf of a copy of ?$P_3$?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$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije