

![0_image_1.png](0_image_1.png)

![0_image_0.png](0_image_0.png)

Abbildung 1: Graphs X and Y with association graph Z = X  Y for the maximum common connectivity preserving induced subgraph problem. Different fillings refer to different vertex attributes. All edges have the same attribute.

Highlighted edges in X and Y correspond to isomophic subgraphs. Note that the highlighted subgraph in X is not induced. Highlighted edges in Z
refer to the maximum clique.

Example 4. Consider the set Mm of partial morphisms φ : V (X) → V (Y ) *with*
D(φ) ≤ m < |X|, where m ≥ 2. There is no property p on IXY *such that* Mm is p*-closed.*
Proof: Let p denote the property on IXY such that the set of all partial morphisms MXY is p-closed. According to Proposition 1, such a property exists. Consider the set M2. It is easy to see that

$$\bigcup_{\phi\in{\mathcal{M}}_{2}}\Gamma(\phi)={\mathcal{R}}_{X Y}^{\mathfrak{p}}.$$

On one hand, the relation R
p XY is too large, because it admits arbitrary partial morphisms as p-morphisms. On the other hand, R
p XY is a minimal set in the following sense:
If we remove an element (i, r) from R
p XY , then the morphism φ ∈ M2 with i φ = r is no longer a p-morphism. This shows the assertion.

## 3.2 Construction Of An Association Graph

We present the usual constructive definition of an association graph for GMP (5) defined on a p-closed search space M.

For each element (i, r) ∈ IXY , we check whether item i from X and item r from Y can be associated to a vertex or edge in an association graph. The morphisms from the search space M determine the association rule via its describing property p. We associate item i from X with item r from Y if they are p-similar. Thus, an **association** graph Z = X  Y is a weighted graph with vertex and edge set

$$\begin{array}{l}{{V(Z)=\left\{i r\,:\,(i,i)\sim_{\mathfrak{p}}(r,r)\right\}\subseteq V(X)\times V(Y)}}\\ {{E(Z)=\left\{(i r,j s)\,:\,(i,j)\sim_{\mathfrak{p}}(r,s)\right\}\subseteq V(Z)\times V(Z).}}\end{array}$$
