Исследование максимального рода графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

В в е д е н и е

ГЛАВА I. ОБЩЕ СВОЙСТВА МАКСИМАЛЬНОГО РОДА ГРАФОВ.

§ 1.1. А- разложения, хордовость и максимальный род графов

§ 1.2.0-хордовые графы

§ 1.3.Хордово критические графы

§ 1.4.Существенность ребер графа относительно максимального рода.

ГЛАВА 2. НАХОЖДЕНИЕ МАКСИМАЛЬНОГО РОДА ГРАФОВ.

§ 2.1.Циклическая связность и максимальный род графов

§ 2.2.Максимальный род плоских графов.

§ 2.3.Полиномиальный алгоритм нахождения максимального рода связного графа.

§ 2.4.Применения полученных результатов

Л и т е р а т у р а.

Одна из наиболее важных и интересных проблем современной теории графов заключается в определении множества родов всех компактных ориентируемых 2-многообразий, в которые граф вкладывается 2-клеточно. Согласно известной теореме Р.А.Дьюка [27] о промежуточных вложениях, связный граф & вкладывается в ориентируемое 2-многообразие б'у рода V 2-клеточно тогда и только тогда, когда где ¡р" (С-) - абсолютный, а максимальный роды графа 0?.

В то время как исследования абсолютного рода (или просто рода) графов имеют почти столетнюю историю (первой работой в этой области можно считать статью П.Хивуда [ЗОЗ), первые публикации, посвященные максимальному роду графов, относятся к

1970 году. Это, в первую очередь работа Н.П.Хоменко и Э.Б.Яворского [21], в которой с помощью метода У- преобразований впервые был найден критерий 1-компонентной 2-клеточной вложимости графа От в ориентируемое 2-многообразие б» , представляющий собой следующее утверждение.

Теорема 9 [21] . Граф 0- вкладывается в ориентируемое 2-многообразие бу 1-компонентно 2-клеточно тогда и только тогда, когда в нем существуют такие V независимых пар смежных ребер, после удаления которых остается фактордерево графа £ .

С помощью этого критерия авторам удалось установить роды ориентируемых 2-многообразий, в которые I- или 2-компонентно 2-клеточно вкладываются графы Кл, фп, Кп,л . Тем самым впервые был найден максимальный род этих графов.

Понятие максимального рода графов было, однако, введено в

1971 году Е.А.Нордхаузом, Б.М.Стюартом и А.Т.Уайтом в работе

42], в которой также (другим методом) был найден максимальный род графа Кп . Эти же авторы вместе с Р.Д.Рингайзеном в работе [41]нашли условия, при которых максимальный род графа равен -нулю. Р.Д.Рингайзен в работе¿4б]нашел максимальный род некоторых плоских графов, а в работе[46]- максимальный род графа Кт,п. В раб от е/47] Р.Д.Рингайзен ввел в рассмотрение класс сверху вложимых графов , т.е. таких графов О , для которых - /. 7 > изучил ряд свойств этих графов и высказал несколько гипотез.

В 1973 году вышел в свет ряд работ, посвященных исследованию максимального рода графов с помощью метода У> - преобразований. Особое место среди этих работ заняла статья Н.П.Хоменко, Н.А.Островерхого и В.А.Кузьменко [19] , в которой была доказана следующая фундаментальная в теории максимального рода графов теорема.

ТеоремаА [19] . Максимальный род произвольного графа & равен максимальному числу таких независимых пар смежных ребер в б- , что граф, полученный из & в результате удаления всех ребер этих пар, будет связным факторграфом графа Ог .

Благодаря этому результату был найден максимальный род полных К- дольных, диаметрально-критических и других классов графов. В работе Н.А.Островерхого и В.А.Кузьменко [II] с помощью теоремы А [19] был найден максимальный род декартового, сильного декартового и лексикографического произведений двух графов, а в работе Н.А.Островерхого [ю] - найден максимальный род некоторых произвольных графов.

Интересно отметить, что практически все результаты, полученные к 1973 году в области максимального рода графов, можно более или менее просто вывести из теоремы А [19] . Это относится к результатам работ [Ю, 11,19,41,42,45,46], также к результату работы Э.Б.Яворского [23], в которой получен новый критерий

1-компонентной 2-клеточной вложимости графа в ориентируемое

2-многообразие.

В 1974 году была опубликована работа Н.П.Хоменко и Н.А.Островерхого [18], в которой теорема А [19] была, в частности, применена к решению вопроса о существовании относительных 2-клеточных вложений. В том же году была опубликована статья Дж.Закса [61], посвященная нахождению максимального рода декартового произведения двух графов. Результаты последней работы перекрывались результатами более ранней работы [п] .

В 1975 году вышли в свет две работы А.Г.Вентре 152,53] , содержащие некоторые результаты о максимальном роде графов, блоки которых сверху вложимы и доказательство сверху вложимости графа Грецша. Эти результаты довольно легко выводятся из теоремы А [19].

В 1976 году была опубликована еще одна работа А.Г.Вентре [54] о сверху вложимости графов, блоки которых сверху вложимы, которая, однако, не содержала существенно новых результатов. В том же году Н.Х.Ксуонг опубликовал две работы [57,58] в которых (без ссылки на работу [19] ) была приведена теорема, по существу совпадающая с теоремой А [19], а также некоторые ее следствия.

В 1977 году вышла в свет работа Н.П.Хоменко и А.Д.Глухова [16] , посвященная исследованию сверху вложимых графов, и работа А.Д.Глухова [2] , в которой были построены контрпримеры к некоторым предположениям, высказанным в работе [473, в частности построен пример 3-связного не сверху вложимого графа. В том же году Ф.Жагер, Н.Х.Ксуонг и Ш.Пейан опубликовали работу 133], в которой анонсировали результаты о максимальном роде одного класса кубических графов и о сверху вложимости циклически 4-реберно связных графов, а А.Г.Вентре опубликовал новую работу Г55] об аддитивности максимального рода графов, в которой несколько обобщил результаты, полученные им в работах [52-54].

В 1978 году была опубликована работа Э.В.Яворского [24], содержащая утверждение об однокомпонентной 2-клеточной вложи-мости графов с четным цикломатическим числом и с диаметром не больше двух. К сожалению, доказательство этого утверждения было некорректным из-за применения неверной леммы. В том же году вышли в свет две статьи, содержащие изложение докладов на конференции в Орсее в 1976 году - работа А.Буше [26] , в которой был построен класс 3-связных не сверху вложимых графов и работа Р.Д.Рингайзена [48], посвященная аддитивности максимального рода графов. Результаты последней нашли более полное отражение в работе К.Х.Литтла и Р.Д.Рингайзена [37], которая обобщала также основные результаты работ [53-55]. В 1978 году были также опубликованы работа М.Юнгермана [34], в которой доказывался критерий сверху вложимости связного графа, полученный еще в 1973 году в работе [19], и работа Р.Д.Рингайзена [49] о графах б , удовлетворяющих условию (£)

В 1979 году вышел в свет целый ряд работ, посвященных максимальному роду графов. В работе Ш.Пейана и Н.Х.Ксуонга [44] были доказаны результаты, анонсированные в работе [33], а в работе этих же авторов вместе с Ф.Жагером [32] были найдены два новых класса сверху вложимых графов. Н.Х.Ксуонг в двух своих работах [59] и [60] дал развернутое изложение результатов, анонсированных им ранее в статьях [57] и [58] (отметим, что основные из этих результатов были получены еще в работе [19)). В статье Ф.Жагера, Ш.Пейана и Н.Х.Ксуонга [31] была найдена новая формула для максимального рода кубических графов, а в статье [43] последних двух авторов были описаны все графы для которых 1 . А.Г.Вентре в своей работе

56] получил оценку для максимального рода графа, для которого известны максимальные роды его подграфов определенного вида. В работе Лю Янпея [38] для нахождения максимального рода графа применялся подход, развитый еще в работе [21], основанный на изучении эйлеровых циклов в графе Ос/ и получены ранее известные результаты: найдены ^м(Кп) и (Кт,п) , а в работе М.Е.Арагно [25] доказана сверху вложимость одного класса кубических гамильтоновых графов. Р.Д.Рингайзен в 1979 году опубликовал обзорную статью [50], посвященную максимальному роду графов. В этой статье получили отражение все существенные результаты зарубежных ученых в области максимального рода, однако, к сожалению, совершенно не были упомянуты важные результаты советских математиков.

В 1980 году была опубликована работа Н.П.Хоменко и А.Д.Глу-хова [17] , в которой наряду с развитым в работах [21] и [19] подходом, основанном на хордовом натягивании, был применен также новый подход к исследованию максимального рода графов. Это позволило авторам найти новую формулу для максимального рода произвольного связного графа и получить эффективную характери-зацию графов с данным максимальным родом. В том же году вышла в свет статья А.Д.Глухова [3], в которой были изучены свойства, введенных в работе [17] . хордово критических графов.

В 1981 году были опубликованы две статьи Л.Небески [39] и [40] . В первой из них показано, что всякий связный и локально связный граф сверху вложимый. Основным результатом второй работы является теорема о максимальном роде графов, эквивалентная теореме 1.2 настоящей диссертации. Эта теорема впервые была доказана в работе [17]. В том же году была опубликована работа В.Г.Лещенко [8], в которой доказана теорема об одноком-понентной 2-клеточной вложимости графов с четным цикломатичес-ким числом и диаметром не больше двух. Кроме того, в 1981 году была опубликована работа А.Д.Глухова [5], в которой была развита (примененная уже в работе [17] ) техника Л- разложений и построен полиномиальный алгоритм нахождения максимального рода произвольного связного графа. В работе [6] А.Д.Глухова эта же техника была применена к исследованию максимального рода плоских графов.

Настоящая диссертация посвящена исследованию максимального рода графов и содержит результаты, опубликованные в работах [2-6, 16,17] . Диссертация содержит две главы, каждая из которых разбита на четыре параграфа.

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

В § 1.1. вводится ряд основных понятий (хордовость, А- разложения и др.) и доказываются утверждения, позволяющие применять 1- разложения к исследованию максимального рода графов. Главными результатами этого параграфа являются теорема 1.1. о существовании приведенных А-разложений для любого связного графа, теорема 1.2, дающая новую формулу для максимального рода графа, и теорема 1.4, которая дает эффективную харак-теризацию графов с данным максимальным родом.

В § 1.2 изучен весьма важный, с точки зрения максимального рода, класс 0-хордовых графов или графов, вкладывающихся 1-компонентно 2-клеточно в ориентируемое 2-многообразие. Здесь доказано утверждение (теорема 1.5) о 0-хордовых факторграфах данного связного графа, позволяющее свести задачу нахождения максимального рода данного графа к построению некоторой цепочки его 0-хордовых факторграфов, а также утверждения о строении максимальных 0-хордовых факторграфов связного графа (предложения 1.1 и 1.2 и их следствия). Кроме того, получен новый критерий 0-хордовости связного графа в терминах существования I - фактора в графе базиса циклов данного графа (теорема 1.6).

В § 1.3 содержит некоторые результаты о хордово критических графах, которые наряду с 0-хордовыми графами играют существенную роль в теории максимального рода графов. Здесь установлен критерий хордовой критичности графа (теорема 1.7), а также найдены ряд необходимых и достаточных условий хордовой критичности.

В § 1.4 рассмотрен вопрос о существенности ребер связного графа относительно максимального рода при удалении из графа или стягивании этих ребер. С помощью Л- разложений описаны существенные в целом реберные подпространства (предложения 1.9 и 1.10) и расположение /*- несущественных ребер (теоремы 1.9 и 1.10) в связном графе. Найдены также достаточные условия

Ц"к- несущественности ребер по стягиванию в связном графе (предложения 1.12 и 1.13).

Вторая глава посвящена нахождению максимального рода и построению максимальных 2-клеточных вложений графов. Изложение при этом существенно опирается на результаты, полученные в первой главе настоящей работы.

В § 2.1 исследуется связь между циклически нечетной реберной связностью (это понятие, обобщающее циклическую реберную связность, было введено в § 1.3) и максимальным родом графа. Показано, что любой циклически нечетно 4-реберно связный граф сверху вложимый (теорема 2.1) и найдена нижняя оценка для максимального рода циклически нечетно 3-реберно связных графов. Кроме того, доказано, что случайный граф 0Пгр, р ~ inn + ^W , tim СО(п) =z сэо , сверху вложимый с вероятностью f-o(1').

В § 2.2 доказано утверждение, позволяющее свести проверку 0-хордовости 2-реберно связного плоского графа G- к проверке критичности графа J (G-jмежевания 2-клеток вложения f графа G- в сферу б"0 (теорема 2.4). При этом использован полученный в § 1.2 критерий 0-хордовости связного графа. На основе этого утверждения построен алгоритм полиномиальной временной сложности для нахождения максимального рода любого связного плоского графа (алгоритм I). Разработан также весьма эффективный алгоритм нахождения максимального рода для одного класса плоских графов -так называемых К VP -графов или параллельно-последовательных графов (алгоритм 2).

В § 2.3 построен алгоритм полиномиальной временной сложности для нахождения максимального рода произвольного связного графа (алгоритм 4). Для обоснования этого алгоритма доказан ряд вспомогательных утверждений о введенных здесь однородных Л-разложениях (леммы 2.6 - 2.9). Идея алгоритма состоит в построении такой цепочки Т- f0c •••4=1 Fm 0 - хордовых факторгра-фов связного графа £ , что , ot<(Fi\F/J = 2, i=*f(t)m, m^M(Q).

При этом находятся как однородные Я- разложения, так и £-разложения (т.е. представления в виде фактордерева с добавленными к нему парами смежных ребер) каждого из графов Fe , i- o(f)m . Теорема 2.5 обосновывает правильность и полиноми-альность алгоритма 4.

§ 2.4 посвящен применению полученных результатов. Здесь описаны три полиномиальных алгоритма (алгоритмы 5,6,7), основанных на алгоритме 4. Алгоритм 5 строит максимальное 2-клеточное вложение произвольного связного графа Q- в ориентируемое

2-многообразие, а алгоритм 6 строит 2-клеточные вложения связного графа в в ориентируемые 2-многообразия родов У = Уо , если задано 2-клеточное вложение этого графа в 2-многообразие . Оба эти алгоритма задают соответствующие вложения в виде вращений. С помощью алгоритма 7 для кубических графов решается задача о нахождении в графе минимального (по числу элементов) множества вершин, после удаления которого получается граф без циклов (лес). Для случая произвольных графов эта задача, имеющая прикладное значение, является - трудной.

Основные результаты настоящей диссертации можно сформулировать следующим образом.

1. Разработана техника Х- разложений, позволившая получить ряд новых результатов в теории максимального рода графов.

2. Получена новая формула для максимального рода произвольного связного графа и дана эффективная характеризация графов с данным максимальным родом.

3. Исследованы 0-хордовые и хордово критические графы, играющие важную роль в теории максимального рода графов, а также изучен вопрос о существенности ребер связного графа при удалении или стягивании относительно максимального рода графов.

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

5. Решена задача нахождения максимального рода любого связного плоского графа путем сведения ее к задачам теории па-росочетаний.

6. С помощью техники 1 - разложений и хордового копредстав-ления (натягивания) графов разработаны алгоритмы полиномиальной временной сложности для нахождения максимального рода и построения максимальных 2-клеточных вложений в ориентируемые 2-много-образия произвольного связного графа.

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

Понятия и обозначения, используемые в настоящей диссертации, в основном взяты из работы [15] . Под графом как правило понимается топологический граф, т.е. конечный одномерный CW-комплекс , где ь- вершинное и реберное пространства графа G- соответственно. Буква (Л {U-ifU.' и т.д.) будет всегда обозначать ребро графа Q- , а буква V и т.д.) - реберное подпространство графа Q . Компонентами связности реберного подпространства V графа Q являются ребра этого графа; число этих ребер обозначается через pQ(U).

Автор благодарит своего научного руководителя старшего научного сотрудника Института математики АН УССР Николая Павловича Хоменко за помощь и постоянное внимание к работе.

1. Ахо А., Хопкрофт Дне., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979, - 536с.

2. Глухов А.Д. Опровержение предположений Рингайзена. В кн.: Теория графов. - Киев: Институт математики АН УССР, 1977, с.90-91.

3. Глухов А.Д. 0 хордово критических графах. В кн.: Некоторые топологические и комбинаторные свойства графов: Препринт 80.8. - Киев: Институт математики АН УССР, 1980,с. 24-27.

4. Глухов А.Д. Максимальный род случайного графа. В кн.: Свойства графов некоторых классов: Препринт 81.2. - Киев: Институт математики АН УССР, 1981, с. 20-22.

5. Глухов А.Д. К теории максимального рода графов. В кн.: Структура и топологические свойства графов: Препринт 81.28. - Киев: Институт математики АН УССР, 1981, с.15-29.

6. Глухов А.Д. 0 максимальном роде плоских графов. Укр. мат.журнал, 1982, 34, № I, с. 97-99.

7. Ивченко Г.И. 0 силе связности случайного графа. Теория вероятностей и ее применения, 1973, 18, № 2, с.417-425.

8. Лещенко В.Г. Однокомпонентное вложение графов одного класса. В кн.: Свойства графов некоторых классов: Препринт 81.2. - Киев: Институт математики АН УССР, 1981,с. 23-26.

9. Оре 0. Теория графов. М.: Наука, 1968, - 352с.

10. Островерхий М.0. Максимальний р1д пох1дних граф1в. Вкн.: у- перетворення граф1в. Ки1в: 1нститут математики АН УРСР, 1973, с.224-233.

11. Островерхий М.О., Кузьменко В.О. Максимальний р1д декартового, сильного декартового I лексикограф1чного добутк1в двох граф1в. В кн.: У- перетворення граф1в. - Ки1в: 1нститут математики АН УРСР, 1973, с.211-223.

12. Рингель Г. Теорема о раскраске карт. М.: Мир, 1977. - 256с.

13. Хоменко М.П. Метод У>- перетворень та деяк1 його засто-сування. В кн.: У- перетворення граф1в. - Ки1в: 1н-ститут математики АН УРСР, 1973, с.35-96.

14. Хоменко М.П. Про вкладення граф1в в 2-многовиди I про 1х структуру. В кн.: перетворення граф1в. - Ки1в: 1нститут математики АН УРСР, 1973, с.7-34.

15. Хоменко Н.П. У- преобразования, топология и алгебра графов. В кн.: Теория графов. - Киев: Институт математики АН УССР, 1977, с.5-45.

16. Хоменко Н.П., Глухов А.Д. О сверху вложимых графах. -В кн.: Теория графов. Киев: Институт математики АН УССР, 1977, с.85-89.

17. Хоменко Н.П., Глухов А.Д. Однокомпонентные 2-клеточные вложения и максимальный род графов. В кн.: Некоторые топологические и комбинаторные свойства графов: Препринт 80.8. - Киев: Институт математики АН УССР, 1980, с.5-23.

18. Хоменко Н.П., Островерхий Н.А. Максимальный род графов: Препринт 74.4. Киев: Институт математики АН УССР, 1974. - 16с.

19. Хоменко M.П., Островерхий М.О., Кузьменко В.О. Максималь-ний р1д граф1в. В кн.: У- перетворення граф1в. - Ки1в: 1нститут математики АН УРСР, 1973, с.180-210.

20. Хоменко Н.П., Шевченко Е.Н. KVP графы: Препринт 77.17. - Киев: Институт математики АН УССР, 1977. - 48с.

21. Хоменко Н.П., Яворский Э.В. У- преобразования графа представления: Препринт 70.7 Киев: Институт математики АН УССР, 1970. - 28с.

22. Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976. - 136с.

23. Яворский Е.Б. 0днокомпонентн1 укладення граф1в I У- перетворення. В кн.: У- перетворення граф1в. - Ки1в: 1нститут математики АН УРСР, 1973, с.97-102.

24. Яворский Э.Б. Представления ориентированных графов ипреобразования. В кн.: Теоретические и прикладные вопросы дифференциальных уравнений и алгебра. Киев: Нау-кова думка, 1978, с.247-250.

25. Aragno М.Е. Sulla superiore immergibilita di certi grafi cubici hamiltoniani. Rend. 1st. Lombardo Accad. Sci. lett., 1979, A115, P* 416-425.

26. Bouchet A. Genre maximum d'un A-graphe. In.: Problèmes combinatores et theorie des graphes. (Colloq. Internat. CNRS Univ. Orsay, Orsay, 1976). - Paris, 1973, p. 57-60.

27. Duke R,A. The genus, regional number and Betti number of a graph. Ganad. J. Math., 1966, 18., N 4, p. 817-822.

28. Edmonds J. A combinatorial representation for polyhedral surfaces. Noteces. Amer. Math. Soc., 1960, 7, p* 646.

29. Edmonds J. Path, trees and flowers. Ganad. J. Math., 1965, 17, IT 5, P. 449-467.

30. Heawood P.J. Map colour theorem, Quart. J. Math., 1890, 24, p. 332-338.

31. Jaeger P., Payan G., Xuong N.H. Maximum genus and trees. ■ Math. Appl. Informât., Rapp. Rech., 1979, N 174. 12 p.

32. Jaeger P., Payan C., Xuong N.H. A class of upper embed-dable graphs. J. Graph Theory, 1979, 1, N 4, p. 387391.

33. Jaeger P., Xuong N.H., Payan C. Genre maximal et connectivité d'un graphe. G.R. Acad. Sci., 1977, À 285, H 3, P. 337-339.

34. Jungerman M. A characterization of upper embeddable graphs. Trans. Amer. Math. Soc., 1978, 241, p. 401406.35* Krishnamoorthy M.S., Deo N. Node-deletion NP-complete problems. SIAM J. Comput., 1979, 8, N 4, p. 619625.

35. Kundu S. Bounds on the number of disjoint spanning tress.-J. Combin. Theory, 1974, B1N 2, p. 199-203.

36. Little G.H., Rimgeisen R.D. An additivity theorem for maximum genus of a graph. Discrete Math. , 1978, 21, N 1, p. 69-74.

37. Liu Yanpei. The maximum orientable genus of a graph. -Sci. Sinica, 1979. Special Issue 2 on Math., p. 41-55.

38. Nebesky L. EVery connected, locally connected graph is upper embeddable. J. Graph. Theory, 1981, N 2, p. 205-207.

39. Nebesky L. A new characterization of the maximum genus of a graph. Czechoslovak Math. J., 1981, ¿1, N 4, p. 604-613.

40. Nordhaus E.A., Stewart B.M., Ringeisen R.D., White A.T. A Kuratowski-type theorem for the maximum genus of a graph. -Notices Amer. Math., Soc., 1971» 18, N 1, p. 91.

41. Nordhaus E.A., Stewart B.M., White A.T. On the maximum genus of a graph. J. Combin. Theory, 1971» B11, N 3, p. 258-267.

42. Payan 0., Xuong N.H. Characterization des graphes d'intervalle d'immersion 1. Math. Appl. Informat., Rapp., Rech., 1979, N 173. - 23 p.

43. Payan C., Xuong N.H. Upper embeddability and connectivity of graph. Discrete Math., 1979» 2IT 1, p. 7180.

44. Ringeisen R.D. Graphs of given genus and arbitrarily large maximum genus. Notices Amer. Math. Soc., 1972, 12, N 1, p. 77.

45. Ringeisen R.D. Determination all compact oriental 2-manifolds upon which K has 2-cell imbeddings. J. Combin.m,iiTheory, 1971, B12, N 2, p. 101-1C4.

46. Ringeisen R.D. Upper and lower embeddable graphs. Lect.Motes. Math., 1972, 303, p. 261-268.

47. Ringeisen R.D. On additivity in maximum genus. In: Problèmes combinatores et theorie des graphes. (Colloq. Internat. CNRS Univ. Orsay, Orsay, 1976). - Paris, 1978,p. 345-347.

48. Ringeisen R.D. On graphs of embedding range one. Lect. Notes Math., 1978, 642, p. 454-464.

49. Ringeisen R.D. Survay of results on the maximum genus of a graph. J. Graph. Theory, 1979, 2, N 1, p. 1-13.

50. Tutte W.T. The factorizations of linear graphs. J. London Math. Soc., 1947, 22, p.107-111.

51. Ventre A.G. Sull1 immergibilita inferiore e superiore del grafo di Gritzch. Riv. Math. Univ. Parma, 1975, 1, p. 227-231.

52. Ventre A.G. Sulla superiore immergibilita di grafi constituiti da blocchi superiormente immergibili. Boll. Unione Math. Ital., 1975, 12, N 5, p. 388-397.

53. Ventre JUG. On the maximum genus of some graphs with upper imbeddable subgraphs. Monatsh. Math., 1979, 86, N 4,p. 327-331.

54. Xuong N.H. Sur les immersions d'un graphe dans les surfaces orientables. G.R. Acad. Sci., 1976, A283, N 10, p. 745-747.

55. Xuong N.H. Sur quelques classes de graphes possédant despropriétés topologiques remarquables. C.R. Acad. Sci. , 1976, A283, N 11, p. 813-816.

56. Xuong N.H. How to determine the maximum genus of a graph. -J. Gombin. Theory, 1979, B26, N 2, p. 217-225.

57. Xuong N.H. Upper embeddable graphs and related topics. J. Combin. Theory, 1979, B26, N 2, p. 226-232.

58. Zaks J. The maximum genus of Cartesian production of graphs. Canad. J. Math., 1974, 26, N 5, p. 1025-1035.- 91