Однородный граф - Homogeneous graph

В математика, а k-сверходнородный граф это график в котором каждый изоморфизм между двумя своими индуцированные подграфы не более k вершины могут быть расширены до автоморфизм всего графа. А k-однородный граф подчиняется ослабленной версии того же свойства, в которой каждый изоморфизм между двумя индуцированными подграфами влечет существование автоморфизма всего графа, который отображает один подграф в другой (но не обязательно расширяет данный изоморфизм).[1]

А однородный граф это граф, который k-однородный для всех k, или эквивалентно k-ультраоднородный для всех k.[1]

Классификация

Единственными конечными однородными графами являются кластерные графы мКп сформированный из непересекающиеся союзы изоморфных полные графики, то Графики Турана сформированный как дополнить графы из мКп, 3 × 3 график ладьи, а 5-цикл.[2]

Единственный счетно бесконечный однородные графы - это непересекающиеся объединения изоморфных полных графов (с размером каждого полного графа, количеством полных графов или обоими счетно бесконечными числами), их дополнительных графов, Графики Хенсона вместе с их дополнительными графами, а График Rado.[3]

Если граф 5-ультраоднородный, то он ультраоднороден для любого k.Есть всего два связаны графы, которые являются 4-ультраоднородными, но не 5-ультраоднородными: Граф Шлефли и его дополнение. Доказательство опирается на классификация конечных простых групп.[4]

Вариации

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

Примечания

  1. ^ а б Ронс (1978).
  2. ^ Гардинер (1976).
  3. ^ Лахлан и Вудро (1980).
  4. ^ Бучак (1980); Кэмерон (1980); Девильеры (2002).
  5. ^ Гардинер (1978); Грей и Макферсон (2010)

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

  • Бучак, Дж. М. Дж. (1980), Теория конечных групп, Кандидат наук. диссертация, Оксфордский университет. Как цитирует Девильеры (2002).
  • Кэмерон, Питер Джефсон (1980), «6-транзитивные графы», Журнал комбинаторной теории, Серия B, 28: 168–179, Дои:10.1016/0095-8956(80)90063-5. Как цитирует Девильеры (2002).
  • Девиллерс, Алиса (2002), Классификация некоторых однородных и сверходнородных структур., Кандидат наук. диссертация, Université Libre de Bruxelles.
  • Гардинер, А. (1976), "Однородные графы", Журнал комбинаторной теории, Серия B, 20 (1): 94–102, Дои:10.1016/0095-8956(76)90072-1, МИСТЕР  0419293.
  • Гардинер А. (1978), "Условия однородности в графах", Журнал комбинаторной теории, Серия B, 24 (3): 301–310, Дои:10.1016/0095-8956(78)90048-5, МИСТЕР  0496449.
  • Gray, R .; Макферсон, Д. (2010), "Счетные связно-однородные графы", Журнал комбинаторной теории, Серия B, 100 (2): 97–118, Дои:10.1016 / j.jctb.2009.04.002, МИСТЕР  2595694.
  • Lachlan, A.H .; Вудро, Роберт Э. (1980), "Счетные сверходнородные неориентированные графы", Труды Американского математического общества, 262 (1): 51–94, Дои:10.2307/1999974, МИСТЕР  0583847.
  • Ронсе, Кристиан (1978), "Об однородных графах", Журнал Лондонского математического общества, Вторая серия, 17 (3): 375–379, Дои:10.1112 / jlms / s2-17.3.375, МИСТЕР  0500619.