Maximal proper subgraphs of median graphs

Boštjan Brešar (Author), Sandi Klavžar (Author)

Abstract

Za medianski graf ▫$G$▫ in vozlišče ▫$v$▫, ki ni presečno, dokažemo, da je ▫$G-v$▫ medianski graf natanko tedaj, ko ▫$v$▫ ni center dvodelnega kolesa. To je nadalje ekvivalentno obstoju določene eliminacijske sheme za povezave, ki so incidenčne z ▫$v$▫. Rezultat implicira karakterizacijo po vozliščih kritičnih (po vozliščih polnih) medianskih grafov, ki so medianski grafi, katerih vsi podgrafi brez enega vozlišča niso medianski (so medianski). Podani sta tudi dve analogni karakterizaciji za primer odstranjevanja povezav.

Keywords

matematika;teorija grafov;medianski graf;podgraf brez enega vozlišča;dvodelno kolo;kvadratna povezava;mathematics;graph theory;median graph;vertex-deleted subgraph;bipartite wheel;square-eddge;square-dismantlable vertex;

Data

Language:	English
Year of publishing:	2007
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	14257497
ISSN:	0012-365X
Views:	636
Downloads:	69
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Maksimalni pravi podgrafi medianskih grafov
Secondary abstract:	For a median graph ▫$G$▫ and a vertex ▫$v$▫ of ▫$G$▫ that is not a cut-vertex we show that ▫$G-v$▫ is a median graph precisely when v is not the center of a bipartite wheel, which is in turn equivalent with the existence of a certain edge elimination scheme for edges incident with ▫$v$▫. This implies a characterization of vertex-critical (respectively, vertex-complete) median graphs, which are median graphs whose all vertex-deleted subgraphs are not median (respectively, are median). Moreover, two analogous characterizations for edge-deleted median graphs are given.
Secondary keywords:	matematika;teorija grafov;medianski graf;podgraf brez enega vozlišča;dvodelno kolo;kvadratna povezava;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1389-1394
Volume:	ǂVol. ǂ307
Issue:	ǂiss. ǂ11-12
Chronology:	2007
ID:	1473047