Запрещенные миноры для графов с ограниченным родом

16

Хорошо известно, что K5 и K3,3 являются запрещенными минорами для плоских графов. Существуют сотни запрещенных миноров для графов, встраиваемых в тор. Количество запрещенных миноров для графов, встраиваемых на поверхность рода g, является экспоненциальной функцией от g . Мой вопрос заключается в следующем:

Существует ли явный граф Gt на t вершинах (который не является полным графом), такой, что Gt является запрещенным минором для графов, вложимых в поверхность рода g , где t является функцией от g ?

РЕДАКТИРОВАТЬ: я понял, что следующая теорема известна:

Для любой поверхности Σ существует такое целое число r , что K3,r не вкладывается в Σ.

Итак, я ищу Gt который не является полным графом, а не полным двудольным графом.

Шива Кинтали
источник
3
Итак, вы хотите красиво сконструированное, параметризованное, бесконечное семейство графов (кроме полных графов), которые являются запрещенными минорами для поверхностей любого рода?
Деррик Столи
@Derrick. Да. Точно.
Шива Кинтали
Тогда я бы перефразировал вопрос, используя такие термины: «Существует ли (простое в построении) семейство графов так что H gK n является минимальным запрещенным минором для графов, вложимых в поверхность рода g{Hg:g1}HgKng
Деррик Столи
Ограничение « и K 3 , 3 не являются минорами G » не может быть тем, что вы хотите. Если они не миноры группы G , то группа G планарна и не может быть запрещенной группой для более высокого рода. K5K3,3GGG
Дэвид Эппштейн
@DavidEppstein Я удалил свои модификации. По сути, я ищу препятствия, которые «отличаются» от и K 33 . K5K33
Шива Кинтали

Ответы:

15

Несвязное объединение копий K 5 (или K 3 , 3 ) является минимальным запрещенным минором для графов рода n - 1 ; то же самое верно для графа, в котором некоторые из этих копий имеют общую вершину, так что блоками графа являются K 5 или K 3 , 3 . Это следует из результатов J. Battle, F. Harary, Y. Kodama и JWT Youngs, «Аддитивность рода графа», Bull. Amer. Математика Soc.nK5K3,3n1K5K3,368 (1962) 565–568, и этого уже достаточно, чтобы показать, что по крайней мере экспоненциально много запрещенных несовершеннолетних.

Боян Мохар, "Препятствие для вложения графов в поверхности", Дискрет. 78 (1989) 135–142, перечисляет график, образованный из путем удаления 4-цикла как имеющего род 2. Поскольку K 7 является тороидальным, это означает, что либо K 8C 4, либо один из его охватывающих подграфов является препятствием вложение торов, и графы, которые имеют n копий этого графа в качестве своих блоков, имеют род 2 n .K8K7K8C4n2n

Мохар также показывает, что граф, образованный из -цикла путем соединения вершины 0 со всеми четными вершинами и вершины 1 со всеми нечетными вершинами, имеет «относительный род», по крайней мере, k / 2 . График плоский, но я думаю, что относительный род означает, что цикл должен быть лицом; или вы можете добавить в граф другую вершину, связанную со всеми вершинами цикла, чтобы эффективно заставить ее быть гранью. Может быть, это ближе к тому, что вы хотите. Но я не думаю, что он показывает, что эти графики являются минимально запрещенными несовершеннолетними.(2k+2)k/2

Дэвид Эппштейн
источник
Ваш последний абзац о цикле - это то, что я ищу. Благодарю. Я принимаю ваш ответ. (2k+2)
Шива Кинтали