Adjacent graphs

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

H-adjacent graphs --- H-смежные графы.

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

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

See also

  • H-distance.