Wyniki wyszukiwania

1

Frucht’s Theorem for the Digraph Factorial

100%

Hammack R. H.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 2

329-336

EN

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.

2

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

Cancellation of direct products of digraphs

100%

Hammack R., Toman K.

Discussiones Mathematicae Graph Theory

|

2010

|

tom 30

|

nr 4

575-590

EN

We investigate expressions of form A×C ≅ B×C involving direct products of digraphs. Lovász gave exact conditions on C for which it necessarily follows that A ≅ B. We are here concerned with a different aspect of cancellation. We describe exact conditions on A for which it necessarily follows that A ≅ B. In the process, we do the following: Given an arbitrary digraph A and a digraph C that admits a homomorphism onto an arc, we classify all digraphs B for which A×C ≅ B×C.

3

New classes of critical kernel-imperfect digraphs

88%

Galeana-Sánchez H., Neumann-Lara V.

Discussiones Mathematicae Graph Theory

|

1998

|

tom 18

|

nr 1

85-89

EN

A kernel of a digraph D is a subset N ⊆ V(D) which is both independent and absorbing. When every induced subdigraph of D has a kernel, the digraph D is said to be kernel-perfect. We say that D is a critical kernel-imperfect digraph if D does not have a kernel but every proper induced subdigraph of D does have at least one. Although many classes of critical kernel-imperfect-digraphs have been constructed, all of them are digraphs such that the block-cutpoint tree of its asymmetrical part is a path. The aim of the paper is to construct critical kernel-imperfect digraphs of a special structure, a general method is developed which permits to build critical kernel-imperfect-digraphs whose asymmetrical part has a prescribed block-cutpoint tree. Specially, any directed cactus (an asymmetrical digraph all of whose blocks are directed cycles) whose blocks are directed cycles of length at least 5 is the asymmetrical part of some critical kernel-imperfect-digraph.

4

Dichromatic number, circulant tournaments and Zykov sums of digraphs

75%

Neumann-Lara V.

Discussiones Mathematicae Graph Theory

|

2000

|

tom 20

|

nr 2

197-207

EN

The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant tournaments for every k ≥ 3, k ≠ 7.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

2 Neumann-Lara V.

1 Galeana-Sánchez H.

1 Hammack R.

1 Hammack R. H.

1 Toman K.

1 2013

1 2010

1 2000

1 1998

Frucht’s Theorem for the Digraph Factorial

Cancellation of direct products of digraphs

New classes of critical kernel-imperfect digraphs

Dichromatic number, circulant tournaments and Zykov sums of digraphs