2016/05/11 by Daniela Bubboloni, Bubboloni, Daniela
Mathematics · #05C40 #05C60 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C40 #msc:05C60 #msc:05C70
paper · pdf · doi:10.48550/arxiv.1605.03549
arXiv admin note: text overlap with arXiv:1502.02966
arxiv created 2016/07/21 · arxiv updated 2016/07/25
We study how the number c(X) of components of a graph X can be expressed through the number and properties of the components of a quotient graph X/∼. 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) when the projection on the quotient X/∼ is pseudo-covering. That procedure becomes particularly easy to handle when the partition corresponding to X/∼ is an orbit partition.