Partial cubes and their [tau]-graphs

Sandi Klavžar (Avtor), Matjaž Kovše (Avtor)

Povzetek

Za delno kocko ▫$G$▫ ima ▫$\tau$▫-graph ▫$G^\tau$▫ ekvivalenčne razrede Djokovic-Winklerjeve relacije kot vozlišča, pri čemer sta razreda ▫$E$▫ in ▫$F$▫ sosednja, če neki povezavi ▫$e \in E$▫ in ▫$f \in F$▫ inducirata konveksno pot ▫$P_3$▫. Dokazano je, da za vsak graf $G$ obstaja medianski graf ▫$M$▫, tako da velja ▫$G = M^\tau$▫, da je ▫$G^\tau$▫ povezan natanko tedaj, ko je ▫$G$▫ pragraf glede na kartezični produkt grafov in da je ▫$\tau$▫-graf medianskega grafa ▫$G$▫ brez ▫$K_n$▫ natanko tedaj, ko ▫$G$▫ ne vsebuje konveksnega ▫$K_{1,n}$▫.

Ključne besede

matematika;teorija grafov;delne kocke;medianski grafi;kartezični produkt grafov;mathematics;graf theory;partial cubes;median graphs;Cartesian product graphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	14252377
ISSN:	0195-6698
Št. ogledov:	37
Št. prenosov:	27
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Delne kocke in njihovi [tau]-grafi
Sekundarni povzetek:	The ▫$\tau$▫-graph ▫$G^\tau$▫ of a partial cube ▫$G$▫ has the equivalence classes of the Djokovic-Winkler relation as vertices, two classes ▫$E$▫ and ▫$F$▫ being adjacent if some edges ▫$e \in E$▫ and ▫$f \in F$▫ induce a convex ▫$P_3$▫. It is shown that for every graph ▫$G$▫ there exists a median graph ▫$M$▫ such that ▫$G = M^\tau$▫, that ▫$G^\tau$▫ is connected if and only if ▫$G$▫ is a Cartesian prime graph, and that for a median graph ▫$G$▫ its ▫$\tau$▫-graph is ▫$K_n$▫-free if and only if ▫$G$▫ contains no convex ▫$K_{1,n}$▫.
Sekundarne ključne besede:	matematika;teorija grafov;delne kocke;medianski grafi;kartezični produkt grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1037-1042
Letnik:	ǂVol. ǂ28
Zvezek:	ǂno. ǂ4
Čas izdaje:	2007
ID:	1473038