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.
DOI : 10.4171/RSMUP/138-2
Mots clés : Graph homomorphism, quotient graph, components, power graphs
@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 :