Wilfried IMRICH i Clemens BRAND

(University of Mining and Metallurgy, Leoben, Austria)

Recognizing Graph Products

Part I. Local and Global Distance Based Methods

Many well known classes of graphs, like hypercubes, Hamming graphs, partial cubes and median graphs are either products themselves or isometric subgraphs, resp. retracts of products. They have been extensively studied, with special emphasis on their structural properties, fast recognition algorithms, and symmetry properties. In this context the recognition of graphs that are only approximately products has also become important.

This talk describes local and global methods for the recognition of the Cartesian, the strong, and the direct product of graphs, and presents ideas on their adaption to the recognition of approximate graph products.

Part II. Spectral Methods

For a product graph, the eigenvalues of its graph Laplacian reveals more or less directly (Cartesian or direct product, respectively) the factorization. The talk explores the connections between spectral properties and product structure. It ends with ideas how spectral methods can be extended to the recognition of approximate graph products.

Serdecznie zapraszamy wszystkich chêtnych !