Спектр графа при реберном расширении

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Секция математики
УДК 517. 19
В. Б. Мнухин, М.В. Черноусое
СПЕКТР ГРАФА ПРИ РЕБЕРНОМ РАСШИРЕНИИ
Получены выражения для характеристического многочлена графа при операции реберного расширения. Как следствия, найдены новые семейства коспектральных графов и графов с целочисленным спектром.
Далее все графы предполагаются конечными, без петель и кратных ребер. Используемые обозначения стандартны, в частности, полный п-вершинный граф обозначается через Кп.
Пусть СиЯ — два графа. Рассмотрим операцию расширени ребер графа С графом Н (или, операцию реберного расширени), состоящую в том, что каждому ребру графа С ставится в соответствие копия графа Н, после чего обе вершины в С, инцидентные выбранному ребру, соединяются со всеми вершинами соответствующей копии Н. Обозначим полученный граф через ООН. Пусть А, В и О — соответственно матрицы смежности, инцидентности и степеней вершин графа С. Как обычно,
РО (Л) = det (А — Л1) обозначает. арактеристический многочлен графа С [!]•
Характеристический многочлен графа ООК был получен Д. Цветко-вичем [2] в 1975 году. В 1980 году первым из авторов данной работы был найден [3,4] характеристический многочлен графа О0Кп. Здесь эти результаты усиливаются для случая реберного расширения графа С произвольным графом Н. Ее основным результатом является следующая теорема.
Теорема. Пусть О — произвольный (п, т)-граф, а Н — произвольный s-peгyляpный граф на к вершинах. Тогда справедливо тождество
Р^Н (Л) = (Л — s)-nPmm (Л)det (Л (5 -Л)I + (Л — 5 + к) А + кО).
Напомним, что два неизоморфных графа с одинаковыми спектрами называются коспектрсшъными. Поиск семейств коспектральных графов является одной из классических проблем спектральной теории графов [1,5]. Следствием теоремы является характеризация одного из таких семейств.
Следствие 1. Пусть О — произвольный граф. Если графы ^ и Н кос-пектрачъны, то коспектрачъными будут и реберные расширения СОН и.
Известия ТРТУ
Специальный выпуск
Следствие 2. Если граф О регулярен степени г, то
Р (О& gt-Н (А) =
А -А — кг А- s + к
В частности, если г=к-5, то
Р& lt-о>-н (А) = (А-?) Рт (А)Ро (А-к)
В 1970 году Ф. Харари была поставлена задача описания графов, имеющих целочисленный спектр (условимся далее называть такие графы целыми).
Следствие 3. Пусть О — целый г-регулярный граф, а Н — целый 5-регулярный граф на г+5 вершинах. Тогда граф СОН является целым.
Следствие 3 позволяет конструировать новые целые графы из уже известных. В частности, если С — кубический целый граф, то для построения нового целого графа его достаточно реберно расширить, например, одним из двух 6-вершинных целых кубических графов.
Предположим теперь, что из графа СОН удалены все ребра, принадлежащие С. Обозначим полученный граф через С° Н. Заметим, что
°
нием, спектр которого исследовался в работах [1]-[3], [5], [6]. Усилением полученных в них результатов является следствие 4.
Следствие 4. Если Н — к-вершинный 5-регулярный граф, то
ЛИТЕРАТУРА
1. Цветков, ч ДэМз- Дуб Мз- Захс X. Спектры графов ф теори и приложени. Киев: Наукова Думкаи198т.
Ртн (А) = (А- ,?)~пРН-(А)а^(А (5 — А) I + кА + ко)
В частности, если й регулярен степени г, то
ро& gt-н (А) = [а- РН (А)
А — А — кг'- к
т. Cvetkovic DMx Spectra of graphsn: ЕогНгД by soHe unary operations. bbiPubls.
Inst. Math. nl 975и1 1ир. у7ф41. у. Мнух, н ВзБ. Спектры графов при некоторы. унарны. операци.. ьыНекоторые топологические и комбинаторные свойства графов. Киев: h нф мат. АН г ССри1980. С. у8ф44.
4. Мнух, н В?. п восстановлении многочленов графа. ыыг7 Internat. Wiss. б oil. ТН IlHenau. I1Hепаии 198тир. 87 490.
5. Cvetkovic DMa- DooB Ма- GXtmBn I% TorSEsev A. Recent Results in the Theory of Graph Spectra. Ы. ф^. и1988.
6x ЗЫпоДо Shoji. On the characteristic polynoHial of the аДЕйсепсу Hatrix of the sut^vision graph of a graph. bbiDiscrete Appl. Math. Hl980Hvol. тир. у49ф?51.
УДК 517. 4
A.A. Афонин
МОДЕЛИРОВАНИЕ ЗАДАЧИ ЛИНЕИНОИ СТАЦИОНАРНОЙ ФИЛЬТРАЦИИ СО СВОБОДНОЙ ГРАНИЦЕЙ. ПРОБЛЕМА СУЩЕСТВОВАНИЯ И ЕДИНСТВЕННОСТИ
S3=r,
Задача линейной стационарной фильтрации впервые строго поставлена и решена в работах [1,2] в случае прямоугольной области (дамбы) с использованием теории вариационных неравенств, причем доказано существование решения- вопрос единственности оставлен открытым. Поз-[]
ласти, причем решение получено как минимум семейства суперрешений.
В настоящей работе представлены математическая модель и конструктивное доказательство существования и единственности решения задачи для области общего вида.
Пусть дамба представляет собой ограниченную область
ЙС3(2), граница которой представляет собой совокуп-81=^ ность трех частей
дО = 51 и52 и53. Здесь 51 -дно дамбы, являющееся непроницаемым для жидкости- 52 — часть дО, находящаяся в контакте с атмосферой- 53 — часть д О, которая находИТСЯ в контакте с ВОдным резервуаром.
СТаВИТСЯ задача: найти область, А СЙ, которая является важной
частью О и функцию и, определенную в, А (и = и (х) — давление), такую, что
дА
д, А = ци11 ци г4, где Г1 С 51, Г1 — непроницаемая для жидкости часть д, А —

ПоказатьСвернуть
Заполнить форму текущей работой