Maximal proper subgraphs of median graphs

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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	14257497
ISSN:	0012-365X
Št. ogledov:	636
Št. prenosov:	69
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Maksimalni pravi podgrafi medianskih grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;medianski graf;podgraf brez enega vozlišča;dvodelno kolo;kvadratna povezava;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1389-1394
Letnik:	ǂVol. ǂ307
Zvezek:	ǂiss. ǂ11-12
Čas izdaje:	2007
ID:	1473047