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

Эта статья о математической концепции. О методе статистического представления см. линейную диаграмму .

Не путать с графом путей .

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

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

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

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

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

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

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

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

Пример

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

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

Свойства

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

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

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

• Линейный график связного графа связен. Если G связен, он содержит путь, соединяющий любые два его ребра, что преобразуется в путь в L ( G ), содержащий любые две вершины L ( G ) . Однако граф G , имеющий несколько изолированных вершин и, следовательно, несвязный, тем не менее может иметь связный линейный граф.
• Линейный граф имеет точку сочленения тогда и только тогда, когда базовый граф имеет мост , ни одна конечная точка которого не имеет степени один.
• Для графа G с n вершинами и m ребрами количество вершин линейного графа L ( G ) равно m , а количество ребер L ( G ) равно половине суммы квадратов степеней вершин в Г , минус м .
• Независимый набор в L ( G ) соответствует паросочетанию в G. ​В частности, максимальное независимое множество в L ( G ) соответствует паросочетанию в G. максимальному Поскольку максимальные паросочетания могут быть найдены за полиномиальное время, то же самое можно сделать и с максимальными независимыми наборами линейных графов, несмотря на сложность проблемы максимального независимого множества для более общих семейств графов. Аналогично, радуги набор в L ( G ) соответствует радужному паросочетанию в G. независимый от
• Реберное хроматическое число графа G равно вершинному хроматическому числу его линейного графа L ( G ) .
• Линейный граф реберно-транзитивного графа является вершинно-транзитивным . Это свойство можно использовать для создания семейств графов, которые (например, граф Петерсена ) являются вершинно-транзитивными, но не являются графами Кэли : если G — реберно-транзитивный граф, который имеет не менее пяти вершин, не является двудольным и имеет нечетные вершины градусов, то L ( G ) является вершинно-транзитивным не-графом Кэли.
• Если граф G имеет эйлеров цикл , то есть если G связен и имеет четное число ребер в каждой вершине, то линейный граф G является гамильтоновым . Однако не все гамильтоновы циклы в линейных графах таким образом происходят от циклов Эйлера; например, линейный график гамильтонова графа G сам по себе является гамильтоновым, независимо от того, является ли G также эйлеровым.
• Если два простых графа изоморфны , то их линейные графы также изоморфны. Теорема об изоморфизме графов Уитни обеспечивает обратное утверждение для всех пар связных графов, кроме одной.
• В контексте теории сложных сетей линейный граф случайной сети сохраняет многие свойства сети, такие как свойство маленького мира (существование коротких путей между всеми парами вершин) и форму распределения ее степеней . Эванс и Ламбиотт (2009) отмечают, что любой метод поиска кластеров вершин в сложной сети можно применить к линейному графу и вместо этого использовать для кластеризации его ребер.

Уитни

Ромбовидный график (слева) и его более симметричный линейный график (справа), исключение из сильной теоремы Уитни.

Если линейные графы двух связных графов изоморфны, то лежащие в их основе графы изоморфны, за исключением случая треугольного графа K ₃ и клешни K _1,3 , которые имеют изоморфные линейные графы, но сами не изоморфны.

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

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

Строго регулярные и идеальные линейные графики

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

Линейный граф полного графа Kn _J также известен как треугольный граф , граф Джонсона ( n , 2) или дополнение к графу Кнезера KGn _{, 2} . Треугольные графы характеризуются своими спектрами , за исключением n = 8 . Их также можно охарактеризовать (опять же за исключением K ₈ ) как сильно регулярные графы с параметрами srg( n ( n – 1)/2, 2( n – 2), n – 2, 4) . Три сильно регулярных графа с теми же параметрами и спектром, что и ( K8 ) _L , являются Чанга , которые можно получить переключением графа с L ( K8 _{графами} ) .

Линейный график двудольного графа идеален ), но не обязательно должен быть двудольным , (см. теорему Кенига как показывает пример когтевого графа. Линейные графы двудольных графов образуют один из ключевых строительных блоков совершенных графов, используемых в доказательстве сильной теоремы о совершенном графе . Частным случаем этих графов являются ладейные графы , линейные графы полных двудольных графов . Как и линейные графы полных графов, они, за одним исключением, могут быть охарактеризованы количеством вершин, количеством ребер и количеством общих соседей для смежных и несмежных точек. Единственным исключительным случаем является L ( K _4,4 ) , параметры которого совпадают с графом Шрикханде . Когда обе стороны биразделения имеют одинаковое количество вершин, эти графы снова становятся строго регулярными.

В более общем смысле, граф G называется линейным совершенным графом, если L ( G ) — совершенный граф . Линейно-совершенные графы — это именно те графы, которые не содержат простых циклов нечетной длины, большей трех. Эквивалентно, граф является линейно совершенным тогда и только тогда, когда каждый из его двусвязных компонентов либо двудольный, либо имеет форму K ₄ (тетраэдр) или K _{1,1, n} (книга из одного или нескольких треугольников, имеющих общее ребро). . Каждый линейный идеальный график сам по себе совершенен.

графов

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

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

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

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

Раздел клики

Разбиение линейного графа на клики

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

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

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

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

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

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

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

Алгоритмы

Руссопулос (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. которых
• Если G — коготь K1,3 _L , то и все последующие графы в ( G ) последовательности — треугольники.
• Если G — граф путей , то каждый последующий граф в последовательности является более коротким путем, пока в конечном итоге последовательность не завершится пустым графом .
• Во всех остальных случаях размеры графов этой последовательности со временем неограниченно увеличиваются.

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

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

Обобщения

Медиальные графы

Основная статья: Медиальный график

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

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

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

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

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

Мультиграфы

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

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

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

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

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

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

В линейном графе 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 ² ) чаще в линейном графике L ( G ) . Другими словами, теорема об изоморфизме графа Уитни гарантирует, что линейный граф почти всегда точно кодирует топологию исходного графа G , но не гарантирует, что динамика на этих двух графах имеет простую связь. Одним из решений является построение взвешенного линейного графа, то есть линейного графа с взвешенными ребрами . Есть несколько естественных способов сделать это. Например, если ребра d и e в графе G инцидентны вершине v степени k , то в линейном графе L ( G ) ребру, соединяющему две вершины d и e, можно присвоить вес 1/( k − 1). . Таким образом, каждое ребро в G что ни один конец не соединен с вершиной степени 1) будет иметь силу 2 в линейном графе L ( G ), что соответствует двум концам, которые ребро имеет в G. (при условии , Это определение взвешенного линейного графа несложно распространить на случаи, когда исходный граф G был направленным или даже взвешенным. Принцип во всех случаях заключается в том, чтобы линейный граф L ( G ) отражал динамику, а также топологию исходного G. графа

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

Основная статья: Линейный график гиперграфа

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

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

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

Ссылки

• Бейнеке, Л.В. (1968), «Производные графы орграфов», в Саксе, Х.; Восс, Х.-Дж.; Вальтер, Х.-Дж. (ред.), Вклад в теорию графов , Лейпциг: Тойбнер, стр. 17–33 .
• Бейнеке, Л.В. (1970), «Характеристики производных графов», Журнал комбинаторной теории , 9 (2): 129–135, doi : 10.1016/S0021-9800(70)80019-9 , MR   0262097 .
• Цветкович, Драгош; Роулинсон, Питер; Симич, Слободан (2004), Спектральные обобщения линейных графов , Серия лекций Лондонского математического общества, том. 314, Кембридж: Издательство Кембриджского университета, номер номера : 10.1017/CBO9780511751752 , ISBN.  0-521-83663-8 , МР   2120511 .
• Деджорджи, Даниэле Джорджио; Саймон, Клаус (1995), «Динамический алгоритм распознавания линейных графов», Теоретико-графовые концепции в информатике (Аахен, 1995) , Конспекты лекций по информатике, том. 1017, Берлин: Springer, стр. 37–48, номер документа : 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 , идентификатор   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), «Запрещенные подграфы для графов с плоскими линейными графиками», Discrete Mathematics , 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 .
• Харари, Ф. (1972), «8. Линейные графики», Теория графов (PDF) , Массачусетс: Аддисон-Уэсли, стр. 71–83, заархивировано из оригинала (PDF) 07 февраля 2017 г. , получено в 2013 г. 11-08 .
• Хеммингер, РЛ; Бейнеке, Л.В. (1978), «Линейные графики и линейные орграфы», в Бейнеке, Л.В.; Уилсон, Р.Дж. (ред.), «Избранные темы теории графов» , Academic Press Inc., стр. 271–305 .
• Юнг, Х.А. (1966), «О теореме Х. Уитни об изоморфизме для графов», Mathematical Annals (на немецком языке), 164 (3): 270–271, doi : 10.1007/BF01360250 , MR   0197353 , S2CID   119898359 .
• Краус Дж. (1943), “Новое доказательство теоремы Уитни о сетях”, Матем. Физ. Лапок , 50 : 75–85, МР   0018403 .
• Лео, Филипп Г.Х. (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. Ред. 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 , МР   0424435 .
• Рыячек, Зденек; Врана, Петр (2011), «Линейные графы мультиграфов и гамильтоновая связность графов без клешней», Journal of Graph Theory , 66 (2): 152–173, doi : 10.1002/jgt.20498 , MR   2778727 , S2CID   8880045 .
• Седлачек, Дж. (1964), «Некоторые свойства графов обмена», Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Publ. Дом Чехословацкой академии. Sci., Прага, стр. 145–150, MR   0173255 .
• Сысло, Мацей М. (1982), «Алгоритм разметки для распознавания линейного орграфа и вывода его корневого графа», Information Processing Letters , 15 (1): 28–30, doi : 10.1016/0020-0190(82)90080- 1 , МР   0678028 .
• Троттер, Л.Е. младший (1977), «Линейные совершенные графики», Mathematical Programming , 12 (2): 255–259, doi : 10.1007/BF01593791 , MR   0457293 , S2CID   38906333 .
• де Верра, Д. (1978), «Онлайн-идеальные графы», Mathematical Programming , 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), «Аналог теоремы Уитни для реберных графов мультиграфов и реберных мультиграфов», Discrete Mathematics and Applications , 7 (3): 287–294, doi : 10.1515/dma.1997.7.3.287 , S2CID   120525090 .

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

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