Median graphs, the remoteness function, periphery transversals, and geodetic number two

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

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.

Ključne besede

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:	2008
Tipologija:	0 - Ni določena
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	14609497
ISSN:	1318-4865
Št. ogledov:	730
Št. prenosov:	22
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Medianski grafi, funkcija oddaljenosti, periferne transverzale in geodetsko število dva
Sekundarni povzetek:	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(m\log 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.
Sekundarne ključne besede:	medianski graf;medianska množica;funkcija oddaljenosti;geodetsko število;periferna transverzala;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-19
Letnik:	ǂVol. ǂ46
Zvezek:	ǂšt. ǂ1046
Čas izdaje:	2008
ID:	67277