Ссылка на класс графиков, которые сохраняют расстояния подграфа при заказе

12

Скажем, граф обладает свойством если его вершины можно упорядочить таким образом, чтобы граф индуцированный вершинами имел для всех . Другими словами, добавление следующей вершины в нашем порядке не влияет на метрику расстояния текущего графа. $G$ $M$ $v_1, v_2, \ldots v_n$ $H_i$ $\{v_1, \ldots, v_i\}$ $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ $j,k \leq i$

Примером такого графа является регулярная сетка. $n \times n$

У этого свойства или класса графиков есть имя? Были ли они изучены?

reference-request graph-theory Mich
источник

Простым примером графа, у которого нет этого свойства, является цикл для . Это связано с тем, что для любого упорядочения подграфы должны быть связаны, и поэтому в момент времени , является линией длины , и поэтому некоторые две вершины расстояние отделено.

k

$k$

k \geq 5

$k \ge 5$

H_{i}

$H_i$

i = ⌊ k / 2 ⌋ + 2 < k

$i = \lfloor k/2 \rfloor +2 < k$

H_{i}

$H_i$

i - 1

$i-1$

i - 1 > ⌊ k / 2 ⌋

$i-1 > \lfloor k/2 \rfloor$

Эндрю Морган

С другой стороны, естественным кандидатом для нахождения хорошего порядка

является создание BFS из произвольного выбора

. Рассматривая

как BFS дерево с некоторыми дополнительными кромками, похоже , единственным препятствием к наличию свойства

для там , чтобы быть что - то «вроде»

- цикла для

в

. Под «как» я подразумеваю, что существует

цикл

v_{1}, \dots, v_{n}

$v_1, \ldots, v_n$

v_{1}

$v_1$

G

$G$

M

$M$

k

$k$

k \geq 5

$k \ge 5$

G

$G$

k

$k$

с

так что

в

. Если мы назовем такой цикл «минимальным», то верно ли, что свойство

эквивалентно отсутствию минимальных циклов длины не менее 5?

v_{1}, \dots, v_{k}, v_{k + 1} = v_{1}

$v_1, \ldots, v_k, v_{k+1}=v_1$

k \geq 5

$k \ge 5$

d (v_{i}, v_{j}) = | i - j |

$d(v_i,v_j) = |i-j|$

G

$G$

M

$M$

Эндрю Морган

1

k

$k$

8

Казалось бы, вы спрашиваете о графах, допускающих порядок исключения с сохранением расстояния, который формирует класс графов, изучаемых в этой статье:

http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec

JimN
источник

2

Также свободно доступно на веб-странице автора: lif-sud.univ-mrs.fr/%7Echepoi/dpo.ps

Флоран Фуко,

8

У меня нет ответа для всего вашего класса графов, но три подкласса графов с этим свойством - это наследственно-дистанционные графы , хордовые графы и медианные графы .

$v_1$

Хордовые графы - это графы, которые имеют порядок со свойством, что каждая последующая вершина, при добавлении, имеет клику для своих соседей. Этот порядок, очевидно, сохраняет дистанцию.

Точно так же медианные графы (включая пример сетки) имеют свойство, заключающееся в том, что для любого упорядочения в ширину каждая вершина имеет окрестность гиперкуба в момент ее добавления. (См. Стр. 76–77 Eppstein et al., «Теория медиа», Springer, 2008). Опять же, это свойство означает, что сложение не может изменить расстояния между предыдущими вершинами.

Есть класс графов, для которого я не знаю названия, обобщающего как хордовые, так и дистанционно-наследственные графы, которые можно распознать за полиномиальное время и которые имеют ваше свойство. Они являются связными графами, которые можно построить из одной вершины, добавляя вершины одну за другой, где соседи каждой новой вершины являются подмножеством одной из замкнутых окрестностей предыдущего графа. Они почти (но не совсем) такие же, как демонтируемые графыразница в том, что новая вершина не обязательно должна быть смежной с вершиной, чья окрестность копируется. Порядок исключения хордального графа является конструкцией этого типа, где каждая новая вершина выбирает подмножество кликов окрестности. Аналогично, наследственно-наследственные графы имеют конструкцию такого типа, в которой соседями каждой новой вершины являются целая замкнутая окрестность, открытая окрестность или одна вершина. Каждая новая вершина не может изменять расстояния предыдущих вершин, поэтому эта последовательность построения имеет свойство, которое вы ищете.

Если вы определяете вершину v как «съемную», если она может быть последней в этой последовательности (у нее есть открытая окрестность, которая является подмножеством чужой закрытой окрестности), то удаление других удаляемых вершин не меняет возможность удаления v : если окрестность v является подмножеством u, и мы удаляем u как имеющую окрестность, которая является подмножеством w, то v все еще можно удалить, потому что его окрестность все еще является подмножеством w. Таким образом, последовательности шагов удаления, которые мы можем выполнить, чтобы вернуть график обратно в ничто, образуют антиматроиди одна такая последовательность может быть найдена за полиномиальное время жадным алгоритмом, который многократно удаляет удаляемую вершину всякий раз, когда она может ее найти. Обратный вывод этого алгоритма дает последовательность построения для данного графа. График куба дает пример графа, который имеет ваше свойство (медианный граф), но не может быть построен таким образом. Я думаю, что срединные графы, которые могут быть построены таким образом, являются в точности квадратными графами (которые включают в себя регулярные сетки). Графы, которые имеют последовательность построения этого типа, также включают в себя все графы, которые имеют универсальную вершину, такую как графы колес , поэтому (в отличие от хордовых графов и дистанционно-наследственных графов) они не являются совершенными и не замкнуты при индуцированных подграфах.

Дэвид Эппштейн
источник

свойство этого класса графиков, в котором вы не уверены, напоминает порядок исключения доминирования. Этот документ, похоже, имеет отношение к первоначальному вопросу: epubs.siam.org/doi/abs/10.1137/…

ДжимН

Я думаю, что порядок исключения доминирования может быть таким же, как и для dlsmantlability. Но вы должны связать этот документ с реальным ответом, потому что его «упорядочивающий исключающий дистанцию» кажется именно тем, о чем спрашивает исходный вопрос.

Дэвид Эппштейн

Ссылка на класс графиков, которые сохраняют расстояния подграфа при заказе

Ответы: