График безразличия

В теории графов , разделе математики, граф безразличия — это неориентированный граф , построенный путем присвоения действительного числа каждой вершине и соединения двух вершин ребром, когда их числа находятся в пределах одной единицы друг от друга. ^[1] Графики безразличия также являются графами пересечения наборов единичных интервалов или правильно вложенных интервалов (интервалов, ни один из которых не содержит других). На основе этих двух типов представлений интервалов эти графики также называются графами единичных интервалов или графами собственных интервалов ; они образуют подкласс интервальных графов .

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

В модели случайных графов Эрдеша–Реньи граф -вершины , число ребер которого значительно меньше, будет графом безразличия с высокой вероятностью, тогда как граф, число ребер которого значительно больше, не будет графом безразличия с высокой вероятностью. вероятность. ^[9] $п$ $n^{2/3}$ $n^{2/3}$

Пропускная способность произвольного графа на единицу меньше размера максимальной клики в графе безразличия, который содержит подграф и выбран так, чтобы минимизировать размер максимальной клики. ^[10] Это свойство соответствует аналогичным отношениям между графами ширины пути и графами интервалов , а также между графами ширины дерева и хордальными графами . Более слабое понятие ширины, ширина клики , может быть сколь угодно большим на графах безразличия. ^[11] Однако каждый собственный подкласс графов безразличия, замкнутый относительно индуцированных подграфов, имеет ограниченную кликовую ширину. ^[12] $G$ $G$

Каждый связный граф безразличия имеет гамильтонов путь . ^[13] Граф безразличия имеет гамильтонов цикл тогда и только тогда, когда он двусвязен . ^[14]

Графы безразличия подчиняются гипотезе реконструкции : они однозначно определяются своими подграфами с удаленными вершинами. ^[15]