Однородный граф
В математике 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]
Примечания
[ редактировать ]Ссылки
[ редактировать ]- Бучак, JMJ (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 .
- Лахлан, АХ; Вудро, Роберт Э. (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 .