Том 8, серия 1, номер 3, 2001 г., Стр. 73-80

УДК 519.176
В. А. Ташкинов
Об изометрическом вложении произвольных графов в графы заданного диаметра, обладающие свойством продолжения метрики

Аннотация:
Доказывается, что произвольный обыкновенный граф $G$ можно вложить как порожденный подграф в граф $H$ заданного диаметра $d(H)=d\geqslant 2$, в котором любые две вершины лежат на некоторой диаметральной цепи. При этом если диаметр $d(G)$ графа $G$ не превосходит $d$, то вложение может быть осуществлено изометрически, т.е. с сохранением расстояний между вершинами в $G$.
Ил. 1, библиогр. 4.

Ташкинов В. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 29 июня 2001 г.