Graph homomorphisms and components of quotient graphs

Bubboloni, Daniela

Rendiconti del Seminario Matematico della Università di Padova, Tome 138 (2017), pp. 39-60.

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

Classification : 05
Mots clés : Graph homomorphism, quotient graph, components, power graphs