Двухуровневый граф - Википедия - Bivariegated graph

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

Примеры

В Граф Петерсена, показанный ниже, является двояким графом: если его разбить на внешний пятиугольник и внутреннюю пятиконечную звезду, каждая вершина на одной стороне разбиения будет иметь ровно одного соседа на другой стороне разбиения. В общем, то же самое верно для любого обобщенный граф Петерсена образованный соединением внешнего многоугольника и внутренней звезды с одинаковым количеством точек; например, это относится к График Мёбиуса – Кантора и График дезарга.

Petersen1 tiny.svg

Любой граф гиперкуба, такой как четырехмерный гиперкуб, показанный ниже, также является бивариегированным.

Hypercubecentral.svg

Однако график, показанный ниже, не является двояким. Какие бы три независимых ребра вы ни выбрали, одно из них является ребром цикла.

6n-graf.svg

Двустворчатые деревья

Дерево Т с 2п вершин, является биваризованным тогда и только тогда, когда число независимости из Т является п, или, что то же самое, тогда и только тогда, когда он имеет идеальное соответствие.[1]

Обобщения

В k-варигированный граф, k ≥ 3, можно определить аналогично. Граф называется k-варигируется, если его набор вершин можно разбить на k равные части, так что каждая вершина смежна ровно с одной вершиной из любой другой части, не содержащей ее.[2]

Примечания

  1. ^ а б Беднарек и Сандерс (1973).
  2. ^ а б Бхат-Наяк, Чоудум и Найк (1978).
  3. ^ Загадка (1978).

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

  • Беднарек, А. Р .; Сандерс, Э. Л. (1973), "Характеристика двояковыпуклых деревьев", Дискретная математика, 5: 1–14, Дои:10.1016 / 0012-365X (73) 90022-8.
  • Бхат-Наяк, Васанти Н.; Чоудум, С.А.; Найк, Ранджан Н. (1978), "Характеризация 2-пестрых графов и 3-пестрых графов", Дискретная математика, 23: 17–22, Дои:10.1016 / 0012-365X (78) 90182-6.
  • Бхат-Наяк, Васанти Н.; Коджай, В. Л.; Найк, Ранджан Н. (1980), «Принудительно 2-вариативные последовательности степеней», Utilitas Math., 18: 83–89.
  • Бхат-Наяк Васанти Н., Ранджан Н. Найк, Дальнейшие результаты по двумерным графам, Utilitas Math. 12 (1977) 317–325.
  • Джавдекар, Медха (1980), "Характеристика насильственного k-вариегированные последовательности степеней, k ≥ 3", Дискретная математика, 29 (1): 33–38, Дои:10.1016 / 0012-365X (90) 90284-O.
  • Джавдекар, Медха (1980), "Характеристика k-вариегированные графики, k ≥ 3", Дискретная математика, 32 (3): 263–270, Дои:10.1016 / 0012-365X (80) 90264-2
  • Риддл, Фэй А. (1978), Биварифицированные графы и их изоморфизмы, Кандидат наук. докторская диссертация, Университет Флориды.