A note on compact graphs |
| |
Authors: | G Tinhofer |
| |
Institution: | Technische Universität München, Institut für Mathematik, Postfach 202420, D-8000 München-2, FRG |
| |
Abstract: | An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|