Skip to main content

Research Repository

Advanced Search

Matrix and graph orders derived from locally constrained graph homomorphisms

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

Authors

J. Fiala

J. A. Telle



Contributors

J. Jedrzejowicz
Editor

A. Szepietowski
Editor

Abstract

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.

Citation

Fiala, J., Paulusma, D., & Telle, J. A. (2005). Matrix and graph orders derived from locally constrained graph homomorphisms. In J. Jedrzejowicz, & A. Szepietowski (Eds.), Mathematical foundations of computer science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 29 August 29-2September 2005 ; proceedings (340-351). https://doi.org/10.1007/11549345_30

Conference Name 30th International Symposium on Mathematical Foundations of Computer Science : MFCS 2005
Conference Location Gdansk, Poland
Start Date Aug 29, 2023
End Date Sep 2, 2005
Publication Date 2005-08
Deposit Date Oct 30, 2008
Pages 340-351
Series Title Lecture notes in computer science
Series Number 3618
Series ISSN 0302-9743
Book Title Mathematical foundations of computer science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 29 August 29-2September 2005 ; proceedings
DOI https://doi.org/10.1007/11549345_30
Keywords Bijective, Injective, Surjective, Partial orders.
Public URL https://durham-repository.worktribe.com/output/1164110
Additional Information 29 August - 2 September, 2005.


You might also like



Downloadable Citations