Гипотеза реконструкции нового орграфа - New digraph reconstruction conjecture

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Однозначно ли орграфы определяются своими подграфами и некоторыми данными в степени?
(больше нерешенных задач по математике)

В гипотеза реконструкции из Станислав Улам одна из самых известных открытых проблем в теория графов. Используя терминологию Фрэнк Харари[1] это можно сформулировать следующим образом: Если грамм и ЧАС - два графа не менее чем на трех вершинах, а bi - биекция из V(грамм) к V(ЧАС) такие, что грамм{v} и ЧАС{ƒ (v)} изоморфны для всех вершин v в V(грамм), тогда грамм и ЧАС изоморфны.

В 1964 году Харари[2] расширил гипотезу реконструкции на ориентированные графы по крайней мере на пяти вершинах в качестве так называемой гипотезы реконструкции орграфа. Многие результаты, подтверждающие гипотезу о реконструкции орграфов, появились между 1964 и 1976 годами. Однако эта гипотеза оказалась ложной, когда П. К. Стокмейер открыл несколько бесконечных семейств контрпримерных пар орграфов (включая турниры) произвольно большого порядка.[3][4][5] Ложность гипотезы реконструкции орграфа вызвала сомнения в самой гипотезе реконструкции. Штокмейер даже заметил, что «возможно, значительные усилия, затрачиваемые на попытки доказать гипотезу (реконструкции), должны быть уравновешены более серьезными попытками построить контрпримеры».[3]

В 1979 году Рамачандран возродил гипотезу реконструкции орграфа в несколько более слабой форме, названной Гипотеза реконструкции нового орграфа. В орграфе количество дуг, проходящих из (соответственно в) вершину v называется превосходить (степень ) из v и обозначается od(v) (соответственно, я бы(v)). Гипотезу о новом орграфе можно сформулировать следующим образом:

Если D и E любые два орграфа и ƒ это биекция от V(D) к V(E) такой, что D{v} и E{ƒ (v)} изоморфны и (od(v),я бы(v)) = (od(ƒ (v)),я бы(ƒ (v))) для всех v в V(D), тогда D и E изоморфны.[6][7]

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

Снижение

  • Все орграфы являются N-реконструируемыми, если все орграфы с 2-связными нижележащими графами являются N-реконструируемыми.[8]
  • Все орграфы являются N-реконструируемыми тогда и только тогда, когда любой из следующих двух классов орграфов является N-реконструируемым, где diam (D) и радиус (D) определены как диаметр и радиус основного графа D.[9]
    1. Орграфы с диаметром (D) ≤ 2 или diam (D) = diam (Dc) = 3
    2. Орграфы D с 2-связными нижележащими графами и радиусом (D) ≤ 2

Текущий статус

По состоянию на 2018 год, контрпример к гипотезе реконструкции нового орграфа не известен.

Рекомендации

  1. ^ Харари, Фрэнк (1969), Теория графов, Ридинг, Массачусетс: Эддисон-Уэсли, МИСТЕР  0256911.
  2. ^ Харари, Фрэнк (1964), «О восстановлении графа из набора подграфов», в Фидлер, М. (ред.), Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963)., Publ. Дом Чехословацкой Акад. Sci., Прага, стр. 47–52, МИСТЕР  0175111
  3. ^ а б Штокмейер, Пол К. (1977), «Ложность гипотезы реконструкции турниров», Журнал теории графов, 1 (1): 19–25, Дои:10.1002 / jgt.3190010108, МИСТЕР  0453584. Erratum, J. Graph Th. 62 (2): 199–200, 2009, Дои:10.1002 / jgt.20398, МИСТЕР2555098.
  4. ^ Штокмейер, Пол К. (1981), "Перепись невосстановимых орграфов. I. Шесть родственных семейств", Журнал комбинаторной теории, Серия B, 31 (2): 232–239, Дои:10.1016 / S0095-8956 (81) 80027-5, МИСТЕР  0630985.
  5. ^ Штокмейер, Пол К. (1991), Перепись невосстановимых диграфов II: Семейство турниров, Препринт.
  6. ^ Рамачандран, С. (1979), "Гипотеза реконструкции орграфа", Информационный бюллетень теории графов, Университет Западного Мичигана, 8 (4).
  7. ^ Рамачандран, С. (1981), "О новой гипотезе реконструкции орграфа", Журнал комбинаторной теории, Серия B, 31 (2): 143–149, Дои:10.1016 / S0095-8956 (81) 80019-6, МИСТЕР  0630977.
  8. ^ Рамачандран, S; Моникандан, S (2006). «Все орграфы являются N-реконструируемыми, если все орграфы с 2-связными нижележащими графами являются N-реконструируемыми». Utilitas Mathematica. UTIL MATH PUBL INC. 71: 225–234. МИСТЕР  2278835.
  9. ^ Рамачандран, S (2012). «Достаточные условия для N-реконструируемости всех орграфов». Utilitas Mathematica. UTIL MATH PUBL INC. 88: 183–188. МИСТЕР  2975831.