Locally constrained graph homomorphisms and equitable partitions

Fiala, J.; Paulusma, D.; Telle, J.A.

doi:10.1016/j.ejc.2007.11.006

Locally constrained graph homomorphisms and equitable partitions

Fiala, J.; Paulusma, D.; Telle, J.A.

Authors

J. Fiala

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

J.A. Telle

Abstract

We 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.

Citation

Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006

Journal Article Type	Article
Publication Date	May 1, 2008
Deposit Date	Oct 6, 2010
Publicly Available Date	Oct 7, 2010
Journal	European Journal of Combinatorics
Print ISSN	0195-6698
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	29
Issue	4
Pages	850-880
DOI	https://doi.org/10.1016/j.ejc.2007.11.006
Public URL	https://durham-repository.worktribe.com/output/1517137