PDF

Discussiones Mathematicae Graph Theory 27(3) (2007) 593-601
DOI: https://doi.org/10.7151/dmgt.1385

FACTORING DIRECTED GRAPHS WITH RESPECT TO THE CARDINAL PRODUCT IN POLYNOMIAL TIME

Wilfried Imrich  and  Werner Klöckl

Chair of Applied Mathematics
Montanuniversität, 8700 Leoben, Austria
e-mail: wilfried.imrich@uni-leoben.at
e-mail: werner.klöckl@uni-leoben.at

Abstract

By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.

Keywords: directed graphs, cardinal product, graph algorithms.

2000 Mathematics Subject Classification: 05C20, 05C75, 05C85.

References

[1]	J. Feigenbaum and A.A. Schäffer, Finding the prime factors of strong direct product graphs in polynomial time, Discrete Math. 109 (1992) 77-102, doi: 10.1016/0012-365X(92)90280-S.
[2]	W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7.
[3]	W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley-Interscience, New York, 2000), Structure and recognition, With a foreword by Peter Winkler.
[4]	R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971) 59-101.

Received 13 February 2006
Revised 17 October 2006
Accepted 10 January 2007