Deficiency of a bipartite graph

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

Deficiency of a bipartite graph --- дефицит двудольного графа.

For a vertex v, the deficiency of a bipartite graph D(v) is a set of pairs defined by D(v) = \{(x,y)| v \in N(x), v \in N(y), x \not \in N(y), x \neq
y\}. So a vertex v is simplicial if D(v) = \emptyset.

For an edge (x,y), the deficiency of a bipartite graph is the set of pairs defined by D(x,y) = \{(a,b)| a, b \in N(x) \cup N(y), (a,b) \not \in E\}. So an edge (x,y) is bisimplicial if D(x,y) = \emptyset.

Here N(v) denotes a neighbourhood of v.