Graph homomorphisms and components of quotient graphs

  • Daniela Bubboloni

    Università degli Studi di Firenze, Italy

Abstract

We study how the number c(X)c(X) of components of a graph XX can be expressed through the number and properties of the components of a quotient graph X/X/\sim. 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 c(X)c(X) when the projection on the quotient X/X/\sim is pseudo-covering. That procedure becomes particularly easy to handle when the partition corresponding to X/X/\sim 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