ǂThe ǂperiphery graph of a median graph

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2010
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	15637081
ISSN:	1234-3099
Views:	1000
Downloads:	343
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Grafi periferij medianskega grafa
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;medianski graf;kartezični produkt;periferija;periferna ekspanzija;
URN:	URN:SI:UM:
Type (COBISS):	Scientific work
Pages:	str. 17-32
Volume:	ǂVol. ǂ30
Issue:	ǂno. ǂ1
Chronology:	2010
ID:	9595949