Haven (graph theory)

In graph theory, if $G$ is a graph, and $k \ge 0$ is an integer, a haven of order $k$ in $G$ is a function assigning to every set $X \subseteq V(G)$ with $\big|X\big| < k$ a vertex set of a component of $G \big\backslash X$ , $\beta\big(X\big)$ , such that if $X \subseteq Y \subseteq V(G)$ and $\big|Y\big| < k$ , then $\beta(Y) \subseteq \beta(X)$ . In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Mathematics and Computer science, a graph is the basic object of study in Graph theory.

The Min-max theorem for tree-width states that a graph has a haven of order $k$ if and only if it has tree width at least $k - 1$ . In Graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph

This combinatorics-related article is a stub. Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects You can help Wikipedia by expanding it.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |