Существует ли круговой граф без треугольников, без звездных сечений, имеющий более n ребер?

9

Я пытаюсь найти график с этими свойствами для моих исследований, но, к сожалению, я не могу найти такой график.

Кто-нибудь знает, существует ли этот граф, или почему невозможно существовать?

Рафаэль Оливейра Лопес
источник
3
Можете ли вы объяснить свою терминологию? Что такое «без звездных сечений» и что такое «круговая диаграмма»?
Юваль Фильмус
1
Конечно. =) Круговой граф - это граф (ненаправленный), вершины которого можно связать с хордами в круге, так что две вершины смежны, если соответствующие хорды пересекаются друг с другом. Вот изображение в качестве примера (из Википедии): en.wikipedia.org/wiki/File:Circle_graph.svg И мы можем сказать, что у графа есть отрезок звезды, когда у вас есть вершина v, которая удаляет v и его соседей (N [v]) от графа получается отключить его.
Рафаэль Оливейра Лопес
1
ISGCI имеет определения без треугольников и круговой граф . Звездный срез - это подмножествоS вершин, отделяющих граф, так что одна вершина в S смежна с любой другой вершиной в S,
Джефф
Этот документ может быть актуальным.
Джефф

Ответы:

11

предполагать гявляется круговым графом без звездных разрезов без треугольников. Я покажу чтог не содержит вершины со степенью больше 2. Следовательно, г самое большее N кромки.

Рассмотрим круговое представление С из г, Набор аккордов параллелен, если нет двух из них, пересекающихся, но есть линия, пересекающая все аккорды.

Свойство 1 :С не имеет 3-х параллельных аккордов.

Доказательство . предполагатьСимеет 3 параллельных аккорда. Кондидер вершинаvсоответствующий среднему аккорду. Затем,N[v]это срез. Это доказывает собственность.

Ради противоречия предположим, г имеет вершину v степени не менее 3. Тогда аккорд, соответствующий vпересекается с 3 другими аккордами. Поскольку эти 3 аккорда пересекают одну линию, они либо параллельны, либо два из них пересекаются. Благодаря свойству 1 два из них пересекаются, что означает, что их вершины образуют треугольник сvчто противоречит г быть без треугольников.

Серж Гасперс
источник
Я не думаю, что 1-й пророчество - правда. Рассмотрим аккорды, образующие стороны регулярногоN-гона, с кругом немного больше, так что он содержит N-гон, но не содержит никаких других пересечений этих сторон.
Дэвид Эппштейн
Хорошо, как исправлено, я думаю, что это работает, и это проще, чем мое доказательство.
Дэвид Эппштейн
8

Нет, такого графа не существует. Чтобы понять, почему нет, предположим, что у нас есть круговой граф, определенный набором аккордов без треугольников. ПозволятьN быть числом вершин графа круга (или числом аккордов), и мбыть числом ребер графа (пересечения двух аккордов). Тогда простая индукция по количеству аккордов показывает, что расположение аккордов имеет точном+N+1лица. Тем не менее, есть не более2N лица, которые касаются круга (меньше, если некоторые лица касаются круга более одного раза), поэтому, если м>Nтогда должно быть как минимум две внутренние грани расположения. Позволятьпбыть кратчайшим путем в двойственном графе расположения ( квадрате ) от одного такого лица к другому, и пустьс быть любым аккордом, двойным к краю п, Тогда звездный срез, вызванныйс разделяет некоторые аккорды, ограничивающие лицо на одном конце п от некоторых аккордов, ограничивающих лицо на другом конце.

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