Graph homomorphisms and components of quotient graphs

  • Daniela Bubboloni

    Università degli Studi di Firenze, Italy

Abstract

We study how the number of components of a graph can be expressed through the number and properties of the components of a quotient graph . We partially rely on classic qualifications of graph homomorphisms such as locally constrained homomorphisms and on the concept of equitable partition and orbit partition. We introduce the new definitions of pseudo-covering homomorphism and of component equitable partition, exhibiting interesting inclusions among the various classes of considered homomorphisms. As a consequence, we find a procedure for computing when the projection on the quotient is pseudo-covering. That procedure becomes particularly easy to handle when the partition corresponding to is an orbit partition.

Cite this article

Daniela Bubboloni, Graph homomorphisms and components of quotient graphs. Rend. Sem. Mat. Univ. Padova 138 (2017), pp. 39–60

DOI 10.4171/RSMUP/138-2