Fiala, J. and Paulusma, Daniel and Telle, J.A. (2008) 'Locally constrained graph homomorphisms and equitable partitions.', European journal of combinatorics., 29 (4). pp. 850-880.
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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (533Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.ejc.2007.11.006|
|Publisher statement:||NOTICE: this is the author's version of a work that was accepted for publication in European journal of combinatorics.|
|Record Created:||06 Oct 2010 14:20|
|Last Modified:||03 Apr 2013 13:18|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|