Цитирование несовершеннолетних - это топологические минусы для подкубических графов

12

Если представляет собой график с максимальной степенью 3 и является минор H , то G является топологическим минор H .GHGH

Википедия цитирует этот результат из «Теории графов» Дистеля. В последней версии книги он указан как Опора 1.7.4. В книге нет доказательств или цитирования.

Известно ли местонахождение (оригинальное) доказательство этого?

Кроме того, есть ли ссылка, доказывающая, что если - путь или подразделение когтя и минор H, то G - подграф H ? Это упоминается здесь кратко, но не хватает ссылки.GHGH

Eli
источник
Книга доступна на diestel-graph-theory.com
Александр Лангер
Спасибо Александр. Эта версия книги не содержит ни ссылки, ни доказательства предложения. Знаете ли вы, есть ли в полном издании его или другой источник для него?
Эли
2
Я помню, как искал цитату по второму факту, который вы указали, но я ничего не нашел. Лучшая цитата, которую я знаю для первого утверждения, - это книга Дистеля, которая не подтверждает это утверждение. Я буду ждать, чтобы увидеть, если кто-то найдет цитату. Если нет, я отправлю доказательство в качестве ответа.
Робин Котари
1
@ Робин, на данный момент, если ты опубликуешь доказательства, для меня этого достаточно. Есть ли подходящий способ приписать вам этот результат где-нибудь использовать? Я не знаком с политикой обмена стека или стандартной практикой.
Эли
1
Фактически, цитирование уже обсуждалось и решалось здесь: meta.cstheory.stackexchange.com/questions/352/…
Аарон Стерлинг,

Ответы:

13

Если представляет собой график с максимальной степенью 3 и является минор H , то G является топологическим минор H .GHGH

Поскольку минор H , G можно получить из H , удалив ребра, изолированные вершины и выполнив сжатие ребер. Также легко показать, что мы можем настаивать на том, что сначала выполняются операции с подграфами, т. Е. Мы можем сначала выполнить все удаления ребер и вершин, а затем выполнить все сокращения ребер. Более того, давайте ограничим определение «сжатие ребер», чтобы запретить сжимающиеся ребра, где одна из вершин имеет степень 1. Сокращение такого ребра такое же, как удаление его, поэтому это не изменит определение младших графов.GHGH

Пусть будет графом, полученным из H , выполнив сначала все удаления ребер / вершин. H 'по- прежнему содержит G как минор. Если мы покажем, что HHHHG содержит G как топологическое минорто мы сделали, так как определение топологического несовершеннолетнему также позволяет край / вершинных удалений.HG

Поскольку можно получить из H GH от края сжатия только, и все промежуточные графики должны иметь максимальную степень 3 , так как не существует никакого способа , чтобы уменьшить максимальную степень графа путем выполнения сжатия кромки. (Это было бы возможно, если бы мы допустили сжатие ребер, падающих на вершину степени 1.)H

Итак, рассмотрим любой шаг в преобразовании H в . Единственные типы ребер, которые мы можем сжать, это те, которые имеют вершины степени 2 или одну вершину степени 2 и одну вершину степени 3. (Все другие комбинации не работают. Например, ребра с двумя вершинами степени-3 приведут к вершине степени 4 при сокращении.)G

И теперь мы закончили, так как если получается из H 2 путем сжатия ребра с двумя вершинами степени 2, то H 2 может быть получено из H 1 , выполняя разбиение ребра на этом ребре. Аналогично для ребра с одной вершиной степени 3 и одной вершиной степени 2. Таким образом, H ' может быть получено из G только путем выполнения краевых подразделений, что означает, что G является топологическим минором H 'H1H2H2H1HGGH и , следовательно , .H

Если - путь или подразделение когтя и минор H, тогда GGHG - подграф H

GHHHG

Мы также нуждались в этом результате для статьи один раз, поэтому мы включили краткое доказательство в нашу статью. Вы можете найти результат в квантовой сложности запросов свойств второстепенных замкнутых графов . Это упомянуто на странице 13. Однако этот факт скрыт в доказательстве чего-то другого и явно не сформулирован как теорема.

Также интересно то, что есть обратное утверждение к этой теореме:

GGG

Робин Котари
источник
1
Благодарю. Если вы случайно натолкнетесь на опубликованную цитату из-за этих результатов, мне все равно понравится, но это звездно.
Эли
Этот ответ теперь размещен в блоге сообщества.
Аарон Стерлинг
Хороший ответ, но я думаю, что у вашей техники запрета сокращений 1 степени есть недостаток. Например, рассмотрим G = K_4 минус любое ребро. Сжатие вдоль двух вершин степени 3 в G приведет к получению графа пути P_3 с максимальной степенью 2. Вместо этого, если вы запретите любые сокращения на ребре, которые были бы эквивалентны некоторому удалению, доказательство должно пройти. Формально вы запрещаете любое сжатие между вершиной x и y, если gamma (x) \ {y} = gamma (y) \ x. Легко показать, что любое сжатие, не нарушающее это ограничение, приведет к новой вершине неуменьшенной степени.
RussellStewart
@ user2237635: Вы правы, спасибо.
Робин Котари