This article is cited in 7 papers

Sufficient conditions for the existence of a graph with a given variety of balls

K. L. Rychkov

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

Abstract: It is proved that for each positive integer $d$ and each collection of integers $\overline\tau=(\tau_0,\tau_1,\dots,\tau_d)$ such that $\tau_0\geqslant\tau_1\geqslant\dots\geqslant\tau_d=1$ and $\tau_{d-1}\geqslant d^2+1$, there exists a graph of diameter $d$ whose variety vector of the balls is equal to $\overline\tau$; if $d\geqslant 3$ then there is no graph of diameter $d$ whose variety vector of balls $(\tau_0,\tau_1,\dots,\tau_d)$ satisfies the condition $\tau_0=\tau_1=\dots=\tau_{d-1}\leqslant2d-1$.

UDC: 519.176

Received: 27.10.2005

 English version: Journal of Applied and Industrial Mathematics, 2007, 1:3, 380–385

Bibliographic databases:

• 
• 
•