Ширина разреза графа и величина вершинного разделения реберного графа

Ширина разреза графа и величина вершинного разделения графа принадлежат к числу инвариантов графов, определяемых через оптимальное линейное упорядочение вершин. Подобные инварианты возникают при решении прикладных задач в таких областях, как электроника, программирование. С этим, в частности, связано их активное изучение.
В настоящей работе устанавливаются соотношения между шириной разреза графа и величиной вершинного разделения реберного графа. В частности показано, что если $G$ – связный граф, имеющий более одного ребра, все вершины которого имеют степень, не превосходящую трех, то $cw(G)=vs(L(G))$, где $L(G)$ – реберный граф графа $G$, $cw(G)$ – ширина разреза $G$, а $vs(L(G))$ – величина вершинного разделения $G$.