Locally constrained graph homomorphisms and equitable partitions

AbstractWe explore the connection between locally constrained graph homomorphisms and degree matrices arising from an equitable partition of a graph. We provide several equivalent characterizations of degree matrices. As a consequence we can efficiently check whether a given matrix M is a degree matrix of some graph and also compute the size of a smallest graph for which it is a degree matrix in polynomial time. We extend the well-known connection between degree refinement matrices of graphs and locally bijective graph homomorphisms to locally injective and locally surjective homomorphisms by showing that these latter types of homomorphisms also impose a quasiorder on degree matrices and a partial order on degree refinement matrices. Computing the degree refinement matrix of a graph is easy, and an algorithm deciding the comparability of two matrices in one of these partial orders could be used as a heuristic for deciding whether a graph G allows a homomorphism of the given type to H. For local surjectivity and injectivity we show that the problem of matrix comparability belongs to the complexity class NP