We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Matrix and graph orders derived from locally constrained graph homomorphisms.

Fiala, J. and Paulusma, Daniel and Telle, J. A. (2005) 'Matrix and graph orders derived from locally constrained graph homomorphisms.', in Mathematical foundations of computer science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 29 August 29-2September 2005 ; proceedings. Berlin: Springer, pp. 340-351. Lecture notes in computer science. (3618).


We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. 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 the orders imposed on degree refinement matrices by our locally constrained graph homomorphisms are also partial orders. We provide several equivalent characterizations of degree (refinement) matrices, e.g. in terms of the dimension of the cycle space of a graph related to the matrix. 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.

Item Type:Book chapter
Keywords:Bijective, Injective, Surjective, Partial orders.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:August 2005
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar