Построение графов, в которых каждая пара вершин имеет единого общего соседа

19

Позволять грамм быть простым графиком на N вершины (N>3) без вершины степени N-1, Предположим, что для любых двух вершинграмм, есть уникальная вершина, смежная с ними обоими. Ван Линт и Уилсон - это курс из курса по комбинаторике , чтобы доказать, что такой граф является регулярным.

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

Какие-либо предложения?

Примечание: что касается доказательства того, что такой граф является регулярным, то он оказывается довольно простым, грубая идея состоит в том, чтобы спарить соседей каждой пары вершин, используя критерии уникального общего соседа, чтобы установить тот факт, что каждая пара вершины имеют одинаковую степень, и тогда аргумент транзитивности с помощью ограничения no-global-vertex дает нам регулярность графа.

Neeldhara
источник

Ответы:

17

Если вы избавитесь от "нет вершины степени N-1«Условие, графы с тем свойством, что каждые две вершины имеют ровно одного общего соседа, являются в точности графами дружбы (набором треугольников, склеенных вместе в общей вершине); как описывает связанная статья, это теорема Эрдеша, Реньи, и Sós. Но, очевидно, все такие графы имеют вершину степениN-1; единственный правильный - треугольник. Таким образом, ответ на ваш вопрос заключается в том, что нет, граф с общим свойством соседа и без степениN-1 вершина не существует.

Дэвид Эппштейн
источник
Почему спасибо - это отлично. Это также объясняет все трудности, с которыми мы сталкивались при построении этих графов без глобальной вершины!
Нилдхара