Forbidden subgraph

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

Forbidden subgraph --- запрещенный подграф.

1. If $H_{1}, \ldots, H_{k} \; (k \geq 1)$ are graphs, then a graph $G$ is said to be $H_{1}, \ldots, H_{k}$-free if $G$ contains no copy of any of the graphs $H_{1}, \ldots, H_{k}$ as an induced subgraph; the graphs $H_{1}, \ldots, H_{k}$ will be also referred to in this context as forbidden subgraphs.

2. A cf-graph $G$ with the initial node $p_0$ has a forbidden subgraph if there exist distinct nodes $p_1$,$p_2$ and $p_3$ and simple paths $P_{0,1}$, $P_{1,2}$, $P_{1,3}$, $P_{2,3}$, $P_{3,2}$, where $P_{i,j}$ denotes a path from $p_i$ to $p_j$, that do not intersect on internal nodes.