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

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

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

graph-theory graph-classes Рафаэль Оливейра Лопес
источник

Можете ли вы объяснить свою терминологию? Что такое «без звездных сечений» и что такое «круговая диаграмма»?

Юваль Фильмус

Конечно. =) Круговой граф - это граф (ненаправленный), вершины которого можно связать с хордами в круге, так что две вершины смежны, если соответствующие хорды пересекаются друг с другом. Вот изображение в качестве примера (из Википедии): en.wikipedia.org/wiki/File:Circle_graph.svg И мы можем сказать, что у графа есть отрезок звезды, когда у вас есть вершина v, которая удаляет v и его соседей (N [v]) от графа получается отключить его.

Рафаэль Оливейра Лопес

ISGCI имеет определения без треугольников и круговой граф . Звездный срез - это подмножество

S

$S$ вершин, отделяющих граф, так что одна вершина в

S

$S$ смежна с любой другой вершиной в

S

$S$ ,

Джефф

Этот документ может быть актуальным.

Джефф

Ответы:

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

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

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

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

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

Серж Гасперс
источник

Я не думаю, что 1-й пророчество - правда. Рассмотрим аккорды, образующие стороны регулярного

n

$n$ -гона, с кругом немного больше, так что он содержит

n

$n$ -гон, но не содержит никаких других пересечений этих сторон.

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

Хорошо, как исправлено, я думаю, что это работает, и это проще, чем мое доказательство.

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

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

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