No label defined (Q4352333)

A graph \(G\) with vertex set \(\{v_1,\dots,v_n\}\) is called a closed sphere-of-influence graph (CSIG) if there are points \(P_1,\dots, P_n\) in the Euclidean plane and positive numbers \(r_1,\dots, r_n\) such that \(\text{dist}(P_i, P_j)\geq \max\{r_i, r_j\}\) for \(1\leq i<j\leq n\), and such that \(v_iv_j\in E(G)\) if and only if \(\text{dist}(P_i, P_j)\leq r_i+ r_j\). \textit{A. Malnič} and the reviewer [Two results on antisocial families of balls, Ann. Discrete Math. 51, 205-207 (1992; Zbl 0764.52009)] showed that the complete graph \(K_8\) is a CSIG. In this paper it is proved that \(K_{12}\) is not a CSIG. For the entire collection see [Zbl 0868.00054].