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:
Typology: 1.01 - Original Scientific Article
Organization: UL FMF - Faculty of Mathematics and Physics
UDC: 519.17
COBISS: 14252377 Link will open in a new window
ISSN: 0195-6698
Views: 37
Downloads: 27
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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
Recommended works:
, no subtitle data available
, magistrsko delo
, no subtitle data available
, diplomsko delo
, no subtitle data available