On the Cardinal Product

Werner Klöckl

Research output: ThesisDoctoral Thesis

24 Downloads (Pure)

Abstract

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.
Translated title of the contributionÜber das Kardinalprodukt
Original languageEnglish
QualificationDr.mont.
Supervisors/Advisors
  • Imrich, Wilfried, Assessor A (internal)
  • Klavžar, Sandi, Assessor B (external), External person
Publication statusPublished - 2007

Bibliographical note

embargoed until null

Keywords

  • cardinal product prime factorization algorithm
  • polynomial automorphisms distinguishing number

Cite this