Retracts of products of chordal graphs
Abstract
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.
Keywords
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;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2010 |
| Typology: | 0 - Not set |
| Organization: | UM FNM - Faculty of Natural Sciences and Mathematics |
| UDC: | 519.17 |
| COBISS: |
15751513
|
| ISSN: | 2232-2094 |
| Parent publication: | Preprint series |
| Views: | 37 |
| Downloads: | 13 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary keywords: | teorija grafov;graf;retrakt;zastražena amalgamacija;tetiven graf;kartezični produkt grafov;medianski graf; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Not categorized |
| Pages: | str. 1-20 |
| Volume: | Vol. 48 |
| Issue: | št. 1134 |
| Chronology: | 2010 |
| ID: | 1475275 |
Recommended works:
Retracts of products of chordal graphs
2010,
no subtitle data available
On cube-free median graphs
2007,
no subtitle data available
On cube-free median graphs
2003,
no subtitle data available
On Vizing's conjecture
2001,
no subtitle data available
Cube intersection concepts in median graphs
2009,
no subtitle data available