Amalgamation of a graph

Материал из WikiGrapp
Перейти к:навигация, поиск

Amalgamation of a graphамальгамация графа.

Amalgamating a graph \,H can be thought of as taking \,H, partitioning its vertices, then, for each element of the partition, squashing together the vertices to form a single vertex in the amalgamated graph \,G. Any edges incident with original vertices in \,H are then incident with the corresponding new vertex in \,G, and any edge joining two vertices that are squashed together in \,H becomes a loop on the new vertex in \,G. The number of vertices squashed together to form a new vertex \,w is the amalgamation number \,\eta(w) of \,w. The resulting graph is the amalgamation of the original. Formally, this is represented by a graph homomorphism f:
V(G) \rightarrow V(H); so for example if w \in V(H), then \,\eta(w)
= |f^{-1}(w)|.