Median graphs, the remoteness function, periphery transversals, and geodetic number twoBalakrishnan, Kannan (Avtor) Brešar, Boštjan (Avtor) Changat, Manoj (Avtor) Imrich, Wilfried (Avtor) Klavžar, Sandi (Avtor) Kovše, Matjaž (Avtor) Subhamathi, Ajitha R. (Avtor) medianski grafmedianska množicafunkcija oddaljenostigeodetsko številoperiferna transverzalamedian graphmedian setremoteness functiongeodetic numberperiphery transverzalhypercubePeriferna 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.20082015-07-10 12:00:54Delo ni kategorizirano49379sl