TY - BOOK

T1 - On the Cardinal Product

AU - Klöckl, Werner

N1 - no embargo

PY - 2007

Y1 - 2007

N2 - The aim of the dissertation are algorithms for the factorization of graphs with respect to the cardinal and the strong product. We develop algorithms for each of these products. The algorithm for the strong product applies Feigenbaum's and Schäffer's polynomial algorithm locally and improves its global complexity. The algorithm for the cardinal product that is presented here is so far the only one that computes the prime factor decomposition of a directed graph with respect to the cardinal product under certain conditions in polynomial time. The proof of the correctness of the algorithm also shows that the prime factorization is unique, which extends the class of directed graphs that are known to have a unique prime factorization. For further generalizations we introduce and investigate a new special class of graphs, so-called R^+_{s,r} - graphs. Our results help to describe the structure of the automorphism group of directed cardinal product graphs. We apply them to the computation of distinguishing numbers of product graphs.

AB - The aim of the dissertation are algorithms for the factorization of graphs with respect to the cardinal and the strong product. We develop algorithms for each of these products. The algorithm for the strong product applies Feigenbaum's and Schäffer's polynomial algorithm locally and improves its global complexity. The algorithm for the cardinal product that is presented here is so far the only one that computes the prime factor decomposition of a directed graph with respect to the cardinal product under certain conditions in polynomial time. The proof of the correctness of the algorithm also shows that the prime factorization is unique, which extends the class of directed graphs that are known to have a unique prime factorization. For further generalizations we introduce and investigate a new special class of graphs, so-called R^+_{s,r} - graphs. Our results help to describe the structure of the automorphism group of directed cardinal product graphs. We apply them to the computation of distinguishing numbers of product graphs.

KW - Kardinalprodukt

KW - polynomialer Automorphismen

KW - starkes Produkt

KW - Primfaktorzerlegung

KW - Algorithmus

KW - Unterscheidungszahl

KW - cardinal product

KW - polynomial automorphisms

KW - prime factorization algorithm

KW - distinguishing number

M3 - Doctoral Thesis

ER -