ǂThe ǂperiphery graph of a median graph

Boštjan Brešar (Avtor), Manoj Changat (Avtor), Ajitha R. Subhamathi (Avtor), Aleksandra Tepeh (Avtor)

Povzetek

Graf periferij medianskega grafa je presečni graf njegovih perifernih podgrafov. V članku pokažemo, da je vsak graf brez univerzalnih vozlišč mogoče realizirati kot graf periferij nekega medianskega grafa. Karakteriziramo tiste medianske grafe, katerih graf periferij je spoj dveh grafov in pokažemo, da so to natanko kartezični produkti medianskih grafov. Vpeljemo medianske grafe sorodne potem, ki so tisti medianski grafi, katerih neodvisnostno število grafa periferij je enako 2, ter pokažemo, da obstajajo medianski grafi sorodni potem s poljubno velikim geodetskim številom. Glede na grafe periferij je obravnavana periferna ekspanzija, pokažemo pa tudi povezavo s konceptom križnih grafov.

Ključne besede

matematika;teorija grafov;medianski graf;kartezični produkt;periferija;periferna ekspanzija;mathematics;graph theory;median graph;Cartesian product;geodesic;periphery;peripheral expansion;

Podatki

Jezik:	Angleški jezik
Leto izida:	2010
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	15637081
ISSN:	1234-3099
Št. ogledov:	1000
Št. prenosov:	343
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Grafi periferij medianskega grafa
Sekundarni povzetek:	The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like median graphs with arbitrarily large geodetic number. Peripheral expansion with respect to periphery graph is also considered, and connections with the concept of crossing graph are established.
Sekundarne ključne besede:	matematika;teorija grafov;medianski graf;kartezični produkt;periferija;periferna ekspanzija;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Znanstveno delo
Strani:	str. 17-32
Letnik:	ǂVol. ǂ30
Zvezek:	ǂno. ǂ1
Čas izdaje:	2010
ID:	9595949