Adjacent graphs

[math]\displaystyle{ H }[/math]-adjacent graphs --- [math]\displaystyle{ H }[/math]-смежные графы.

Let [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math] be two graphs of the same order and same size such that [math]\displaystyle{ V(G_{1}) = V(G_{2}) }[/math], and let [math]\displaystyle{ H }[/math] be a connected graph of order 3 at least.

Two subgraphs [math]\displaystyle{ H_{1} }[/math] and [math]\displaystyle{ H_{2} }[/math] of [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math], respectively, are [math]\displaystyle{ H }[/math]-adjacent if [math]\displaystyle{ H_{1} \cong H_{2} \cong H }[/math] and [math]\displaystyle{ H_{1} }[/math] and [math]\displaystyle{ H_{2} }[/math] share some but not all edges, that is, [math]\displaystyle{ E(H_{1} \cap E(H_{2}) \neq \emptyset }[/math] and [math]\displaystyle{ E(H_{2}) - E(H_{1}) \neq \emptyset }[/math]. The graphs [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math] are themselves [math]\displaystyle{ H }[/math]-adjacent if [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math] contain [math]\displaystyle{ H }[/math]-adjacent subgraphs [math]\displaystyle{ H_{1} }[/math] and [math]\displaystyle{ H_{2} }[/math], respectively, such that [math]\displaystyle{ E(H_{2}) - E(H_{1}) \subseteq E(\bar{G}_{1}) }[/math] and [math]\displaystyle{ G_{2} = G_{1} - E(H_{1}) + E(H_{2}) }[/math].

See also

• [math]\displaystyle{ H }[/math]-distance.