RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., Ser. 1, 2001 Volume 8, Issue 3, Pages 73–80 (Mi da226)

On the isometric embedding of arbitrary graphs into a graph of a given diameter possessing the metric continuation property

V. A. Tashkinov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We prove that an arbitrary ordinary graph $G$ can be embedded as a generated subgraph into a graph $H$ of given diameter $d(H)=d\geqslant 2$ in which any two vertices lie on some diametral path. If the diameter $d(G)$ of $G$ is less than or equal to $d$, then the embedding can be achieved isometrically, that is, with preservation of the distances between the vertices in $G$.

UDC: 519.176

Received: 29.06.2001



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024