TY - BOOK

T1 - On the Cardinal Product

AU - Klöckl, Werner

N1 - embargoed until null

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 Primfaktorzerlegung Algorithmus

KW - polynomialer Automorphismen Unterscheidungszahl Produkt

KW - starkes

KW - cardinal product prime factorization algorithm

KW - polynomial automorphisms distinguishing number

M3 - Doctoral Thesis

ER -