Итало Хосе Дейтер (17 декабря 1939 г.) - американский математик , родившийся в Аргентине , бывший профессор математики и информатики ( Университет Пуэрто-Рико , август 1984 г. - февраль 2018 г.) и исследователь в области алгебраической топологии , дифференциальной топологии , теории графов , теория кодирования и теория дизайна . Он получил степень лиценциата в области математики в Университете Буэнос - Айресе в 1967 году, прибыл в Университете Рутгерса в 1970 году с помощью Гуггенхайма и получил там докторскую степень. получил степень по математике в 1975 году под руководством профессора Теда Петри [1] при поддержке Национального научного фонда . С 1977 по 1984 год он был профессором Федерального университета Санта-Катарина , Бразилия , с грантами Национального совета по научному и технологическому развитию (CNPq).
Итало Хосе Дейтер | |
---|---|
Родившийся | 17 декабря 1939 г. (возраст Баия-Бланка , Аргентина | 81)
Национальность | Аргентинский американец |
Альма-матер | |
Известен | |
Научная карьера | |
Поля | |
Учреждения | Университет Пуэрто-Рико, кампус Рио-Пьедрас |
Докторант | Тед Петри |
Дейтер был приглашенным научным сотрудником в ряде исследовательских институтов, включая Университет Сан-Паулу , Национальный институт математики Пура и Апликада , Федеральный университет Риу-Гранди-ду-Сул , Кембриджский университет , Национальный автономный университет Мексики , Университет Саймона Фрейзера , Университет Виктории , Нью-Йоркский университет , Иллинойский университет в Урбане-Шампейн , Университет Макмастера , DIMACS , Автономный университет Барселоны , Технический университет Дании , Обернский университет , Политехнический университет Каталонии , Мадридский технический университет , Карлов университет , Оттавский университет и Симон Боливарский университет . Разделы ниже описывают актуальность работы Дейтера в областях исследований, упомянутых в первом абзаце выше или в соседней рамке.
Алгебраическая и дифференциальная топология
В 1971 году Тед Петри [2] высказал предположение , что если X является замкнутой , гладкой 2 п - мерный гомотопический комплексное проективное пространство , что допускает нетривиальное гладкое действие этого круга , и если функция часов, отображение X на 2 п - мерный комплекс проективное пространство , является гомотопической эквивалентностью, то h сохраняет классы Понтрягина . В 1975 году Дейтер [3] доказал гипотезу Петри для n = 3, установив таким образом, что каждое замкнутое гладкое 6-мерное гомотопически комплексное проективное пространство должно быть комплексным 3-мерным проективным пространством CP 3 . Результат Дейтера наиболее актуален ввиду экзотических S 1 -действий Петри на CP 3 , [4] (кроме тривиальных S 1 -действий на CP 3 ).
Пусть О компактная группа Ли , пусть У гладкое G - многообразие и пусть F A G - волокна отображение между G- векторных расслоений той же размерности над Y , которые на каждом G - волокно является правильным и имеет степень один. Петри [2] также спросил: каковы необходимые и достаточные условия существования гладкого G-отображения, собственно G-гомотопного F и трансверсального нулевому сечению? Дейтер [5] представил оба типа условий, которые не близки к необходимому и достаточному условию из-за контрпримера. [5]
Основным инструментом, задействованным в установлении вышеизложенных результатов путем сведения проблем дифференциальной топологии к решениям алгебраической топологии, является эквивариантная алгебраическая K-теория , где эквивариантность понимается по отношению к группе, заданной окружностью , то есть единичной окружности комплексной плоскости .
Теория графов
Теорема Эрдеша – Посы и нечетные циклы
В 1962 году Пол Эрдеш и Лайош Поза доказали, что для любого натурального числа k существует такое натуральное число k ', что для каждого графа G либо (i) G имеет k вершинно-непересекающихся (длинных и / или четных) циклов, либо (ii ) существует подмножество X из менее чем k 'вершин графа G такое, что G \ X не имеет (длинных и / или четных) циклов. Этот результат, известный сегодня как теорема Эрдеша – Посы , не может быть распространен на нечетные циклы. Фактически, в 1987 году Дейтер и Виктор Нейман-Лара [6] показали, что для целого числа k> 0 существует граф G, не имеющий непересекающихся нечетных циклов такой, что число вершин G, удаление которых уничтожает все нечетные циклы G, равно выше k.
Любляна граф в двоичном 7-кубе
В 1993 годе [7] Браувер , Dejter и Томасен описали неориентированный , двудольный граф с 112 вершин и 168 ребер , ( пол-симметричного , то есть края транзитивны , но не вершина-транзитивные , кубический граф с диаметром 8, радиус 7, хроматические номер 2, хроматический индекс 3, обхват 10, ровно 168 циклов длины 10 и 168 циклов длины 12), известный с 2002 года как граф Любляны . Они [7] также установлено , что Dejter граф , [8] , полученный путем удаления копию кода Хэмминга длины 7 из двоичного 7- куба , допускает 3- разложение на две копии графа Ljubljana . Смотрите также. [9] [10] [11] [12] [13] [14] Более того, отношения этого предмета с подмножествами, блокирующими квадрат, и с совершенными доминирующими множествами (см. Ниже) в гиперкубах были рассмотрены Дейтером и др. с 1991 г. в, [12] [13] [14] и. [9]
Фактически, в [7] были даны ответы на два вопроса, а именно:
(а) Сколько цветов нужно для раскраски n- куба без одноцветных 4-циклов или 6-циклов? Брауэр , Дейтер и Томассен [7] показали, что четырех цветов достаточно, и тем самым решили проблему Эрдеша. [15] (Независимо найдено FRKChung. [16] Усовершенствовав это, Марстон Кондер [17] в 1993 году показал, что для всех n не менее 3 ребра n -куба могут быть 3-раскрашены таким образом, что не является монохроматическим 4-циклом или 6-циклом).
(б) Какие вершинно-транзитивные индуцированные подграфы есть в гиперкубе? График Dejter упоминалось выше , является 6-регулярная, вершина-переходных и, как это было предложено, ее края могут быть 2-цветные , так что две полученные монохроматические подграфы изоморфны полу-симметричным Ljubljana графа обхвата 10.
В 1972 г. И. З. Bouwer [18] приписывается граф с указанными свойствами графа Ljubljana к RM Фостер .
Граф Кокстера и граф Клейна
В 2012 году Дейтер [19] показал, что 56-вершинный кубический граф Клейна F {56} B [20], обозначаемый здесь Γ ', может быть получен из 28-вершинного кубического графа Кокстера Γ путем адекватного сжатия квадратов 24 7-циклы графа Γ, наделенные ориентацией, полученной при рассмотрении Γ как-ультраоднородный [21] орграф , где- это набор, образованный как ориентированными 7-циклами, так и 2-дугами, которые плотно скрепляют эти ориентированные 7-циклы в Γ. В процессе видно, что Γ 'является C'-ультраоднородным (неориентированным) графом, где C' - это совокупность, образованная как 7-циклами, так и 1-путями, которые плотно скрепляют эти 7-циклы в Γ '. Это дает вложение Γ 'в 3-тор T 3, которое образует отображение Клейна [22] в обозначениях Кокстера (7,3) 8 . Двойственный граф Г»в Т 3 является дистанционно регулярным квартиком Клейна граф, с соответствующим двойной картой Кокстером обозначений (3,7) 8 . Другие аспекты этой работы также цитируются на следующих страницах:
Битангенсы квартики .
Граф Кокстера .
График Хивуда .
В 2010 г. Дейтер [23] адаптировал понятие-ultrahomogeneous график для орграфов , и представлен сильно связного-ультраоднородный ориентированный граф на 168 вершинах и 126 попарно непересекающихся по дуге 4-циклах с регулярной степенью и исходящей степенью 3 и без цепей длины 2 и 3 путем изменения определения графа Кокстера с помощью пучков упорядоченных прямых плоскости Фано, в которых пучки были заменены заказанные карандаши.
Изучение ультраоднородных графов (соответственно орграфов ) восходит к Шихану, [24] Гардинеру , [25] Ронсу, [26] Камерону , [27] Гольфанду и Клину, [28] (соответственно, Фраиссе , [ 29] Лахлан и Вудроу, [30] Черлин [31] ). См. Также стр. 77 в « Бонди и Мурти» . [32]
K d -ультраоднородные конфигурации
В 2013 г. [33] мотивированный изучением связных графов Менгера [34] самодвойственных 1-конфигураций (n d ) 1 [35] [36], представимых в виде K d -ультраоднородных графов, Дейтер задался вопросом, для каких значений n такие существуют графы, поскольку они дают наиболее симметричные, связанные, непересекающиеся по ребрам объединения n копий K d на n вершинах, в которых роли вершин и копий K d взаимозаменяемы. Для d = 4 известны следующие значения n: n = 13, 21 [37] [38] [39] и n = 42, [40] Эта ссылка, сделанная Дейтером в 2009 г., дает граф G, для которого каждый изоморфизм между две из 42 копий K 4 или две из 21 копии K 2,2,2 в G расширяются до автоморфизма G. Хотя было бы интересно определить спектр и кратности задействованных значений n, Дейтер [33] вносит значение n = 102 через схему ассоциации Биггса-Смита (представленную с помощью секстетов [41] mod 17), показанную для управления прикреплением 102 (кубооктаэдрических) копий линейного графика 3-куба к 102 (тетраэдрические) копии K 4 , которые разделяют каждый треугольник с двумя копиями кубооктаэдрических копий и гарантируют, что дистанционный 3-граф графа Биггса-Смита является графом Менгера самодуальной 1-конфигурации (102 4 ) 1 . Этот результат [33] было получено в качестве применения преобразования дистанционно-транзитивных графов в графах С-ВГ , который привел вышеупомянутый документ [19] , а также позволило противостоять, [42] , как орграфы, тем Летучка графа к Граф Дезарга .
Эти приложения, а также ссылка [43] используют следующее определение. Для данного семейства орграфов C орграф G называется C-ультраоднородным, если любой изоморфизм между двумя индуцированными членами C в G продолжается до автоморфизма группы G. В [43] показано, что ровно 7 дистанционно транзитивных кубических Графы среди существующих 12 обладают особым ультраоднородным свойством по отношению к ориентированным циклам, реализующим обхват, который позволяет построить связанный орграф Кэли с аналогичными ультраоднородными свойствами, в котором эти ориентированные циклы кажутся минимально «раздвинутыми» или «разделенными» и чье описание действительно красиво и проницательно.
Гамильтоничность в графах
В 1983 г. Дейтер [44] обнаружил, что эквивалентное условие существования Z 4 -цикла Гамильтона на графе ходов шахматного коня обычного типа (1,2), (соответственно (1,4)) на 2nx2n- доска состоит в том, что n нечетно больше 2 (соответственно 4). Эти результаты цитируются И. Парберри [45] [46] в связи с алгоритмическими аспектами проблемы рыцарского тура.
В 1985 г. Дейтер [47] представил технику построения циклов Гамильтона в графах среднего уровня . О существовании таких циклов предположили И. Гавел в 1983 г. [48] и М. Бак и Д. Видеманн в 1984 г. [49] (хотя Бела Боллобас представил это Дейтеру как гипотезу Пола Эрдёша в январе 2004 г.). 1983) и установлен Т. Мютце [50] в 2014 году. Этот метод использовался в ряде статей Дейтера и студентов. [51] [52] [53] [54] [55] [56]
В 2014 году Дейтер [57] вернулся к этой проблеме и установил каноническое упорядочение вершин в фактор-графе (каждого графа среднего уровня под действием группы диэдра) во взаимно однозначном соответствии с начальным участком система нумерации (присутствует в виде последовательности A239903 в энциклопедии целочисленных последовательностей по Neil Sloane ) [58] состоит из ограниченных строк роста [59] [60] (с к-е числа каталонского [61] выражаются посредством строки 10 ... 0 с k «нулями» и одной « единицей », как это делает Дж. Арндт на стр. 325 [60] ) и связаны с лексическим соответствием цветов Кирстеда-Троттера. [62] Эта система нумерации может применяться к диэдрально-симметричной ограниченной версии гипотезы о средних уровнях.
В 1988 г. Дейтер [63] показал, что для любого натурального числа n можно определить все 2-покрывающие графы полного графа K n на n вершинах; кроме того, он показал, что среди них есть только один граф, который связан и имеет максимальную группу автоморфизмов, которая оказывается двудольной; Дейтер также показал, что i-покрывающий граф K n является гамильтоновым, если i меньше 4, и что получаются должным образом минимальные связные негамильтоновы покрывающие графы K n , которые являются 4-покрытиями K n ; Кроме того, в этой работе были построены негамильтоновы связные 6-покрытия K n .
Также в 1988 году Дейтер [64] показал, что если k, n и q - целые числа, такие, что если 0 меньше 2k, а это меньше n = 2kq1, то граф, порожденный обобщенными ходами шахматного коня типа (1,2k) на 2n x 2n-шахматной доске, имеет гамильтоновые циклы, инвариантные относительно четверти поворота. Для k = 1, соответственно 2, это распространяется на следующее необходимое и достаточное условие существования таких циклов: что n нечетно и больше 2k-1.
В 1990 году Дейтер [65] показал, что если n и r - целые числа больше 0 и n + r больше 2, то разность двух концентрических квадратных досок A и B с (n + 2r) 2 и n 2 элементами соответственно имеет цикл Гамильтона шахматного рыцаря инвариантен относительно четверти оборота тогда и только тогда, когда r больше 2 и либо n, либо r нечетно.
В 1991 году Дейтер и Нейман-Лара [66] показали, что для группы Z n, свободно действующей на графе G, понятие графа напряжений [67] применяется для поиска гамильтоновых циклов в G, инвариантных относительно действия Z n на G. В качестве приложения для n = 2 и 4 были найдены эквивалентные условия и нижние оценки для циклов Гамильтона шахматного рыцаря, содержащих пути, охватывающие квадратные квадранты и прямоугольные полуподоски, соответственно.
Идеальные доминирующие наборы
Совершенное доминирующее множество S графа G - это множество вершин графа G такое, что каждая вершина G либо находится в S, либо смежна ровно с одной вершиной графа S. Вейхзель [68] показал, что совершенное доминирующее множество n- куб Q n индуцирует подграф Q n , компоненты которого изоморфны гиперкубам, и предположил, что каждый из этих гиперкубов имеет одинаковую размерность. В 1993 году Дейтер и Вейхзель [14] представили первые известные случаи, в которых эти компоненты имеют одинаковое измерение, но разные направления, а именно в 8-кубе с компонентами, которые представляют собой 1-кубы, каждый из которых образован одним ребром, с задействованными ребрами. в:
(а) четыре разных направления, как сказал Александр Фельценбаум Вейхзелю в Реховоте, Израиль, 1988 г .;
(b) восемь различных направлений, включая код Хэмминга длины 7, граф Хивуда , плоскость Фано и систему троек Штейнера порядка 7.
Результат п. (А) выше немедленно распространяется на совершенные доминирующие множества в кубах размерностей, которые являются степенями двойки, компоненты которых содержат каждое единственное ребро в половине координатного направления. С другой стороны, в 1991 г. Дейтер и Фелпс [69] расширили результат (b) выше снова на кубы, размеры которых являются степенями двойки , с компонентами, каждая из которых состоит из уникального ребра во всех направлениях координат. (Однако этот результат пока не распространяется на q-ичные кубы, как запланировано авторами).
На гипотезу Вейкселя [68] положительно ответили Остергард и Уикли [70], которые нашли совершенное доминирующее множество в 13-кубе, компонентами которого являются 26 4-кубов и 288 изолированных вершин. Дейтер и Фелпс [71] дали короткое и элегантное доказательство этого результата.
Эффективные доминирующие наборы
E-цепь - это счетное семейство вложенных графов, каждый из которых имеет эффективное доминирующее множество. Коды Хэмминга в n-кубах представляют собой классический пример E-цепочек. Дейтер и Серра [72] предоставили инструмент для построения E-цепочек графов Кэли. Этот инструмент использовался для построения бесконечных семейств E-цепочек графов Кэли, порожденных деревьями транспонирования диаметра 2 на симметрических группах. Эти графы, известные как звездные графы [73], обладали свойством эффективного доминирования, установленным Арумугамом и Кала. [74] В отличие от этого, Дейтер и О. Томайконца [75] показали, что не существует эффективного доминирующего множества ни в одном графе Кэли, порожденном деревом транспонирования диаметра 3. Было проведено дальнейшее исследование многопоточных деревьев расстояний и E-множеств звездных графов. пользователя Dejter. [76] В 2012 году Дейтер адаптировал приведенные выше результаты к случаю орграфов . [77] Фактически, эффективные доминирующие множества в наихудшем случае в орграфах задуманы так, что их присутствие в определенных сильных орграфах соответствует наличию эффективных доминирующих множеств в звездных графах. Тот факт, что звездчатые графы образуют так называемую плотную сегментарную соседнюю E-цепь [72] , отражается в соответствующем факте для орграфов.
Квазиидеальные доминирующие множества
В 2009 году [78] Дейтер определил подмножество вершин S графа G как квази-совершенное доминирующее множество в G, если каждая вершина v графа G не в S смежна с d v ∈ {1,2} вершинами графа S, а затем исследовал совершенные и квазисовершенные доминирующие множества в регулярном тесселяционном графе символа Шлефли {3,6} и в его тороидальных фактор-графах, что дает классификацию их совершенных доминирующих множеств и большей части их квазисовершенных доминирующих множеств S с индуцированными компонентами формы K ν , где ν ∈ {1,2,3} зависит только от S.
Теория кодирования
Инварианты совершенных кодов с исправлением ошибок
Инварианты совершенных кодов с исправлением ошибок были рассмотрены Дейтером в [79] [80] и Дейтером и Дельгадо [81], в которых показано, что совершенный код C с исправлением 1 ошибки «складывается» над своим ядром с помощью Системы троек Штейнера, связанные с его кодовыми словами. Результирующее «сворачивание» дает граф, инвариантный для C через конфигурации и тензоры Паша. Более того, инвариант является полным для кодов Васильева [82] длины 15 с точки зрения Ф. Хергерта [83], показывая существование неаддитивных пропелинейных 1-совершенных кодов, [84] [85] и позволяющих визуализировать пропелинейные кода посредством коммутативной группы, образованной его классами мод-ядра, а также для обобщения понятия пропелинейного кода путем расширения задействованной композиции перестановок на более общий групповой продукт.
Обобщение совершенных кодов Ли
Руководствуясь прикладной проблемой в компьютерной архитектуре, Арауджо, Дейтер и Хорак [86] ввели понятие идеального доминирующего по расстоянию множества, PDDS, в графе, представляя собой обобщение совершенных кодов Ли, [87] совершенных по диаметру кодов, [88] ] и других кодов и доминирующих множеств, тем самым инициируя систематическое изучение таких множеств вершин. Некоторые из этих наборов, относящиеся к мотивирующему приложению, были построены, а отсутствие других было продемонстрировано. Фактически , было сформулировано расширение давней гипотезы Голомба-Велча [87] в терминах PDDS.
Всего совершенных кодов
Согласно Дейтеру и Дельгадо, [89] для заданного подмножества вершин S 'стороны P m сеточного графа G размером mxn идеальные доминирующие множества S в G, где S' является пересечением S с V (P m ), могут быть определяется с помощью исчерпывающего алгоритма времени работы O (2 m + n ). Расширяя алгоритм до бесконечных сеточных графов шириной m-1, периодичность делает двоичное дерево решений сокращаемым до конечного многопоточного дерева, замкнутый обход которого дает все такие множества S. Графы, индуцированные дополнениями таких множеств S, могут быть кодируется массивами упорядоченных пар натуральных чисел, для увеличения и определения которых существует более быстрый алгоритм. Недавняя характеристика сеточных графов, имеющих полные совершенные коды S (т.е. только с 1-кубами в качестве индуцированных компонентов, также называемая 1-PDDS [86] и DPL (2,4) [88] ), выполненная Клостермейером и Голдвассером [90]. ] позволил Дейтеру и Дельгадо [89] показать, что эти множества S являются ограничениями только одного полного совершенного кода S 1 в графе планарной целочисленной решетки, с дополнительным бонусом, заключающимся в том, что дополнение к S 1 дает апериодическое разбиение, подобное замощению Пенроуза. черепица. Напротив, параллельные, горизонтальные, полностью совершенные коды в графе планарной целочисленной решетки находятся в соответствии 1-1 с дважды бесконечными {0,1} -последовательностями.
Дейтер показал [91], что существует несчетное количество параллельных полных совершенных кодов в плоском целочисленном решеточном графе L; напротив, существует только один 1-совершенный код и только один полный совершенный код в L, причем последний код ограничивается полными совершенными кодами графов с прямоугольной сеткой (что дает асимметричный тайлинг Пенроуза на плоскости); в частности, Дейтер охарактеризовал все продукты цикла C m x C n, содержащие параллельные полные совершенные коды, а также d-совершенные и полностью совершенные кодовые разбиения L и C m x C n , причем первые имели в качестве фактор-графа неориентированные графы Кэли циклическая группа порядка 2d 2 + 2d + 1 с образующей {1,2d 2 }.
В 2012 году Араужо и Дейтер [92] внесли предположительный вклад в классификацию решетчатых полных совершенных кодов в n-мерных целочисленных решетках с помощью пар (G, F), образованных абелевыми группами G и гомоморфизмами F из Z n на G, в соответствии с цитированной выше работой Араужо-Дейтер-Хорак. [86]
Комбинаторные конструкции
С 1994 года Дейтер участвовал в нескольких проектах Combinatorial Designs, первоначально предложенных Александром Розой, CC Lindner и CA Rodger, а также работал с Э. Мендельсоном, Ф. Франеком, Д. Пайком, П. А. Адамсом, Э. Дж. Биллингтоном, Д. Г. Хоффманом, М. Мешка и другие, которые дали результаты по следующим предметам:
Инварианты для 2-факторизации и циклических систем, [93]
Треугольники в 2-факторизациях, [94] [95]
Количество 4-циклов в 2-факторизациях полных графов, [96]
Направил почти решаемую проблему Гамильтона-Ватерлоо, [97]
Количество 4-циклов в 2-факторизациях K 2n минус 1-фактор, [98]
Почти разрешимые 4-тактные системы, [99]
Критические наборы для завершения латинских квадратов [100]
Почти разрешимые максимальные упаковки полных графов с 4-циклами. [101]
Рекомендации
- ^ Итало Хосе Dejter на Математическая генеалогия
- ^ a b Петри Т. "Гладкие S 1 -действия на гомотопических комплексных проективных пространствах и смежные вопросы", Бюлл. Амер. Математика. Soc. 78 (1972) 105–153
- ^ Дейтер IJ "Гладкие S 1 -многообразия в гомотопическом типе CP 3 ", Mich. Math. Jour. 23 (1976), 83–95.
- ^ Петри Т. "Экзотические S 1 -действия на CP 3 и связанные темы", Инвент. Математика. 17 (1972), 317–327.
- ^ a b Dejter IJ "G-трансверсальность к CP ^ n", Springer-Verlag Lecture Notes по математике, 652 (1976), 222–239
- ^ Дейтер IJ; Нойман-Лара В. "Неограниченность нечетной циклической трансверсальности", Сб. Математика. Soc. Дж. Бойяи, 52 (1987), 195–203
- ^ а б в г Брауэр AE; Дейтер Эй Джей; Томассен К. "Высокосимметричные подграфы гиперкубов", J. Algebraic Combinat. 2, 22-25, 1993 г.
- ^ Клин М .; Лаури Дж .; Зив-Ав М. "Связи между двумя полусимметричными графами на 112 вершинах через призму ассоциативных схем", Jour. Symbolic Comput., 47–10, 2012, 1175–1191.
- ^ a b Borges J .; Дейтер И. Я. "О совершенных доминирующих множествах в гиперкубах и их дополнениях", J. Combin. Математика. Комбинировать. Comput. 20 (1996), 161-173
- ^ Дейтер IJ "О симметричных подграфах 7-куба: обзор", Discrete Math. 124 (1994) 55–66
- ^ Дейтер IJ "Симметрия факторов 7-кубической оболочки Хэмминга", J. Combin. Des. 5 (1997), 301–309
- ^ а б Дейтер И.Дж.; Гуан П. «Блокирующие квадраты подмножества ребер в гиперкубах и предотвращение вершин», Теория графов, комбинаторика, алгоритмы и приложения (Сан-Франциско, Калифорния, 1989), 162–174, SIAM, Филадельфия, Пенсильвания, 1991
- ^ а б Дейтер И.Дж.; Пуйоль Дж. «Совершенное доминирование и симметрия в гиперкубах», Труды Двадцать шестой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1995). Congr. Нумер. 111 (1995), 18–32
- ^ a b c Дейтер Эй Джей; Weichsel PM "Скрученные совершенные доминирующие подграфы гиперкубов", Труды Двадцать четвертой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1993). Congr. Нумер. 94 (1993), 67–78.
- ^ Эрдеш П. «Некоторые из моих любимых нерешенных проблем», в: Дань уважения Полу Эрдешу (А. Бейкер, Б. Боллобас и А. Хайнал, ред.), Cambridge Univ. Press, Кембридж. 1990, 467–478.
- ^ Чунг ФРК "Подграфы гиперкуба, содержащие немалые четные циклы", 1. Журнал теории графов, 16 (1992) 273–286.
- ^ Кондер М. "Бестигранные подграфы гиперкубов", Журнал теории графов, 17–4 (1993), 477–479.
- ^ Бауэр IZ "На ребрах, но не вершинных транзитивных регулярных графах", J. Combin. Теория (В) 12 (1972), 32-40.
- ^ a b Дейтер И. Дж. От графа Кокстера к графу Клейна, Журнал теории графов, 70-1 (2012), 1–9.
- ^ Вайсштейн, Эрик В. "Кубический симметричный граф". Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/CubicSymmetricGraph.html
- ^ Исаксен округ Колумбия; Янковский С .; Проктор С. « О K * -ультраоднородных графах. Архивировано 23 марта 2014 г. на Wayback Machine », Ars Combinatoria, 82 (2007), 83–96.
- ^ Schulte E .; Wills JM "Полиэдральная реализация карты {3, 7} 8 Феликса Клейнана римановой поверхности рода 3", J. London Math. Soc., S2-32 (1985), 539–547.
- ^ Дейтер IJ "На4 -ультраоднородный ориентированный граф », Дискретная математика, (2010), 1389–1391.
- ^ Шиэн Дж. "Гладко вложимые подграфы", J. London Math. Soc., S2-9 (1974), 212–218.
- ^ , Гардинер А. «Однородные графы», Журнал комбинаторной теории, серия B, 20 (1976), 94–102.
- ^ Ронс К. «Об однородных графах», J. London Math. Soc., S2-17 (1978), 375–379.
- ^ Cameron PJ "6-транзитивные графы", J. Combin. Теория Сер. В 28 (1980), 168–179.
- ^ Гольфанд Ja. Ju .; Клин М. Х. "О k -однородных графах", Алгоритмические исследования в комбинаторике, 186 (1978), 76–85.
- ^ Fraïssé R. "Sur l'extension aux Relations de quelques proprietes des ordres", Ann. Sci. Ecole Norm. Как дела. 71 (1954), 363–388.
- ^ AH Lachlan AH; Вудроу Р. "Счетные сверходнородные неориентированные графы", Пер. Амер. Математика. Soc. 262 (1980), 51–94.
- ^ Черлин Г. Л. "Классификация счетных однородных ориентированных графов и счетных однородных n -турниров", Воспоминания амер. Математика. Soc., Т. 131, номер 612, Провиденс, Род-Айленд, январь 1988 г.
- ^ Bondy A .; Murty USR; Теория графов, Springer-Verlag, 2008.
- ^ a b c Дейтер И. Дж. "На самодвойственной 1-конфигурации K 4 -UH (102 4 1, arXiv: 1002.0588 [math.CO].
- ^ Coxeter HSM "Самодуальные конфигурации и регулярные графы", Bull. Амер. Математика. Soc., 56 (1950), 413-455; http://www.ams.org/journals/bull/1950-56-05/S0002-9904-1950-09407-5/S0002-9904-1950-09407-5.pdf .
- ^ Gropp, Харальд (1994). «О симметричных пространственных конфигурациях» . Дискретная математика . 125 (1–3): 201–209. DOI : 10.1016 / 0012-365X (94) 90161-9 .
- ^ Колборн CJ; Диниц Дж. Х. "Справочник комбинаторных схем CRC", CRC, 1996.
- ^ Грюнбаум Б. "Конфигурации точек и линий", Grad. Тексты по математике. 103, амер. Математика. Соц, Провиденс Р.И., 2009.
- ^ Grünbaum B .; Ригби Дж. Ф. "Настоящая конфигурация (21 4 )", Жур. Лондонская математика. Soc., Sec. Сер. 41 (2) (1990), 336–346.
- ^ Писанский Т .; Серватиус Б. "Конфигурации с графической точки зрения", Биркхойзер, 2013.
- ^ Дейтер И. Дж. «На {K 4 , K 2,2,2 } -ультраоднородном графе», Австралазийский журнал комбинаторики, 44 (2009), 63-76.
- ^ Биггс Н.Л .; Хоар MJ "Конструкция секстета для кубических графов", Combinatorica, 3 (1983), 153-165.
- ^ Дейтер IJ "Противостояние диграфов Паппа-Дезарга", Jour. Комбинировать. Математика. Комбинировать. Comput ", появится в 2013 г., arXiv: 0904.1096 [math.CO]
- ^ a b Дейтер И. Дж. "Ориентация и разделение дистанционно-транзитивных графов", Ars Mathematica Contemporanea, 5 (2012) 221-236
- ^ IJ Дейтер "Эквивалентные условия для проблемы Эйлера на Z 4 -циклах Гамильтона", Ars Combinatoria, 16B, (1983), 285-295
- ^ https://larc.unt.edu/ian/research/puzzles/knightstour/
- ^ I. Parberry "Эффективный алгоритм для задачи тура Найта", Дискретная прикладная математика, 73, (1997), 251-260
- ^ Дейтер IJ "Гамильтоновы циклы и факторы двудольных графов", в Y. Alavi et al., Eds., Graph Theory and its Appl. в Alg. и комп. Sci., Wyley, 1985, 189–199.
- ^ Гавел I. "полутраекторий в направленных кубов", в: М. Фидлер (Ed.), Графов и других комбинаторных Topics, Teubner-Texte математики, Teubner, Лейпциг, 1983, стр. 101-108..
- ^ Бак М. и Видеманн Д. «Коды Грея с ограниченной плотностью», Дискретная математика, 48 (1984), 163-–171.
- ^ Мютце Т. "Доказательство гипотезы среднего уровня", Arxiv 1404-4442
- ^ Дейтер И. Дж. "Стратификация по гамильтонности", Congressus Numeranium, 47 (1985) 265-272.
- ^ Дейтер IJ; Кинтана Дж. «Длинные циклы в графах вращающихся дверей», Congressus Numerantium, 60 (1987), 163–168.
- ^ Дейтер IJ; Cordova J; Кинтана Дж. «Два гамильтоновых цикла в двудольных отражающих графах Кнезера», Discrete Math. 72 (1988) 63-70.
- ^ Дейтер IJ; Кинтана Дж. «О расширении гипотезы И. Гавела», в работе Ю. Алави и др. ред., Теория графов, Комбин. and Appl., J. Wiley 1991, vol I, 327-342.
- ^ Дейтер IJ; Cedeno W .; Жореги В. "Диаграммы Фрухта, булевы графы и циклы Гамильтона", Scientia, Ser. А. Математика. Sci., 5 (1992/93) 21-37.
- ^ Дейтер IJ; Cedeno W .; Жореги В. «Заметка о F-диаграммах, булевых графах и гамильтоновых циклах», Дискретная математика. 114 (1993), 131-135.
- ^ Дейтер IJ "Упорядочивание уровней L k и L k + 1 из B 2k + 1 ".
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A239903» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Ruskey F. "Простые комбинаторные коды Грея, построенные путем обращения подсписок", Lecture Notes in Computer Science, 762 (1993) 201-208.
- ^ а б Арндт Дж., Вычислительные вопросы: идеи, алгоритмы, исходный код, Springer, 2011.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A000108» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Кирстед HA; Троттер В. Т. "Явные соответствия на двух средних уровнях булевой решетки", Заказ 5 (1988), 163-171.
- ^ IJ Дейтер "Минимальные гамильтоновы и негамильтоновы накрывающие графы K n ", Ars Combinatoria, 25-C, (1988), 63-71.
- ^ IJ Dejter "(1,2k) -Гамильтоновые циклы Чесснайта, инвариантные относительно четверти оборота", Scientia, Ser. А. Математика. Sci., 2 (1988), 39-51.
- ^ IJ Дейтер "Четвертьоборотные и гамильтоновые циклы для кольцевых графов шахматного рыцаря", Scientia, Ser. А. Математика. Sci., 4 (1990/91), 21-29.
- ^ IJ Дейтер и В. Нейман-Лара «Графики напряжения и циклы Гамильтона», в издании В. Кулли, успехи в теории графов, Vishwa Int. Publ., Gulbarga, India, 1991, 141–153.
- ^ JL Gross и TW Tucker "Topological Graph Theory" Wiley, New York (1987).
- ^ a b Weichsel P. "Доминирующие множества в n-кубах", Jour. теории графов, 18 (1994), 479-488
- ^ Дейтер. IJ; Фелпс К.Т. "Об идеальном преобладании двоичных кубов", препринт.
- ^ Östergård P .; Weakley WD "Построение покрывающих кодов с заданными автоморфизмами", Des. Коды Cryptogr. 16 (1999), 65-73
- ^ Дейтер IJ; Фелпс К.Т. "Тернарные коды Хэмминга и двоичные совершенные накрывающие коды", в: А. Барг и С. Лицын, ред., Коды и схемы ассоциации, DIMACS Ser. Дискретная математика. Теорет. Comput Sci. 56, амер. Математика. Soc., Провиденс, Род-Айленд, 111–113 "
- ^ а б Дейтер И.Дж.; Серра О. "Эффективные доминирующие множества в графах Кэли", Discrete Appl. Матем., 129 (2003), вып. 2-3, 319-328.
- ^ Акерс SB; Кришнамурти Б. "Теоретико-групповая модель для симметричных взаимосвязанных сетей", IEEE Trans. Comput., 38 (1989), 555-565.
- ^ Arumugam S .; Кала Р. "Параметры доминирования звездных графов", Ars Combinatoria, 44 (1996) 93-96
- ^ Дейтер IJ; Томайконца О. "Отсутствие эффективных доминирующих множеств в графах Кэли, порожденных деревьями транспозиции диаметра 3", Дискрет. Матем., 232 (2017), 116-124.
- ^ Дейтер IJ "Звездные графы: деревья расстояний с резьбой и E-множества", J. Combin. Математика. Комбинировать. Comput. 77 (2011), 3-16.
- ^ Дейтер И.Дж. «Эффективные доминирующие множества наихудшего случая в орграфах», Дискретная прикладная математика, 161 (2013) 944–952. Первый онлайн DOI 10.1016 / j.dam.2012.11.016
- ^ Дейтер И.Дж. "Квазисовершенное доминирование в треугольных решетках", Математическая теория графов, 29 (1) (2009), 179-198.
- ^ Дейтер IJ "SQS-графы расширенных 1-совершенных кодов", Congressus Numerantium, 193 (2008), 175-194.
- ^ Дейтер IJ "STS-графический инвариант для совершенных кодов", J. Combin. Математика. Комбинировать. Вычисл., 36 (2001), 65-82.
- ^ Дейтер IJ; Дельгадо А.А. "STS-Графы модульного ядра совершенных кодов", Дискретная математика, 253 (2005), 31-47.
- ^ Васильев Ю.Л. «О негрупповых плотноупакованных кодов», задача кибернетики, 8 (1962) 375-378 (на русском).
- ^ Hergert F, "Классы эквивалентности кодов Васильева длины 15", Springer-Verlag Lecture Notes 969 (1982) 176-186.
- ^ Rifà J .; Basart JM; Huguet L. "О полностью регулярных пропелинейных кодах" AAECC (1988) 341-355
- ^ Rifà J .; Пуйоль Дж. "Трансляция инвариантных пропелинейных кодов, Transact. Info. Th., IEEE, 43 (1997) 590-598.
- ^ a b c Араужо С; Дейтер Эй Джей; Хорак П. «Обобщение кодов Ли», Конструкции, коды и криптография, 70 77-90 (2014).
- ^ a b Голомб SW; Валлийский Л.Р. «Совершенные коды в метрике Ли и упаковка полимино», SIAM J. Applied Math. 18 (1970), 302-317.
- ^ a b Horak, P .; Аль-Бдаиви, Б.Ф. «Коды идеального диаметра Ли», IEEE Transactions on Information Theory 58-8 (2012), 5490-5499.
- ^ а б Дейтер И.Дж.; Дельгадо А.А. «Совершенное доминирование в графах с прямоугольной сеткой», Дж. Комбин. Математика. Комбинировать. Вычисл., 70 (2009), 177-196.
- ^ Klostermeyer WF; Гольдвассер Дж. Л. "Всего совершенных кодов в сеточных графах", Бюлл. Inst. Гребень. Appl., 46 (2006) 61-68.
- ^ Дейтер IJ "Совершенное доминирование в графах с регулярной сеткой", Austral. Jour. Комбайн., 42 (2008), 99-114
- ^ Дейтер IJ; Араужо К. «Решеточно-подобные полные совершенные коды», Математические обсуждения теории графов, 34 (2014) 57–74, DOI: 10.7151 / dmgt.1715.
- ^ Дейтер IJ; Ривера-Вега ИП; Роза Александер "Инварианты для 2-факторизаций и циклических систем", J. Combin. Математика. Комбинировать. Comput., 16 (1994), 129-152.
- ^ Дейтер IJ; Франек Ф .; Mendelsohn E .; Роза Александер "Треугольники в 2-факторизациях", Журнал теории графов, 26 (1997) 83-94.
- ^ Дейтер IJ; Франек Ф .; Роза Александер "Гипотеза о завершении для тройных систем Киркмана", Utilitas Mathematica, 50 (1996) 97-102
- ^ Дейтер IJ; Линднер СС; Роза Александер "Число 4-циклов в 2-факторизациях K n ", J. Combin. Математика. Комбинировать. Comput., 28 (1998), 101-112.
- ^ Дейтер IJ; Pike D .; Роджер К.А. "Направленная почти решаемая проблема Гамильтона-Ватерлоо", Австралас. J. Combin., 18 (1998), 201-208.
- ^ Адамс PA, Биллингтон EJ; Линднер CC "Число 4-циклов в 2-факторизациях K 2n минус 1-фактор}, Дискретная математика., 220 (2000), №1-3, 1-11.
- ^ Дейтер IJ; Линднер СС; Роджер CA; Мешка М. "Почти разрешимые четырехцикловые системы", J. Combin. Математика. Комбинировать. Вычисл., 63 (2007), 173-182.
- ^ Horak P .; Дейтер IJ "Завершающие латинские квадраты: критические множества, II", Jour. Комбинировать. Des., 15 (2007), 177-83.
- ^ Биллингтон EJ; Дейтер Эй Джей; Hoffman DG; Линднер CC "Почти разрешимые максимальные упаковки полных графов с 4-циклами", Графы и комбинаторика, 27 (2011), вып. 2, 161–170