Подграф Сакса - Sachs subgraph

В теория графов, а Подграф Сакса данного графа является подграф в котором все связанные компоненты либо одинарные, либо циклы. Эти подграфы названы в честь Хорст Сакс, который использовал их в расширении характеристический многочлен из матрица смежности графиков.[1] Подобное расширение с использованием подграфов Сакса также возможно для постоянные многочлены графиков.[2] Подграфы Сакса и вычисленные с их помощью многочлены применялись в химическая теория графов,[3] например, как часть теста на наличие несвязывающие орбитали в углеводород конструкции.[4]

А охватывающий подграф Сакса, также называемый {1,2} -фактором, является подграфом Сакса, в котором каждая вершина данного графа инцидентна ребру подграфа.[5] Союз двух идеальное соответствие всегда является двудольным остовным подграфом Сакса, но в целом подграфы Сакса не ограничиваются тем, что они являются двудольными. Некоторые авторы используют термин «подграф Сакса» для обозначения только охватывающих подграфов Сакса.[6]

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

  1. ^ Сакс, Хорст (1964), "Beziehungen zwischen den in einem Graphen enthaltenen Kreisen und seinem charakteristischen Polynom", Publicationes Mathematicae Debrecen (на немецком), 11: 119–134, МИСТЕР  0172271
  2. ^ Ли, Вэй; Лю, Шуньи; Ву, Тингзэн; Чжан, Хэпин (2017), "О постоянных многочленах графов", Полиномы графа, Дискретная математика и ее приложения, Бока-Ратон, Флорида: CRC Press, стр. 101–121, МИСТЕР  3790914
  3. ^ Вагнер, Стефан; Ван, Хуа (2019), Введение в теорию химических графов, Дискретная математика и ее приложения, Бока-Ратон, Флорида: CRC Press, стр. 215, ISBN  978-1-138-32508-1, МИСТЕР  3837106
  4. ^ Тютюльков, Н .; Dietz, F .; Müllen, K .; Baumgarten, M .; Карабунарлиев, С. (сентябрь 1993 г.), "Структура и свойства неклассических полимеров", Теоретика Chimica Acta, 86 (4): 353–367, Дои:10.1007 / bf01128522
  5. ^ Aaghabali, M .; Акбари, С .; Тайфируз, З. (2017), «Порядок наибольших подграфов Сакса в графах», Линейная и полилинейная алгебра, 65 (1): 204–209, Дои:10.1080/03081087.2016.1179710, МИСТЕР  3575888, S2CID  124186154
  6. ^ Ян, Юйцзюнь; Йе, Донг (2018), «Обратные двудольные графы», Комбинаторика, 38 (5): 1251–1263, arXiv:1611.06535, Дои:10.1007 / s00493-016-3502-y, МИСТЕР  3884787, S2CID  54465291