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.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.