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. 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 is pseudo-covering. That procedure becomes particularly easy to handle when the partition corresponding to the quotient graph is an orbit partition.

Graph homomorphisms and components of quotient graphs / Bubboloni, Daniela. - In: RENDICONTI DEL SEMINARIO MATEMATICO DELL'UNIVERSITA' DI PADOVA. - ISSN 0041-8994. - STAMPA. - 138:(2017), pp. 39-60. [10.4171/RSMUP/138-2]

Graph homomorphisms and components of quotient graphs

BUBBOLONI, DANIELA
2017

Abstract

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. 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 is pseudo-covering. That procedure becomes particularly easy to handle when the partition corresponding to the quotient graph is an orbit partition.
2017
138
39
60
Bubboloni, Daniela
File in questo prodotto:
File Dimensione Formato  
graph-hom-print-version.pdf

Accesso chiuso

Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 235.57 kB
Formato Adobe PDF
235.57 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1089856
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact