Однородный граф
В математике k - ультраоднородный граф - это граф , в котором каждый изоморфизм между двумя его индуцированными подграфами с не более чем k вершинами может быть расширен до автоморфизма всего графа. K - однородный граф подчиняется ослабленной версии того же свойства, в котором каждый изоморфизм между двумя индуцированными подграфами подразумевает существование автоморфизма всего графа, который отображает один подграф на другой (но не обязательно расширяет заданный изоморфизм). [1]
Однородный граф — это граф, который является k -однородным для каждого k или, что эквивалентно, k -ультраоднородным для каждого k . [1] Это частный случай однородной модели .
Классификация
Единственными конечными однородными графами являются кластерные графы mK n , образованные из несвязных объединений изоморфных полных графов , графы Турана, образованные как дополнительные графы mK n , граф ладьи 3 × 3 и 5- цикл . [2]
Единственными счетно бесконечными однородными графами являются несвязные объединения изоморфных полных графов (с размером каждого полного графа, числом полных графов или обоими числами счетно бесконечными), их дополнительные графы, графы Хенсона вместе со своими дополнительными графами и граф Радо . [3]
Если граф 5-ультраоднороден, то он ультраоднороден для любого k . Существует только два связных графа, которые являются 4-ультраоднородными, но не 5-ультраоднородными: граф Шлефли и его дополнение. Доказательство основано на классификации конечных простых групп . [4]
Вариации
Граф является связно-однородным, если любой изоморфизм между двумя связными индуцированными подграфами может быть расширен до автоморфизма всего графа. В дополнение к однородным графам, конечные связные связно-однородные графы включают все графы циклов , все графы квадратных ладей , граф Петерсена и 5-регулярный граф Клебша . [5]
Примечания
- ^ ab Ronse (1978).
- ^ Гардинер (1976).
- ^ Лаклан и Вудро (1980).
- ^ Бузак (1980); Кэмерон (1980); Девиллер (2002).
- ^ Гардинер (1978); Грей и Макферсон (2010)
Ссылки
- Бузак, Дж. М. Дж. (1980), Теория конечных групп , докторская диссертация, Оксфордский университет. Как цитирует Девиллер (2002).
- Кэмерон, Питер Джефсон (1980), «6-транзитивные графы», Журнал комбинаторной теории , Серия B, 28 : 168–179 , doi : 10.1016/0095-8956(80)90063-5. Как цитирует Девиллер (2002).
- Девиллер, Элис (2002), Классификация некоторых однородных и ультраоднородных структур , докторская диссертация, Свободный университет Брюсселя.
- Гардинер, А. (1976), «Однородные графы», Журнал комбинаторной теории , Серия B, 20 (1): 94–102 , doi :10.1016/0095-8956(76)90072-1, MR 0419293.
- Гардинер, А. (1978), «Условия однородности в графах», Журнал комбинаторной теории , Серия B, 24 (3): 301– 310, doi : 10.1016/0095-8956(78)90048-5 , MR 0496449.
- Грей, Р.; Макферсон, Д. (2010), «Счетные связно-однородные графы», Журнал комбинаторной теории , Серия B, 100 (2): 97–118 , doi : 10.1016/j.jctb.2009.04.002 , MR 2595694.
- Лаклан, AH; Вудро, Роберт Э. (1980), «Счетные ультраоднородные неориентированные графы», Труды Американского математического общества , 262 (1): 51– 94, doi : 10.2307/1999974 , MR 0583847.
- Ронсе, Кристиан (1978), «Об однородных графах», Журнал Лондонского математического общества , Вторая серия, 17 (3): 375–379 , doi :10.1112/jlms/s2-17.3.375, MR 0500619.
