Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: graph automorphisms

Sortuj według:

Ogranicz wyniki do:

Frucht’s Theorem for the Digraph Factorial

100%

Hammack R. H.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 2

329-336

To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms a group, and the loops form a subgroup that is isomorphic to Aut(A). (So E(A!) can be regarded as an extension of Aut(A).) This note proves an analogue of Frucht’s theorem in which Aut(A) is replaced by the group E(A!). Given any finite group G, we show that there is a graph A for which E(A!) ∼= G.

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

Tree-like isometric subgraphs of hypercubes

63%

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

1 Brešar B.

1 Hammack R. H.

1 Imrich W.

1 Klavžar S.

1 2013

1 2003

Wyniki wyszukiwania

Frucht’s Theorem for the Digraph Factorial

Tree-like isometric subgraphs of hypercubes