Graph homomorphisms and components of quotient graphs
Rendiconti del Seminario Matematico della Università di Padova, Tome 138 (2017), pp. 39-60.

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.

Publié le :
DOI : 10.4171/RSMUP/138-2
Classification : 05
Mots clés : Graph homomorphism, quotient graph, components, power graphs
Bubboloni, Daniela 1

1 Università degli Studi di Firenze, Italy
@article{RSMUP_2017__138__39_0,
     author = {Bubboloni, Daniela},
     title = {Graph homomorphisms and components of quotient graphs},
     journal = {Rendiconti del Seminario Matematico della Universit\`a di Padova},
     pages = {39--60},
     publisher = {European Mathematical Society Publishing House},
     address = {Zuerich, Switzerland},
     volume = {138},
     year = {2017},
     doi = {10.4171/RSMUP/138-2},
     mrnumber = {3743244},
     zbl = {1387.05164},
     url = {http://www.numdam.org/articles/10.4171/RSMUP/138-2/}
}
TY  - JOUR
AU  - Bubboloni, Daniela
TI  - Graph homomorphisms and components of quotient graphs
JO  - Rendiconti del Seminario Matematico della Università di Padova
PY  - 2017
SP  - 39
EP  - 60
VL  - 138
PB  - European Mathematical Society Publishing House
PP  - Zuerich, Switzerland
UR  - http://www.numdam.org/articles/10.4171/RSMUP/138-2/
DO  - 10.4171/RSMUP/138-2
ID  - RSMUP_2017__138__39_0
ER  - 
%0 Journal Article
%A Bubboloni, Daniela
%T Graph homomorphisms and components of quotient graphs
%J Rendiconti del Seminario Matematico della Università di Padova
%D 2017
%P 39-60
%V 138
%I European Mathematical Society Publishing House
%C Zuerich, Switzerland
%U http://www.numdam.org/articles/10.4171/RSMUP/138-2/
%R 10.4171/RSMUP/138-2
%F RSMUP_2017__138__39_0
Bubboloni, Daniela. Graph homomorphisms and components of quotient graphs. Rendiconti del Seminario Matematico della Università di Padova, Tome 138 (2017), pp. 39-60. doi : 10.4171/RSMUP/138-2. http://www.numdam.org/articles/10.4171/RSMUP/138-2/

Cité par Sources :