Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Arboreal structure and regular graphs of median-like classes

100%

Brešar B.

Discussiones Mathematicae Graph Theory

2003

tom 23

nr 2

215-225

We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional property. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.

Tree-like isometric subgraphs of hypercubes

51%

Brešar B., Imrich W., Klavžar S.

Discussiones Mathematicae Graph Theory

2003

tom 23

nr 2

227-240

Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Brešar B.

1 Imrich W.

1 Klavžar S.

2 2003

Wyniki wyszukiwania

Arboreal structure and regular graphs of median-like classes

Tree-like isometric subgraphs of hypercubes