Том 11, серия 2, номер 2, 2004 г., Стр. 25-44
УДК 519.17
А. А. Добрынин, Л. С. Мельников
Индекс Винера для графов и их реберных графов
Аннотация:
Рассматривается индекс Винера – инвариант связного неориентированного графа, равный сумме расстояний между всеми парами его вершин. Показано, что разность индексов Винера графа и его реберного графа может принимать любое целое значение$t$ . В частности, дан положительный ответ на открытый вопрос о существовании графов с произвольным цикломатическим числом$\lambda>3$ , для которых$t=0$ . Доказательство проводится построением соответствующих графов с дополнительными требованиями на двудольность и внешнепланарность.
Добрынин А. А. 1
Мельников Л. С. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: dobr@math.nsc.ru, omeln@math.nsc.ru
Статья поступила 7 июля 2004 г.
