Ball number

Ball number — шаровое число (графа).

By a family of solid balls in [math]\displaystyle{ \,R^{3} }[/math], we mean a family of balls no two of which penetrate each other. A chain is a finite sequence of solid balls [math]\displaystyle{ b_{1}, b_{2}, \ldots, b_{n} }[/math] in which each consecutive pair of balls is tangent. The two balls [math]\displaystyle{ \,b_{1}, b_{n} }[/math] are called the end balls of the chain.

Let [math]\displaystyle{ \,a_{1}, a_{2} }[/math] be two solid balls. If an end of a chain is tangent to [math]\displaystyle{ \,a_{1} }[/math], and the other end of the chain is tangent to [math]\displaystyle{ \,a_{2} }[/math], then the chain is said to connect [math]\displaystyle{ \,a_{1}, a_{2} }[/math]. Let [math]\displaystyle{ \,G = (V,E) }[/math] be a finite graph. Take a family of red solid balls [math]\displaystyle{ a_{i}, \; i \in V }[/math]. Connect each non-tangent pair [math]\displaystyle{ \,a_{i}, a_{j} }[/math] ([math]\displaystyle{ i,\;j \in E }[/math]) by a chain of blue solid balls so that no two distinct chains share a blue ball. Then we have a family [math]\displaystyle{ {\mathcal F} }[/math] consisting of solid balls [math]\displaystyle{ a_{i}, \; i \in V }[/math], and the solid balls making the chains. This family is called a representation of [math]\displaystyle{ \,G }[/math]. The ball number [math]\displaystyle{ \,b(G) }[/math] of [math]\displaystyle{ \,G }[/math] is the minimum number of balls necessary to make a representation of [math]\displaystyle{ \,G }[/math]. For example, [math]\displaystyle{ \,b(K_{6}) = 8 }[/math], [math]\displaystyle{ \,b(K_{7}) = 13 }[/math].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.