In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the cutwidth of an
undirected graph is the smallest
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
with the following property: there is an ordering of the
vertices of , such that for every , there are at most edges with one endpoint in and the other endpoint in .
See also
*
Pathwidth
*
Treewidth
References
{{reflist
Integers
Graph invariants