EuDML | Browse

Page 1

Displaying 1 – 5 of 5

Factoring directed graphs with respect to the cardinal product in polynomial time II

Wilfried Imrich, Werner Klöckl (2010)

Discussiones Mathematicae Graph Theory

By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the...

Factorisation of snarks.

Chladný, Miroslav, Škoviera, Martin (2010)

The Electronic Journal of Combinatorics [electronic only]

Folding on the wedge sum of graphs and their fundamental group.

Abu-Saleem, M. (2010)

APPS. Applied Sciences

Frucht’s Theorem for the Digraph Factorial

Richard H. Hammack (2013)

Discussiones Mathematicae Graph Theory

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,...

Fundamental groupoids of digraphs and graphs

Alexander Grigor'yan, Rolando Jimenez, Yuri Muranov (2018)

Czechoslovak Mathematical Journal

We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.