20.500.12556/DKUM-49379 Median graphs, the remoteness function, periphery transversals, and geodetic number two Medianski grafi, funkcija oddaljenosti, periferne transverzale in geodetsko število dva Periferna transverzala medianskega grafa ▫$G$▫ je vpeljana kot množica vozlišč, ki zadane vse periferije grafa $G$. S pomočjo tega koncepta so na dva različna načina karakterizirani medianski grafi z geodetskim številom 2. To so natanko tisti medianski grafi, ki vsebujejo periferno transverzalo moči 2, kot tudi medianski grafi, za katere obstaja takšen profil, da je funkcija oddaljenosti konstantna na ▫$G$▫. Predstavljen je tudi algoritem, ki v času ▫$O(m log n)$▫ odloči, ali je dani graf z ▫$n$▫ vozlišči in ▫$m$▫ povezavami medianski graf z geodetskim številom 2. Dobljenih je še več nadaljnjih lastnosti funkcije oddaljenosti na hiperkockah in medianskih grafih. Navedenih je tudi nekaj odprtih problemov. A periphery transversal of a median graph ▫$G$▫ is introduced as a set of vertices that meets all the peripheral subgraphs of ▫$G$▫. Using this concept, median graphs with geodetic number 2 are characterized in two ways. They are precisely the median graphs that contain a periphery transversal of order 2 as well as the median graphs for which there exists a profile such that the remoteness function is constant on ▫$G$▫. Moreover, an algorithm is presented that decides in ▫$O(mlog n)$▫ time whether a given graph ▫$G$▫ with ▫$n$▫ vertices and ▫$m$▫ edges is a median graph with geodetic number 2. Several additional structural properties of the remoteness function on hypercubes and median graphs are obtained and some problems listed. medianski graf medianska množica funkcija oddaljenosti geodetsko število periferna transverzala median graph median set remoteness function geodetic number periphery transverzal hypercube true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 12:00:54 2015-07-10 12:00:54 2022-05-27 03:09:28 2019-07-10 21:28:29 2008 0 0 str. 1-19 št. 1046 Vol. 46 2008 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1318-4865 519.17 44310272 14609497 URN:SI:UM:DK:1WEO2T3D http://www.imfm.si/preprinti/PDF/01046.pdf 1 https://dk.um.si/Dokument.php?lang=slv&id=73938 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0