On the remoteness function in median graphs

Kannan Balakrishnan (Avtor), Boštjan Brešar (Avtor), Manoj Changat (Avtor), Wilfried Imrich (Avtor), Sandi Klavžar (Avtor), Matjaž Kovše (Avtor), Ajitha R. Subhamathi (Avtor)

Povzetek

Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m \log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.

Ključne besede

hiperkocka;medianski graf;medianska množica;funkcija oddaljenosti;geodetsko število;periferna transverzala;median graph;median set;remoteness function;geodetic number;periphery transverzal;hypercube;

Podatki

Jezik:	Angleški jezik
Leto izida:	2009
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	15383897
ISSN:	0166-218X
Št. ogledov:	37
Št. prenosov:	21
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Funkcija oddaljenosti v medianskih grafih
Sekundarni povzetek:	A profile on a graph ▫4G$▫ is any nonempty multiset whose elements are vertices from ▫$G$▫. The corresponding remoteness function associates to each vertex ▫$x \in V(G)$▫ the sum of distances from ▫$x$▫ to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph ▫$G$▫ whose remoteness function is maximum (antimedian set of ▫$G$▫) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph ▫$G$▫ on ▫$n$▫ vertices and ▫$m$▫ edges, decides in ▫$O(m \log n)$▫ time whether ▫$G$▫ is a median graph with geodetic number 2.
Sekundarne ključne besede:	hiperkocka;medianski graf;medianska množica;funkcija oddaljenosti;geodetsko število;periferna transverzala;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 3679-3688
Letnik:	ǂVol. ǂ157
Zvezek:	ǂiss. ǂ18
Čas izdaje:	2009
ID:	1474539