Какое правильное определение

Как следует из названия, каково правильное определение -tree? Есть несколько работ, в которых говорится о k- деревьях и частичных k- деревьях как об альтернативных определениях для графов с ограниченной шириной дерева, и я видел много, казалось бы, неправильных определений. Например, по крайней мере одно место определяет k- деревья следующим образом:$k$$k$$k$$k$

Граф называется деревом тогда и только тогда, когда либо G является полным графом с k вершинами, либо G имеет вершину v со степенью k - 1 , для которой G ∖ v является k- деревом. Частичное k- дерево - это любой подграф k- дерева.$k$$G$$k$$G$$v$$k − 1$$G \setminus v$$k$$k$$k$

Согласно этому определению можно создать следующий график:

1. Начните с ребра , 2- дерево.$(v_1, v_2)$$2$
2. Для создайте вершину v i и сделайте ее смежной с v i - 1 и v i - 2 .$i=1\ldots n$$v_i$$v_{i-1}$$v_{i-2}$

Это создаст полосу из квадратов с диагоналями. Точно так же мы можем начать создавать полосу из первого квадрата в направлении, ортогональном полосе выше. Тогда у нас будет первый ряд и первый столбец сетки n × n . Заполнить сетку легко, создавая вершины и соединяя их с вершинами сверху и слева.$n$$n \times n$

Конечным результатом является график, который содержит сетку , которая, как известно, имеет ширину дерева $n\times n$$n$ .

Правильное определение деревьев должно быть следующим:$k$

Граф называется деревом тогда и только тогда, когда либо G является полным графом с k вершинами, либо G имеет вершину v со степенью k - 1, такую, что сосед v образует k -клик, а G v является к- дерево$k$$G$$k$$G$$v$$k-1$$v$$k$$G \ v$$k$

Тогда сетчатый граф, описанный выше, не может быть создан.

Я прав?

Я в основном согласен с вами, с помощью лишь небольшой модификации:

Граф $G$ является $k$ -tree тогда и только тогда , когда либо $G$ является полным графом с $k+1$ вершин, или $G$ имеет вершину $v$ такой , что (открытая) окрестность $v$ образует $k$ -clique, и $G - v$ является $k$ -tree.

Другими словами, $v$ должно иметь степень $k$ , а не $k-1$ в вашем определении.

Я лично предпочитаю определение снизу вверх, но это всего лишь вопрос вкуса:

• Полный граф на $k+1$ вершинах является $k$ деревом.
• $k$ -tree $G$ с $n+1$ вершин ( $n\ge k+1$ ) может быть изготовлен из $k$ -tree $H$ с $n$ вершинами, добавив вершину , смежную с точно $k$ вершины , которые образуют $k$ -clique в $H$ .
• Другие графы не являются $k$ деревьями.

Это определение является слегка измененной версией определения из лекционных заметок Пинара Хеггернеса .