Iskanje po katalogu digitalne knjižnice

Opis: We characterize the graphs ▫$G$▫ that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain ▫$K_{2;3}$▫, ▫$k$▫-wheels ▫$W_k$▫, and ▫$k$▫-wheels minus one spoke T$W_k^- ; (k ge 4)$T as induced subgraphs. We also show that these graphs ▫$G$▫ are exactly the cage-amalgamation graphs introduced by Brešar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of "solid" simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
Ključne besede: teorija grafov, graf, retrakt, zastražena amalgamacija, tetiven graf, kartezični produkt grafov, medianski graf, graph theory, graph, retract, gated amalgamation, chordal graph, Cartesian product of graphs, median graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 663; Prenosov: 85
Povezava na celotno besedilo