Adjacent graphs

Материал из WikiGrapp
Версия от 15:48, 18 января 2011; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>H</math>-adjacent graphs''' --- <math>H</math>-смежные графы. Let <math>G_{1}</math> and <math>G_{2}</math> be two ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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