Partial cubes and their [tau]-graphs

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

Abstract

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}$▫.

Keywords

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

Data

Language:	English
Year of publishing:	2007
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	14252377
ISSN:	0195-6698
Views:	37
Downloads:	27
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Delne kocke in njihovi [tau]-grafi
Secondary abstract:	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}$▫.
Secondary keywords:	matematika;teorija grafov;delne kocke;medianski grafi;kartezični produkt grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1037-1042
Volume:	ǂVol. ǂ28
Issue:	ǂno. ǂ4
Chronology:	2007
ID:	1473038