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

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи

БЕЛЯЕВСКИй Владимир Васильевич

СПЕЦИАЛЬНЫЕ МАТРИЦЫ ГРАФОВ Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Минск 1992

Работа выполнена в Белорусском государственном университете.

Научный руководитель - кандидат физико-математических наук,

профессор Лепешинский Николай Андреевич.

Официальные оппоненты - доктор физико-математических наук,

профессор Тышкевич Регина Иосифовна; - кандидат физико-математических наук Тюрин Владимир Львович.

Ведущая организация - Институт математики СО Российской . АН.

Защита состоится " ю " шурела._1992,г.

в часов на заседании специализированного совета К 006.19.01 по присуждению ученой степени кандидата физико-математических наук в Институте математики АН Беларуси по адресу :

220072, г. Минск, ул. Сурганова, 11

С. диссертацией можно ознакомиться в библиотеке Института математики АН Беларуси.

Автореферат разослан " ю " дкхрпцх_1992 г.

Ученый секретарь специализированного совета

кандидат физ.-мат. наук -ЯЯс— А. И. Астровский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

'"" ^£1У5:№Ность_проблемы^ Известно немало практических задач и ■еоретических проблем в математике, физике, химии, которые сводят-:я к изучению спектра матрицы специального вида. В теории графов »та проблематика активно изучается после появления работ Л. М. Лих--енбаума (1956), Л.Коллаца и У. Синоговица (1957). Одним из стиму-!ов ее развития является, в частности, постоянное совершенствова-ше и математизация теории молекулярных орбиталей в химии.

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

юзволили сформулировать основные вопросы этого раздела математи-

* )

си. Как отметил Д.Цветкович , среди них такие, как "...конструирование коспектральных графов, поведение собственных значений при треобразованиях графа, спектр и реконструкция графов...".

Значительный вклад в развитие спектральной теории графов внесли Л.Бабаи, Н.Бигс, Р. Боуз, Ф. Буссемакер, С. Годсил, И.Гутман, М. Дуб, Ю. Зайдель, X. Захс, Р.Камерон, Ю.Ван Линт, А. Мовиовиц, В. Хе~ мерс, Б. Татт, Д. Хигман, А. Хофман, Д. Цаеткович, А. Швенк и другие.

Большинство работ этих авторов саязано с рассмотрением характеристического многочлена графа (т.е. характеристического многочлена его матрицы смежности), который является важным инвариантом для описания и исследования структурных свойств графов. Построение Л.Коллацем и У. Синоговицем в 1957 году неизоморфных коспектральных графов привело к изучению характеристических многочленов других матриц, однозначно задающих граф. К таким матрицам относятся матрицы Зайделя, Кирхгофа и другие. Естественно возникает вопрос о взаимосвязях различных спектров графов. Для его решения перспективным является исследование •обобщенной матрицы смежности, введенной Х.Юбо (1975) под другим названием и которую использовали' для исследований другие авторы.

Важность конструирования коспектральных графов раскрыта

ф I

Cvetkovic D. Some possible directions In further investigations of graph spectra // Algebraic Methods in Graph Theory. - Vol I. Colloq. Math. Soc. - Amsterdam, 1981. - P. 47-67.

ft )

Д. Цветковичем, М. Дубом, X. Захсом . В контексте этого обоснована еше более значительный интерес представляют вопросы построения не изоморфных графов с одинаковыми обобщенными характеристические; многочленами (такие графы будем называть бикоспектральными >. В литературе этот вопрос специально не рассматривался, хотя некоторьк известные .классы графов, как оказалось, таковыми являются. Сильн< регулярные графы (Р. Боуз, 1963), полярные графы (Р. И. Тышкевич, 1980), а также операции прямой суммы и полного произведения гра фов, введенные А.А.Зыковым, являются перспективными объектами для построения семейств бикоспектральных графов.

Известная гипотеза Улама (точнее, гипотеза Келли-Улама) сост< ит в том, что граф с числом вершин п>3 может быть восстановлен по набору, состоящему из п его (п-1 )-вершинных порожденных подграфов полученных из исходного удалением каждой его вершийы. Эта гипотеза, как'известно, подтверждена только для отдельных классов графо] и тесно связана с одной из центральных проблем теории графов -изоморфизме. Сложность вопроса, поставленного в гипотезе Келли Улама привела к рассмотрению ее спектрального варианта (И.Гутман, Д.Цветкович, 1975, А.Швенк, 1979) - по набору характеристических многочленов (п-1 )-вершнных порожденных подграфов восстановить характеристический многочлен графа, который в настоящее время также не подтверзден в общем случае.- Б связи с этим, определенный интерес представляет спектральный вариант гипотезы, сформулированный в терминах обобщенных характеристических многочленов.

Цв£Ё5?_Е§521Ь1 является выявление взаимосвязей между обобщенны ми характеристическими многочленами и модифицированными (в том чи еле, известными) характеристическими многочленами графа; конструи рование бикоспектрапьных графов; реконструкция обобщенного характеристического многочлена n-вершинного граф- по набору обобщенных характеристических многочленов его (п-1>-вершиннык порожденных подграфов.

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

--i---

*г1вегкович Д.,'Дуб М. , Захс X. Спектры графов. Теория и применени //Киев: Наукоэа думка, 1984. Пер. с англ.: D. Cvetkovic, M.Daob H.Sachs. Spectra of Graph. Theory and Application. Berlin, 1980.

- положительно рекен один из спектральных аналогов гипотезы .{елли-Улама, сформулированный а терминах обоблданных характеристических многочленов n-вершинного графа и < h-1 )-вершинных г^ррожден-* шх подграфов.

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

П^бликацин^ По теме диссертации опубликовано 4 работы.

Ап£обация_£§боты^ Результаты диссертации докладывались на IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989), научной конференции "Актуальные проблемы социально-гуманитарных и естественных наук", посвященной 70-летию университета (Минск, 1991), городском семинаре по теории графов под рук. Р.И.Тыяхевич (Минск, 1986-1990 ), семинаре лаборатории математической кибернетики ИМ АН Беларуси (Минск, 1991), семинаре "Кетоды и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1991).

Об;ьем_|>аботы^ Диссертация изложена на 111 страницах и состоит из введения, трех глав, списка цитируемой литературы, содержащего 94 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

ГЛАБА_Г посвящена исследованию обобщенного характеристического многочлена графа и носит вспомогательный характер. В первом параграфе даны необходимые.определения и понятия, отличные от общепринятых. Среди них '

Определение 1.1. Пусть вершины графа G занумерованы числами 1,2,...,п. Тогда матрица A(x,y,z> размера пхп с элементами если

если 1 и j смежны, если i и J несмежны.

ai.

ai, Г2'

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

Определение 1.2. Обобщенным характеристическим многочленом графа в называется определитель его обобщенной матрицы смежности ЬеЬАд( х,у,г ).

При некоторых фиксированных значениях переменных в определениях 1.1 и 1.2 рассматриваемые объекты ("модифицированные" матрицы смежности и "модифицированные" характеристические многочлены! изучались ранее. В частности, А(0,1,0) - обычная матрица смежности, СеЪА<х,-1,0)=Р(х) -обычный характеристический многочлен графа.

Установлено, что обобщенный характеристический многочлен, кап инвариант графа не слабее любого модифицированного характеристического многочлена. Приводится таблица коэффициентов характеристических многочленов коспектральных деревьев с чийлом вершин дс десяти й коэффициентов характеристических многочленов дополнены* этих деревьев,' на основании которой делается вывод, что обобщенны? характеристический многочлен является полным инвариантом для деревьев с числом вершин по крайней мере до десяти (утверждение 1.1).

Во Етором параграфе исследуются вопросы вычисления обобщенного характеристического многочлена графа. Приведены формулы для вычисления характеристических многочленов, таблица коэффициентов обобщенных характеристических многочленов и факторизованные по переменной х над полем рациональных чисел'значения обобщенных характеристических многочленов всех графов с числом вершин до пяти. Доказана теорема, устанавливающая взаимосвязь ' между обобщенным и двумя модифицированными характеристическими многочленами графа.

Теорема 2.2. Для любого п-вершинного графа б с обобщенной матрицей смежности А(х+а^,у,2 ), у*з имеет место

( у-2 г уг0-гу~ (х+й.Ъ )( ул -я. )+уи1 -гу. -------г—---¿-.ЮеЪАС-----А----¿--1---------1>У1,*1> ~

где У1,г1,у2

уг.-гу. (х+<31Ь)(у2-г2 )+у22-2у2

-------^еЬАС------------------------У2'г2)

<У2"*г2 у-2 .1

- константы, такие, что У^ъ^г у1г2"!у2г:1

Здесь A(x+d1t>y,a)=A(x,/>z kd1>t, где )- пхп-матрица,

о которой k~ символ Кронекера, dj- степень вершины i, t- неза-йисимая переменная. ■ '

В частном случае, при y1=z2=-l, у^г^О, имеет место результат, доказанный А.Kau*'. Теорема 2.2 имеет ряд важных применений. Первое из них отмечено в следствии 2.1. Второе заключается в возможности представления произвольного модифицированного характерна стического многочлена двумя заданными модифицированными характеристическими многочленами. Эту возможность иллюстрируют, например, следствия 2.2-2.5 для наиболее распостраненных характеристических многочленов графов. Теорема 2.2 также широко используется в аналитических преобразованиях а глазах II, III.

Третий параграф посвящен исследованию обобщенных характеристических многочленов регулярных и сильно регулярных графов. Следующая теорема устанавливает взаимосвязь между обобщенным и модифицированным характеристическим многочленом регулярного графа.

Теорема 3.1. Для п-вершинного регулярного степени к графа а с обобщенной матрицей смежности A(x,y,z), y*z имеет место

DetA( X,y,2 >=----Ff---Trri?TrT---r^rr7--TDetAC---ff^T"---.У0'а0

где f <y.z )=<y-s >/(yjj-ZQ а Уд»^- константы, такие, что у^*zq.

Доказанный А.Кац результат относится к случаю yQ=-l,zg=0.

Возможные применения теоремы 3.1 проиллюстрированы следствиями 3.1-3.2, устанавливавшими соотношения между различными спектрами регулярного графа. Результат следствия 3.1 известен и первоначально доказан X. Захсом**5 более сложным путем (см. также-теорему 2.6 монографии ).

На основании простейших свойств 3.1-3.3 сильно регулярных —_ . . Кац А.О. Об одном классе полиномиальных инвариантов графа //

•Латв. мат. ежегодник. -19S0. - Н 3. - С. 137-146. >м<)

Sachs Н. Beziehcinren zwischen den in einem Graphen enthalten kreisen und seinem charakteristischen Polynom // Publ. Math. -December 1964. - H. 11. - S. 119-134.

"^^Цветкович Д. , Дуб M. , Захс X. Спектры графов. Теория и применение. - Киев: Наукова думка, 1984. - С. 58.

графов установлены рекуррентные формулы для элементов 1-ой степен» обобщенной матрицы смежности через элементы 1-1 степени это{ матрицы (лемма 3.1). Доказана

Теорема 3.3. Для сильно регулярного графа с с параметрам!

Р £

СеЪА( %,у, г )=( х-г+кС у-г )+пг )(х-г+г(у-г )) ( х-г+э! у-г ) где т и е - кратности второго и третьего собственных значений г и, э (к<г<с) характеристического многочлена графа б.

Варьируя значениями переменных х,у,и в модифицированной матрице смежности сильно регулярного графа этой матрице можно придат; дополнительное "хорошее" свойство. Так, например, модифицировании; матрицы смежности рассматриваемого графа А( х,< -л+к-г >г/( -к-г ),г) 1 А( х, (-п+к-з/(к-е), в) при любых и, имеют ровно два различны собственных значения. Этот прием используется при' доказательств* теоремы"5.2. В следствии 3.5(3.6) отражены наборыпеременных когд; модифицированная матрица смежности сильно регулярного графа явля еТся ортогональной (идемпотентной).

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

В главе II исследуются вопросы построения так называемы бйкоспектральных графоз, т.е. графов с совпадающими обобщенным характеристическими многочленами. Получены бесконечные серии бико спектральных градов при применении как известных графовых бинарны операций, таких как прямая сумма, полное произведение, полярно соединение, так и новых унарных операций; таких как двудолизация поляризация графа. Основная идея при построении бикоспектралькь графов заключается в использовании в качестве операндов графовь операций бйкоспектральных графов меньшей размерности.

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

Рассмотрены полные и дополнения к полным графам (утверждет 4.1, 4.3), граф приема гостей и его дополнение (утверждение 4.Е простой цикл ¡(утверждение 4.6), простой путь (утверждение 4Л

Важную роль играют ут ерждения 4.2 и 4.7, названные соответственно принципом двойственности и обобщением теоремы Ф.Кларка.

Утверждение 4.2 (принцип двойственности). Пусть DetA„(x,y,3),

- обобщенный характеристический многочлен графа G. Тогда

DetАр;( х, у, з )=DetA_( х,у, z ) -обобщенный характеристический многочлен ^ . ь

дополнения к графу G.

Утверждение 4.7 Пусть G - граф с веркинаии, занумерованными числами 1,2,...,п, G ^ - подграф, получзнный из графа G удалением i-ой вершины и инцидентных ей ребер. Тогда

Det\G<x,y,2)=-j:i2iDetAG (x,y,z).

В утверждении 4.9 установлены зависимости, выршгакядае обобщенный характеристический многочлен прямой суммы "и полного произведения графа G с m-вершинным полным графом К и его дополнением icm через обобщенный характеристический многочлен графа G, а в утверэденииг4.10 - прямой суммы и полного произведения произвольных двух графов через характеристические многочлены этих графов и их дополнений.

Далее вводятся новые унарные операции над графами - двудоли-зация D(G) и поляризация р(G) графа G я их разновидности.

Для определенности, пусть вершины G занумерованы числами 1,2,...,п. Тогда графы D(G) и P(G> имеют 2п вершин, занумерованный

числами 1,2,. . . ,2п. Две вершины i и j С 1=1,2,. . . ,п, j=n+l,n+2,------

2п) графа D(G> смежны тогда и только тогд&, когда вершины i и j-n графа G смежны. Граф P(G) кроме ребер графа D(G) содержит дополнительно ребра, соединяющие все веряины I и j при i,j<n, inj.

Легко заметить, что D(G) -двудольный, a P(G) -полярный графы.

Утверждение 4.11 выражает обобщенный характеристический многочлен двудолизации графа G в виде произведения обобщенного и модифицированного характеристических многочленов графа G, а .утверждение 4.12 - обобщенный характеристический многочлен поляризации сильно регулярного графа через обобщенный характеристический многочлен графа-операнда.

Наконец, утверждение 4.13 позволяет свести вычислен» обобщенного характеристического многочлена полярного соединения (Ge>Km) к вычислению определителя преобразованной обобщенной матрицы смежности х, у, 2 ),

Результаты, параграфов 1-4 используется в главе_11 при постро-

?

ении серий бикоспектральных графов. Теорема 5.1 содержит 15 эквивалентных высказываний о бикоспектральных графах. Проведви вычислительный эксперимент, на основе которого сформулировано утверждение 5.1 о существовании ро ю двадцати пар бикоспектральных графов с числом вершин до семи, все эти графы являются семивершинниками.

Теорема 5.2. Для любого п>7 существуют пары бикоспектральных тгвершинньгх графов.

Пусть G - сильно регулярный граф с множеством вершин v(G). Оказывается, что обобщенный характеристический многочлен подграфа G^ графа G, порожденного множеством вершин V(G^)nV(G> однозначно определяется обобщенным характеристическим многочленом подграфа в^ графа G, порожденного множеством вершин V<Go)=V(G)\V<G^). Взаимосвязь обобщенных характеристических многочленов графов G^ и G2 дается в виде теоремы 5.3,

При доказательстве теоремы 5.3 использован факт, что при некоторых значениях переменных в модифицированной матрице сильно регулярного графа эта матрица имеет ровно два собственных значения Это дает возможность применения известной теоремы Хемерса .

Из теоремы Б.З получен ряд следствий 5.2-5.7, которые можно применить при построении пар бикоспектральных графов. Например, при удалении каждой вершины (каждой пары смежных вершин, каждой пары несмежных вершин) получаем классы графов, состоящие из п (кп/2, n( n-k-1)/2 ) бикоспектральных (возможно, изоморфных) графов. Приведен пример, иллюстрирующий применение теоремы 5.3 для построения восьмивершинных бикоспектральных графов из неизоморфных сильно регулярных гр&фов с параметрами 16,6,2,2.

Способы построения бикоспектральных графов, основание на результатах утверждений четвертого параграфа, сформулированы в следующем виде: ' •

Теорема 5.4. Пусть G и И - бикоспектральные графы, F -произвольный граф. Следующие графы попарно бикоспектрапьны :

G*F И Н^Г, G*F И HVF, GW И EVF, GW И HVF,

G©K И Н&К , • GffiK И Н©К , G®K И Н®К , (ЗФК И 0®К , П П П _П П П _п

D( в ) И D( Н ), D(G) И D(H), P(G) И Р(Н), Р( G) И Р(Н). — •

Haemers W. Н. Eigenvalue methods In algebraic graph theory // Thesis; Eindhoven, 1979 (Mat." Centr. Amsterdam, 1980). - P. 217.

Здесь - операци" прямой суммы графов; V - полного произведения; © - полярного соединения графов; о(р) - двудолизация графа Р(Р) - поляризация сильно регулярного графа г.

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

Глава_1Г1 посвящена изучению одного из спектральных аналогов известйой гипотезы Кйлли-Улама и состоит из двух параграфов.

В шестом параграфе рассмотрены свойства обобщенного характеристического многочлена ОеЪА(х,у,г> п-вершинного графа а и обобщенных характеристических многочленов БеЬА^Сх.у^) его (п-1 )-вер-шинных порожденных подграфов 1=1,2,...,п. Здесь ограничимся

рассмотрением случаев, когда граф (3 и его подграфы не являются полными или дополнениями к полным графам. Доказаны две леммы, накладывающие ограничения на коэффициенты 'модифицированных характеристических многоч.-енов графа в.

Лемма 6.1. Пусть А(х,у,г) - обобщенная патрица смежности графа й, СеЬА(0,у,2 СеЬЛ( х,1,0 jX•,;

СеЬАСх.ОД >=хп+Е^С)2ь^-Для коэффициентов рассматриваемых многочленов выполняются следующие равенства:

с

j=l,2,. . . ,п-1;

С0=Ь0;

здесь при ю<0 или ш>1.

Лемма 6.2. Пусть А<х,у,г ^ кхп_^укг,'_к - обобщен-

ный характеристический многочлен графа б. Тогда значения . . "п-^Е^о"^-^ к ' .И1.2»-• ■ не зависят от. структуры графа, постоянна при фиксированных значениях ,5 и п и выражаются формулами

зп__,=<-1 >-Н1(п'Т1>, .¡=0,1,... , п-1,

Э0 = (-1 )п_1<п-1

следующая теорема устанавливает соотношения между коэффициентами обобщенного характеристического многочлена п-вершинного графа <3 и обобщенных характеристических многочленов его <п-1)-вершинных

подграфов 1=1,2,...,п.

Теорема 6.1. Для обобщенного характеристического- многочлена ОеЬА( х,у, г ) п-вершинного графа в (б^К Дп_), п>3 и обобшенных харшстеристических многочленов ЮеЪА^х.у-.н) его (п-1 )-вершшных подграфов (1=1,2,...,п имеет место

ОеЬА(и,1,0 >+( -1 )П_1 йе^АС 1 —и,0,1 ) = Э""1*1'61^'1-".0.1 )Ое1А(и,1 ,0)+ОеЪА1(и,1,0)ОеЬА(1-и,0,1 ))

При доказательстве теоремы 6.1 использовались утверждение 4.9 теорема 2.2, лемма Боровских , техника преобразований определителей и обобщенных характеристических многочленов. Эта теорема играет важную роль для задачи, рассмотренной в следующем параграфе. Кроме того, соотношения в леммах 6.1 и 6.2 могут рассматриваться как необходимые условия для многочленов, которые являются соответствующими характеристическими многочленами графов.

Задача реконструкции обобщенного характеристического многочлена DetA(x,y,s) п-вершинного графа а по набору обобщенных характеристических многочленов йеЬАЛх,у,ъ') его п-вершинных порожденных подграфов <3^ 1=1,2,...,п рассмотрена в седьмом параграфе.

Исследованы четыре различных случая реконструкции обобщенного характеристического многочлена графа, в некоторых из них по дополнительной информации о структуре порожденного подграфа восстанавливается не только обобщенный характеристический многочлен ОеЬА^< х,у,%) графа а, но и сам граф а. Наиболее трудный для исследования случай 4 возникает, когда среди порожденных подграфов нет полных графов или дополнений к ним, степень (Зее1 удаляемой вершины 1 при получении из а не равна нулю или п-1, существуют хотя бы два графа Gi и для которых дее1*с!ее1. При доказательстве основного результата здесь используются теорема 6.1, обобщение теоремы Ф.Кларка (утверждение 4.7), свойства квадрата многочлена, зависимости между коэффициентами модифицированных характеристических многрчленов графа (лемма 6.1), выражение обобщенного

ф )

Колмыков В. А. Спектры графов IX (дифференцирование по ребру и по вершине). - Воронеж. - 1988. - 9 с. Рукопись предст. Воронеж, ун-том. Деп. в ВИНИТИ 3.06.88, Н5203-В88 Деп.

характеристического м огочлена графа fGVK^ ) через обобщенный

характеристический многочлен графа G (утверждение 4.9), техника преобразований обобщенных характеристических многочленов.

Основной результат главы III формулируется в виде теоремы 7.1 которая дает положительный ответ на вопрос Д. Цветковича о спектральном варианте гипотезы Келли-Улама, сформулированный в терминах обобщенных характеристических многочленов графов.

Теорема 7.1. Обобщенный характеристический многочлен п—нер— шинного графа G реконструируется по заданным обобщенным характеристическим многочленам его ( п-1)-вершинных порожденных подграфов G^ 1=1,2,. . . ,п.

При доказательстве теоремы 7.1 наиболее, акт„вно использовались два специально выбранных характеристических многочлена среди всех обощенных характеристических многочленов (п-1)-вершинных порожденных подграфов G^ графа G. Другие такие многочлены использованы лишь однажды при вычислении суммы всех многочленов. Таким образом, обобщенный характеристический многочлен нерегулярного графа реконструируется по сумме всех обобщенных характеристических многочленов его <п-1)-вериинных порозденных подграфов и двум специально выбранным из этих обобщенных характеристических многочленов (следствие 7.1), а в отдельных случаях для реконструкции достаточно информации о сумме, всех обобщенных характеристических многочленов порожденных подграфов и одному из этии характеристических многочленов.

В заключение параграфа сделано замечание о реконструкции n-вершинного графа G по набору его (п-1)-вершинных порожденных подграфов Gi»G2'"*"*Gn—"1 и известному значению обобщенного характеристического многочлена DetAß(к,у ) графа G. Контрпримером здесь является, в частности, одна из пар семиЬершинных бикоспектральиых графов. Способы получения бикоспектральных графов, описанные а пятом параграфе, позволяют легко получить контрпримеры для произвольного числа вершин п, п>7. '

Основные результаты диссертации опубликованы а следующих

работах:

1. Беляеоский В. В. , Бризгалова И.И. О характеристическом многочлене обобщенной матри. л смежности графа / Ред. журн. "Вестник Белорус, ун-та. Сер. 1, физ. , мат., мех." - Минск, 1984. -16 е.. ил. - Библиогр. 10 назв. - Леп. в БелНИШТИ 18.06.84, Н894Бе-84.

2. Беляевский В.В. О некоторых свойствах обобщенного характеристического многочлена графа // Яробл. вопросы автоматизации производства и обработки информации. - Минск: Университетское, 1987. - С. 243-246.

3. Беляевский В. В., Лепешинский H.A.. Викоепектральные графы // Методы и программы решения оптимизационных задач на графах и сетях. Ч. II. - Новосибирск, 1387. - С. 12-14.

4. Беляевский В.В. Об одном спектральном варианте гипотезы Келли-Улама // Актуальные проблемы социально-гуманитарных и естественных наук / Тез. докл. лаучн. конференции, поев. 70-летию университета. Минск, апрель 19Slr. - Минск, Вышэйшая школа, 1991. - С. 96-97.