Линейный график

В математической дисциплине теории графов линейный граф неориентированного графа $G$ — это другой граф $L(G)$ , который представляет смежности между ребрами G . $L($ $G$ $)$ строится следующим образом: для каждого ребра в $G$ создаем вершину в $L($ $G$ $)$ ; для каждых двух ребер в $G$ $,$ имеющих общую вершину, создаем ребро между их соответствующими вершинами в $L($ $G$ $)$ .

Название «линейный граф» происходит из статьи Харари и Нормана (1960), хотя и Уитни (1932), и Краус (1943) использовали эту конструкцию до этого. ^[1] Другие термины, используемые для обозначения линейного графа, включают покрывающий граф , производный , дуальный граф от ребра к вершине , сопряженный граф , представительный граф и θ-образ , ^[1] а также реберный граф , граф обмена , присоединенный граф и производный граф . ^[2]

Хасслер Уитни (1932) доказал, что в одном исключительном случае структура связного графа $G$ может быть полностью восстановлена из его линейного графа. ^[3] Многие другие свойства линейных графов следуют из перевода свойств базового графа из вершин в ребра, и по теореме Уитни тот же перевод может быть сделан и в другом направлении. Линейные графы не имеют клешней , а линейные графы двудольных графов являются совершенными . Линейные графы характеризуются девятью запрещенными подграфами и могут быть распознаны за линейное время .

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

Формальное определение

Для данного графа $G$ его линейный граф $L (G)$ является графом таким, что

каждая вершина L $($ $G$ $)$ представляет собой ребро $G$ ; $и$
две вершины $L (G)$ являются смежными тогда и только тогда, когда их соответствующие ребра имеют общую конечную точку («являются инцидентными») в $G$ .

То есть, это граф пересечений ребер $G$ , представляющий каждое ребро набором из его двух конечных точек. ^[2]

Пример

На следующих рисунках показан граф (слева, с синими вершинами) и его линейный граф (справа, с зелеными вершинами). Каждая вершина линейного графа обозначена парой конечных точек соответствующего ребра в исходном графе. Например, зеленая вершина справа, обозначенная 1,3, соответствует ребру слева между синими вершинами 1 и 3. Зеленая вершина 1,3 смежна с тремя другими зелеными вершинами: 1,4 и 1,2 (соответствующими ребрам, разделяющим конечную точку 1 в синем графе) и 4,3 (соответствующими ребру, разделяющему конечную точку 3 в синем графе).

График G
Вершины в L( G ), построенные из ребер в G
Добавлены ребра в L( G )
Линейный график L( G )

Характеристики

Переводимые свойства базового графа

Свойства графа $G$ , зависящие только от смежности между ребрами, могут быть переведены в эквивалентные свойства в $L (G)$ , зависящие от смежности между вершинами. Например, паросочетание в $G$ представляет собой набор ребер, никакие два из которых не являются смежными, и соответствует набору вершин в $L (G),$ никакие две из которых не являются смежными, то есть независимому набору . ^[4]

Таким образом,

Линейный граф связного графа связен. Если $G$ связен, он содержит путь , соединяющий любые два его ребра, что переводится в путь в $L (G),$ содержащий любые две вершины $L (G)$ . Однако граф $G$ , имеющий некоторые изолированные вершины и, следовательно, несвязный, может, тем не менее, иметь связный линейный граф. ^[5]
Линейный граф имеет точку сочленения тогда и только тогда, когда базовый граф имеет мост , для которого ни одна из конечных точек не имеет степени один. ^[2]
Для графа $G$ с $n$ вершинами и $m$ ребрами число вершин линейного графа $L (G)$ равно $m$ , а число ребер $L (G)$ равно половине суммы квадратов степеней вершин в $G$ минус $m$ . ^[6]
Независимое множество в $L (G)$ соответствует паросочетанию в $G$ . В частности, максимальное независимое множество в $L (G)$ соответствует максимальному паросочетанию в $G$ . Поскольку максимальные паросочетания могут быть найдены за полиномиальное время, то же самое можно сделать и с максимальными независимыми множествами линейных графов, несмотря на сложность задачи максимального независимого множества для более общих семейств графов. ^[4] Аналогично, радужно-независимое множество в $L (G)$ соответствует радужному паросочетанию в $G$ .
Хроматическое число ребра графа $G$ равно хроматическому числу вершины его линейного графа $L (G)$ . ^[7]
Линейный граф рёберно-транзитивного графа является вершинно-транзитивным . Это свойство может быть использовано для генерации семейств графов, которые (как граф Петерсена ) являются вершинно-транзитивными, но не являются графами Кэли : если $G$ является рёберно-транзитивным графом, имеющим по крайней мере пять вершин, не является двудольным и имеет нечётные степени вершин, то $L (G)$ является вершинно-транзитивным не-графом Кэли. ^[8]
Если граф $G$ имеет цикл Эйлера , то есть если $G$ связен и имеет четное число ребер в каждой вершине, то линейный граф $G$ является гамильтоновым . Однако не все гамильтоновы циклы в линейных графах происходят из циклов Эйлера таким образом; например, линейный граф гамильтонова графа $G$ сам является гамильтоновым, независимо от того, является ли $G$ также эйлеровым. ^[9]
Если два простых графа изоморфны, то их линейные графы также изоморфны. Теорема Уитни об изоморфизме графов обеспечивает обратное утверждение для всех, кроме одной пары связных графов.
В контексте теории сложных сетей линейный граф случайной сети сохраняет многие свойства сети, такие как свойство малого мира (существование коротких путей между всеми парами вершин) и форму ее распределения степеней . ^[10] Эванс и Ламбиотт (2009) отмечают, что любой метод поиска кластеров вершин в сложной сети может быть применен к линейному графу и использован вместо этого для кластеризации его ребер.

Теорема изоморфизма Уитни

Если линейные графы двух связных графов изоморфны, то и базовые графы изоморфны, за исключением случая треугольного графа $K 3$ и клешни $K 1,3$ , которые имеют изоморфные линейные графы, но сами по себе не изоморфны. ^[3]

Помимо $K 3$ и $K 1,3$ , существуют некоторые другие исключительные малые графы со свойством, что их линейный граф имеет более высокую степень симметрии, чем сам граф. Например, ромбовидный граф $K 1,1,2$ (два треугольника, разделяющие ребро) имеет четыре автоморфизма графа , но его линейный граф $K 1,2,2$ имеет восемь. На иллюстрации показанного ромбовидного графа поворот графа на 90 градусов не является симметрией графа, но является симметрией его линейного графа. Однако все такие исключительные случаи имеют не более четырех вершин. Усиленная версия теоремы Уитни об изоморфизме утверждает, что для связных графов с более чем четырьмя вершинами существует взаимно-однозначное соответствие между изоморфизмами графов и изоморфизмами их линейных графов. ^[11]

Аналоги теоремы Уитни об изоморфизме были доказаны для линейных графов мультиграфов , но в этом случае они более сложны. ^[12]

Сильно регулярные и совершенные линейные графики

Линейный граф полного графа $K n$ также известен как треугольный граф , граф Джонсона $J (n, 2)$ или дополнение графа Кнезера $KG n,2$ . Треугольные графы характеризуются своими спектрами , за исключением $n = 8$ . ^[13] Они также могут быть охарактеризованы (опять же за исключением $K 8$ ) как сильно регулярные графы с параметрами $srg(n (n - 1)/2, 2(n - 2), n - 2, 4)$ . [ ^14] Три сильно регулярных графа с теми же параметрами и спектром, что и $L (K 8)$ являются графами Чанга , которые могут быть получены переключением графов из $L (K 8)$ .

Линейный граф двудольного графа является совершенным (см. теорему Кёнига ), но не обязательно двудольным, как показывает пример графа-клешни. Линейные графы двудольных графов образуют один из ключевых строительных блоков совершенных графов, используемых в доказательстве сильной теоремы о совершенном графе . ^[15] Особым случаем этих графов являются графы ладьи , линейные графы полных двудольных графов . Как и линейные графы полных графов, их можно охарактеризовать, за одним исключением, по их количеству вершин, количеству ребер и количеству общих соседей для смежных и несмежных точек. Единственным исключительным случаем является $L (K 4,4)$ , который разделяет свои параметры с графом Шрикханде . Когда обе стороны двудольного графа имеют одинаковое количество вершин, эти графы снова являются сильно регулярными. ^[16]

В более общем смысле граф $G$ называется линейно совершенным графом, если $L (G)$ является совершенным графом . Линейно совершенные графы — это в точности те графы, которые не содержат простых циклов нечетной длины, большей трех. ^[17] Эквивалентно, граф является линейно совершенным тогда и только тогда, когда каждый из его двусвязных компонентов является либо двудольным, либо имеет форму $K 4$ (тетраэдр) или $K 1,1, n$ (книга из одного или нескольких треугольников, имеющих общее ребро). ^[18] Каждый линейно совершенный граф сам по себе совершенен. ^[19]

Другие связанные семейства графов

Все линейные графы являются графами без клешней , графами без индуцированного подграфа в форме дерева с тремя листьями. ^[20] Как и в случае с графами без клешней в более общем смысле, каждый связный линейный граф $L (G)$ с четным числом ребер имеет совершенное паросочетание ; ^[21] эквивалентно, это означает, что если базовый граф $G$ имеет четное число ребер, его ребра можно разбить на двухреберные пути.

Линейные графы деревьев — это в точности блочные графы без клешней . ^[22] Эти графы использовались для решения задачи в теории экстремальных графов , построения графа с заданным числом ребер и вершин, наибольшее дерево которого, индуцированное как подграф, является наименьшим из возможных. ^[23]

Все собственные значения матрицы смежности $A$ линейного графа не меньше −2. Причина этого в том, что $A$ можно записать как , где $J$ — беззнаковая матрица инцидентности предлинейного графа, а $I$ — тождество. В частности, $A$ $+ 2$ $I$ — матрица Грама системы векторов: все графы с этим свойством были названы обобщенными линейными графами. ^[24] $A=J^{\mathsf {T}}J-2I$

Характеристика и распознавание

Раздел клики

Для произвольного графа $G$ и произвольной вершины $v$ в $G$ множество ребер, инцидентных $v,$ соответствует клике в линейном графе $L (G)$ . Клики, образованные таким образом, разбивают ребра $L (G)$ . Каждая вершина $L (G)$ принадлежит ровно двум из них (двум кликам, соответствующим двум конечным точкам соответствующего ребра в $G$ ).

Существование такого разбиения на клики можно использовать для характеристики линейных графов: Граф $L$ является линейным графом некоторого другого графа или мультиграфа тогда и только тогда, когда возможно найти набор клик в $L$ (позволяя некоторым кликам быть одиночными вершинами), которые разбивают ребра $L$ таким образом, что каждая вершина $L$ принадлежит ровно двум кликам. ^[20] Это линейный граф графа (а не мультиграф), если этот набор клик удовлетворяет дополнительному условию, что никакие две вершины $L$ не находятся одновременно в тех же двух кликах. При наличии такого семейства клик базовый граф $G$ , для которого $L$ является линейным графом, может быть восстановлен путем создания одной вершины в $G$ для каждой клики и ребра в $G$ для каждой вершины в $L$ с его конечными точками, являющимися двумя кликами , содержащими вершину в $L.$ Согласно сильной версии теоремы Уитни об изоморфизме, если базовый граф $G$ имеет более четырех вершин, может быть только одно разбиение этого типа.

Например, эту характеристику можно использовать, чтобы показать, что следующий график не является линейным:

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

Запрещенные подграфы

Другая характеристика линейных графов была доказана в Beineke (1970) (и ранее сообщена без доказательства Beineke (1968)). Он показал, что существует девять минимальных графов, которые не являются линейными графами, таких, что любой граф, который не является линейным графом, имеет один из этих девяти графов в качестве индуцированного подграфа . То есть граф является линейным графом тогда и только тогда, когда никакое подмножество его вершин не индуцирует один из этих девяти графов. В приведенном выше примере четыре самые верхние вершины индуцируют клешню (то есть полный двудольный граф $K 1,3$ ), показанную в верхнем левом углу иллюстрации запрещенных подграфов. Следовательно, согласно характеристике Beineke, этот пример не может быть линейным графом. Для графов с минимальной степенью не менее 5 в характеристике необходимы только шесть подграфов в левом и правом столбцах рисунка. ^[25]

Алгоритмы

Руссопулос (1973) и Лехот (1974) описали линейные алгоритмы времени для распознавания линейных графов и реконструкции их исходных графов. Сысло (1982) обобщил эти методы на направленные графы . Дегиорджи и Саймон (1995) описали эффективную структуру данных для поддержания динамического графа, подверженного вставкам и удалениям вершин, и поддержания представления входных данных в виде линейного графа (когда он существует) за время, пропорциональное количеству измененных ребер на каждом шаге.

Алгоритмы Руссопулоса (1973) и Лехота (1974) основаны на характеристиках линейных графов, включающих нечетные треугольники (треугольники в линейном графе со свойством, что существует другая вершина, смежная с нечетным числом вершин треугольника). Однако алгоритм Дегиорджи и Саймона (1995) использует только теорему Уитни об изоморфизме. Он усложняется необходимостью распознавать удаления, которые заставляют оставшийся граф становиться линейным графом, но при специализации на статической задаче распознавания необходимо выполнять только вставки, и алгоритм выполняет следующие шаги:

Постройте входной граф $L$ , добавляя вершины по одной за раз, на каждом шаге выбирая вершину для добавления, которая смежна хотя бы с одной ранее добавленной вершиной. Добавляя вершины в $L$ , поддерживайте граф $G,$ для которого $L = L (G)$ ; если алгоритму когда-либо не удается найти подходящий граф $G$ , то входные данные не являются линейным графом, и алгоритм завершается.
При добавлении вершины $v$ к графу $L (G),$ для которого $G$ имеет четыре или меньше вершин, может случиться так, что представление линейного графа не будет уникальным. Но в этом случае дополненный граф достаточно мал, чтобы его представление в виде линейного графа можно было найти методом грубой силы за постоянное время.
При добавлении вершины $v$ к большему графу $L$ , который равен линейному графу другого графа $G$ , пусть $S$ будет подграфом $G,$ образованным ребрами, которые соответствуют соседям $v$ в $L.$ Проверьте, что $S$ имеет вершинное покрытие, состоящее из одной вершины или двух несмежных вершин. Если в покрытии две вершины, дополните $G$ , добавив ребро (соответствующее $v$ ), которое соединяет эти две вершины. Если в покрытии только одна вершина, то добавьте новую вершину в $G$ , смежную с этой вершиной.

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

Итерация оператора линейного графика

ван Рой и Уилф (1965) рассматривают последовательность графов

G,L(G),L(L(G)),L(L(L(G))),\dots .\

Они показывают, что когда $G$ — конечный связный граф , для этой последовательности возможны только четыре поведения:

Если $G$ — циклический граф, то $L (G)$ и каждый последующий граф в этой последовательности изоморфны самому G. $Это$ единственные связные графы, для которых $L (G)$ изоморфен $G$ . ^[26]
Если $G$ — клешня $K 1,3$ , то $L (G)$ и все последующие графы в последовательности являются треугольниками.
Если $G$ — граф путей , то каждый последующий граф в последовательности представляет собой более короткий путь, пока в конечном итоге последовательность не завершится пустым графом .
Во всех остальных случаях размеры графиков в этой последовательности со временем неограниченно увеличиваются.

Если $G$ не связан, эта классификация применяется отдельно к каждому компоненту $G.$

Для связных графов, которые не являются путями, все достаточно большие числа итераций операции линейного графа создают графы, которые являются гамильтоновыми. ^[27]

Обобщения

Медиальные графы и выпуклые многогранники

Когда планарный граф $G$ имеет максимальную степень вершины три, его линейный граф является планарным, и каждое планарное вложение $G$ может быть расширено до вложения $L (G)$ . Однако существуют планарные графы с более высокой степенью, линейные графы которых непланарны. К ним относятся, например, 5-звездный граф $K 1,5$ , граф драгоценных камней, образованный добавлением двух непересекающихся диагоналей внутри правильного пятиугольника, и все выпуклые многогранники с вершиной степени четыре или более. ^[28]

Альтернативная конструкция, медиальный граф , совпадает с линейным графом для планарных графов с максимальной степенью три, но всегда является планарным. Он имеет те же вершины, что и линейный граф, но потенциально меньше ребер: две вершины медиального графа смежны тогда и только тогда, когда соответствующие два ребра являются последовательными на некоторой грани планарного вложения. Медиальный граф двойственного графа плоского графа совпадает с медиальным графом исходного плоского графа. ^[29]

Для правильных многогранников или простых многогранников операция медиального графа может быть представлена геометрически как операция отсечения каждой вершины многогранника плоскостью, проходящей через середины всех его инцидентных ребер. ^[30] Эта операция известна по-разному: второе усечение, ^[31] вырожденное усечение, ^[32] или выпрямление . ^[33]

Всего графиков

Общий граф $T (G)$ графа $G$ имеет в качестве вершин элементы (вершины или ребра) $G$ , и имеет ребро между двумя элементами, когда они либо инцидентны, либо смежны. Общий граф также может быть получен путем подразделения каждого ребра $G$ и затем взятия квадрата подразделенного графа. ^[34]

Мультиграфы

Понятие линейного графа графа $G$ может быть естественным образом расширено на случай, когда $G$ является мультиграфом. В этом случае характеристики этих графов могут быть упрощены: характеристика в терминах разбиений на клики больше не должна препятствовать принадлежности двух вершин к одной и той же клике, а характеристика с помощью запрещенных графов имеет семь запрещенных графов вместо девяти. ^[35]

Однако для мультиграфов существует большее число пар неизоморфных графов, которые имеют одинаковые линейные графы. Например, полный двудольный граф $K 1, n$ имеет тот же линейный граф, что и дипольный граф и мультиграф Шеннона с тем же числом ребер. Тем не менее, аналоги теоремы Уитни об изоморфизме все еще могут быть получены в этом случае. ^[12]

Линейные орграфы

Построение графов де Брейна как итерированных линейных орграфов

Также возможно обобщить линейные графы до направленных графов. ^[36] Если $G$ — направленный граф, его направленный линейный граф или линейный орграф имеет одну вершину для каждого ребра $G.$ Две вершины, представляющие направленные ребра от $u$ до $v$ и от $w$ до $x$ в $G,$ соединены ребром от $uv$ до $wx$ в линейном орграфе, когда $v = w$ . То есть каждое ребро в линейчатом орграфе $G$ представляет собой направленный путь длины два в $G.$ Графы де Брейна могут быть сформированы путем повторения этого процесса формирования направленных линейных графов, начиная с полного направленного графа . ^[37]

Взвешенные линейные графики

В линейном графе $L (G)$ каждая вершина степени $k$ в исходном графе $G$ создает $k (k - 1)/2$ ребер в линейном графе. Для многих типов анализа это означает, что узлы высокой степени в $G$ перепредставлены в линейном графе $L (G)$ . Например, рассмотрим случайное блуждание по вершинам исходного графа $G$ . Оно будет проходить по некоторому ребру $e$ с некоторой частотой $f$ . С другой стороны, это ребро $e$ отображается в уникальную вершину, скажем, $v$ , в линейном графе $L (G)$ . Если теперь мы выполним тот же тип случайного блуждания по вершинам линейного графа, частота, с которой посещается $v , может полностью отличаться от$ f . Если наше ребро $e$ в $G$ было соединено с узлами степени $O (k)$ , оно будет проходить $O (k 2)$ чаще в линейном графе $L (G)$ . Другими словами, теорема Уитни об изоморфизме графов гарантирует, что линейный граф почти всегда точно кодирует топологию исходного графа $G,$ но она не гарантирует, что динамика этих двух графов имеет простую связь. Одним из решений является построение взвешенного линейного графа, то есть линейного графа с взвешенными ребрами . Существует несколько естественных способов сделать это. ^[38] Например, если ребра $d$ и $e$ в графе $G$ инцидентны вершине $v$ со степенью $k$ , то в линейном графе $L (G)$ ребру, соединяющему две вершины $d$ и $e,$ можно присвоить вес $1/(k - 1)$ . Таким образом, каждое ребро в $G$ (при условии, что ни один из концов не соединен с вершиной степени 1) будет иметь силу 2 в линейном графе $L (G),$ соответствующую двум концам, которые ребро имеет в $G$ . Это определение взвешенного линейного графа легко расширить на случаи, когда исходный граф $G$ был направленным или даже взвешенным. ^[39] Принцип во всех случаях заключается в том, чтобы линейный график $L (G)$ отражал динамику, а также топологию исходного графа $G.$

Линейные графики гиперграфов

Ребра гиперграфа могут образовывать произвольное семейство множеств , поэтому линейный граф гиперграфа совпадает с графом пересечений множеств из семейства.

Граф непересекаемости

Граф дизъюнктности графа G $,$ обозначаемый $D (G)$ , строится следующим образом: для каждого ребра в $G$ создаем вершину в $D (G)$ ; для каждых двух ребер в $G$ , не имеющих общей вершины, создаем ребро между их соответствующими вершинами в $D (G)$ . ^[40] Другими словами, $D (G)$ является дополнительным графом графа L $(G) .$ Клика в D $(G) соответствует$ независимому множеству в $L (G)$ , и наоборот.

Примечания

^ ab Хеммингер и Бейнеке (1978), стр. 273.
^ abc Harary (1972), стр. 71.
^ ab Whitney (1932); Krausz (1943); Harary (1972), теорема 8.3, стр. 72. Harary приводит упрощенное доказательство этой теоремы, предложенное Jung (1966).
^ ab Paschos, Vangelis Th. (2010), Комбинаторная оптимизация и теоретическая информатика: интерфейсы и перспективы, John Wiley & Sons, стр. 394, ISBN 9780470393673Очевидно , что между паросочетаниями графа и независимыми множествами его линейного графа существует взаимно-однозначное соответствие.
^ Необходимость рассмотрения изолированных вершин при рассмотрении связности линейных графов отмечена Цветковичем, Роулинсоном и Симичем (2004), стр. 32.
^ Харари (1972), Теорема 8.1, с. 72.
^ Дистель, Рейнхард (2006), Теория графов, Graduate Texts in Mathematics, т. 173, Springer, стр. 112, ISBN 9783540261834. Также в бесплатном онлайн-издании, Глава 5 («Раскрашивание»), стр. 118.
^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы по автоморфизмам графов и реконструкции, Лондонское математическое общество, студенческие тексты, т. 54, Кембридж: Cambridge University Press, стр. 44, ISBN 0-521-82151-7, г-н 1971819. Лаури и Скапеллато приписывают этот результат Марку Уоткинсу.
^ Харари (1972), Теорема 8.8, с. 80.
^ Рамезанпур, Каримипур и Машаги (2003).
^ Юнг (1966); Дегиорджи и Саймон (1995).
^ ab Зверович (1997)
^ Ван Дам, Эдвин Р.; Хемерс, Виллем Х. (2003), «Какие графы определяются своим спектром?», Линейная алгебра и ее приложения , 373 : 241–272, doi : 10.1016/S0024-3795(03)00483-X , MR 2022290, S2CID 32070167. См. в частности Предложение 8, стр. 262.
^ Харари (1972), Теорема 8.6, стр. 79. Харари приписывает этот результат независимым работам Л. Ч. Чанга (1959) и А. Дж. Хоффмана (1960).
^ Чудновски, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, S2CID 119151552. См. также Руссель, Ф.; Русу, И.; Тюилье, Х. (2009), «Сильная гипотеза о совершенном графе: 40 лет попыток и ее разрешение», Дискретная математика , 309 (20): 6092–6113, doi : 10.1016/j.disc.2009.05.024 , MR 2552645, S2CID 16049392.
^ Harary (1972), Теорема 8.7, стр. 79. Harary приписывает эту характеристику линейных графов полных двудольных графов Муну и Хоффману. Случай равного числа вершин с обеих сторон ранее был доказан Шрикханде.
^ Троттер (1977); де Верра (1978).
^ Маффрей (1992).
^ Троттер (1977).
^ ab Harary (1972), теорема 8.4, стр. 74, дает три эквивалентные характеристики линейных графов: разбиение ребер на клики, свойство быть свободным от клешней и нечетных ромбов и девять запрещенных графов Бейнеке.
^ Самнер, Дэвид П. (1974), «Графы с 1-факторами», Труды Американского математического общества , 42 (1), Американское математическое общество: 8–12, doi :10.2307/2039666, JSTOR 2039666, MR 0323648. Лас Верньяс, М. (1975), «Заметки о сопоставлениях в графах», Cahiers du Center d'Etudes de Recherche Opérationnelle , 17 (2–3–4): 257–260, MR 0412042.
↑ Харари (1972), Теорема 8.5, стр. 78. Харари приписывает этот результат Гэри Чартранду .
^ Эрдёш, Пол ; Сакс, Майкл ; Шош, Вера Т. (1986), «Максимальные индуцированные деревья в графах», Журнал комбинаторной теории, Серия B , 41 (1): 61–79, doi : 10.1016/0095-8956(86)90028-6.
^ Цветкович, Роулинсон и Симич (2004).
^ Метельский и Тышкевич (1997)
^ Этот результат также является теоремой 8.2 Харари (1972).
↑ Харари (1972), Теорема 8.11, стр. 81. Харари приписывает этот результат Гэри Чартранду .
^ Седлачек (1964); Гринвелл и Хеммингер (1972).
^ Архидьякон, Дэн (1992), «Медиальный граф и дуальность напряжение-ток», Дискретная математика , 104 (2): 111–141, doi : 10.1016/0012-365X(92)90328-D , MR 1172842.
^ Макки, TA (1989), "Графовая теоретико-модель географической дуальности", Комбинаторная математика: Труды Третьей международной конференции (Нью-Йорк, 1985) , Ann. New York Acad. Sci., т. 555, Нью-Йорк: New York Acad. Sci., стр. 310–315, Bibcode : 1989NYASA.555..310M, doi : 10.1111/j.1749-6632.1989.tb22465.x, MR 1018637, S2CID 86300941.
^ Пью, Энтони (1976), Многогранники: визуальный подход , Издательство Калифорнийского университета, ISBN 9780520030565.
^ Лёб, Артур Ли (1991), Космические структуры — их гармония и контрапункт (5-е изд.), Birkhäuser, ISBN 9783764335885.
^ Вайсштейн, Эрик В. «Ректификация». MathWorld .
↑ Харари (1972), стр. 82.
^ Рыячек и Врана (2011).
^ Харари и Норман (1960).
^ Чжан и Линь (1987).
^ Эванс и Ламбиотт (2009).
^ Эванс и Ламбиотт (2010).
^ Мешулам, Рой (01.01.2001). «Комплекс клик и соответствие гиперграфов». Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

Ссылки

Бейнеке, Л.В. (1968), «Производные графы орграфов», Сакс, Х.; Восс, Х.-Дж.; Вальтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie , Лейпциг: Тойбнер, стр. 17–33..
Бейнеке, Л. В. (1970), «Характеристики производных графов», Журнал комбинаторной теории , 9 (2): 129–135, doi : 10.1016/S0021-9800(70)80019-9 , MR 0262097.
Цветкович, Драгош; Роулинсон, Питер; Симич, Слободан (2004), Спектральные обобщения линейных графов , Серия лекций Лондонского математического общества, т. 314, Кембридж: Cambridge University Press, doi : 10.1017/CBO9780511751752, ISBN 0-521-83663-8, МР 2120511.
Degiorgi, Daniele Giorgio; Simon, Klaus (1995), "Динамический алгоритм распознавания линейных графов", Графовые концепции в информатике (Аахен, 1995) , Lecture Notes in Computer Science, т. 1017, Berlin: Springer, стр. 37–48, doi :10.1007/3-540-60618-1_64, MR 1400011.
Эванс, ТС; Ламбиотт, Р. (2009), «Линейные графики, разделы связей и перекрывающиеся сообщества», Physical Review E , 80 (1): 016105, arXiv : 0903.2181 , Bibcode : 2009PhRvE..80a6105E, doi : 10.1103/PhysRevE.80.016105, PMID 19658772.
Эванс, ТС; Ламбиотт, Р. (2010), «Линейные графики взвешенных сетей для перекрывающихся сообществ», European Physical Journal B , 77 (2): 265–272, arXiv : 0912.4389 , Bibcode : 2010EPJB...77..265E, doi : 10.1140/epjb/e2010-00261-8, S2CID 119504507.
Гринвелл, Д. Л.; Хеммингер, Роберт Л. (1972), «Запрещенные подграфы для графов с планарными линейными графами», Дискретная математика , 2 : 31–34, doi : 10.1016/0012-365X(72)90058-1 , MR 0297604.
Харари, Ф .; Норман, Р.З. (1960), «Некоторые свойства линейных орграфов», Rendiconti del Circolo Matematico di Palermo , 9 (2): 161–169, doi : 10.1007/BF02854581, hdl : 10338.dmlcz/128114 , S2CID 122473974.
Harary, F. (1972), "8. Линейные графики", Теория графов (PDF) , Массачусетс: Addison-Wesley, стр. 71–83, заархивировано из оригинала (PDF) 2017-02-07 , извлечено 2013-11-08.
Хеммингер, Р. Л.; Бейнеке, Л. В. (1978), «Линейные графы и линейные орграфы», в Бейнеке, Л. В.; Уилсон, Р. Дж. (ред.), Избранные темы теории графов , Academic Press Inc., стр. 271–305.
Юнг, Х.А. (1966), «Zu einem Isomorphiesatz von H. Whitney für Graphen», Mathematische Annalen (на немецком языке), 164 (3): 270–271, doi : 10.1007/BF01360250, MR 0197353, S2CID 119898359.
Краус, Дж. (1943), "Новая демонстрация теории Уитни в сюр-ле-резо", Мат. Физ. Лапок , 50 : 75–85, МР 0018403.
Lehot, Philippe GH (1974), «Оптимальный алгоритм для обнаружения линейного графа и вывода его корневого графа», Journal of the ACM , 21 (4): 569–575, doi : 10.1145/321850.321853 , MR 0347690, S2CID 15036484.
Маффрей, Фредерик (1992), «Ядра в совершенных линейных графах», Журнал комбинаторной теории , Серия B, 55 (1): 1–8, doi : 10.1016/0095-8956(92)90028-V , MR 1159851.
Метельский, Юрий; Тышкевич, Регина (1997), "О линейных графах линейных 3-однородных гиперграфов", Журнал теории графов , 25 (4): 243–251, doi :10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
Рамезанпур, А.; Каримипур, В.; Машаги, А. (2003), "Создание коррелированных сетей из некоррелированных", Phys. Rev. E , 67 (4): 046107, arXiv : cond-mat/0212469 , Bibcode : 2003PhRvE..67d6107R, doi : 10.1103/physreve.67.046107, PMID 12786436, S2CID 33054818.
ван Рой, ACM; Уилф, HS (1965), «Граф обмена конечного графа», Acta Mathematica Hungarica , 16 (3–4): 263–269, doi : 10.1007/BF01904834 , hdl : 10338.dmlcz/140421 , S2CID 122866512.
Руссопулос, НД (1973), "Алгоритм max { m , n } для определения графа H по его линейному графу G ", Information Processing Letters , 2 (4): 108–112, doi :10.1016/0020-0190(73)90029-X, MR 0424435.
Рыячек, Зденек; Врана, Петр (2011), «Линейные графы мультиграфов и гамильтоновая связность графов без клешней», Journal of Graph Theory , 66 (2): 152–173, doi : 10.1002/jgt.20498, MR 2778727, S2CID 8880045.
Седлачек, Й. (1964), «Некоторые свойства графов обмена», Теория графов и ее приложения (Труды симпозиума в Смоленице, 1963) , Изд-во Чехословацкой академии наук, Прага, стр. 145–150, MR 0173255.
Sysło, Maciej M. (1982), «Алгоритм маркировки для распознавания линейного орграфа и вывода его корневого графа», Information Processing Letters , 15 (1): 28–30, doi :10.1016/0020-0190(82)90080-1, MR 0678028.
Троттер, Л. Э. младший (1977), «Линейно-совершенные графы», Математическое программирование , 12 (2): 255–259, doi :10.1007/BF01593791, MR 0457293, S2CID 38906333.
де Верра, Д. (1978), «Онлайновые совершенные графы», Математическое программирование , 15 (2): 236–238, doi :10.1007/BF01609025, MR 0509968, S2CID 37062237.
Уитни, Х. (1932), «Конгруэнтные графы и связность графов», American Journal of Mathematics , 54 (1): 150–168, doi : 10.2307/2371086, hdl : 10338.dmlcz/101067 , JSTOR 2371086.
Чжан, Фу Цзи; Линь, Го Нин (1987), «О графах де Брёйна – Гуда», Acta Math. Синица , 30 (2): 195–205, МР 0891925.
Зверович, И. Э. (1997), Аналоговые выводы Уитни для реберных графов мультиграфов и реберных мультиграфов, Дискретная математика , 9 (2): 98–105, doi : 10.4213/dm478 , MR 1468075. Переведено на английский язык как Зверович, И. Э. (1997), "Аналог теоремы Уитни для реберных графов мультиграфов и реберных мультиграфов", Дискретная математика и приложения , 7 (3): 287–294, doi :10.1515/dma.1997.7.3.287, S2CID 120525090.

Внешние ссылки

Линейные графики, Информационная система по включению классов графов
Вайсштейн, Эрик В. «Линейный график». MathWorld .