Abstract sphere-of-influence graphs (Q1310234)

Let \(S\) be a finite set of points in the Euclidean plane. For each \(x \in S\), let \(r_ x\) be the smallest distance from \(x\) to any other point of \(S\), and \(B_ x\) and \(A_ x\) be the open and closed disks (respectively) of radius \(r_ x\) with center \(x\). Two graphs \(G(S)\) and \(G^*(S)\), called the sphere-of-influence graph and the closed sphere- of-influence graph, are defined on the vertex set \(S\). There is an edge \(xy\) in \(G(S)\) iff \(B_ x \cap B_ y \neq \varnothing\) and \(xy\) is an edge in \(G^*(S)\) iff \(A_ x \cap A_ y \neq \varnothing\). A graph is called a SIG (or CSIG) if it is isomorphic to some \(G(S)\) (respectively \(G^*(S))\). This paper presents several elementary results on SIGs and CSIGs. Thus all \(K_ n\) with \(n \leq 8\) are SIGs and CSIGs. While every path \(P_ n\) is a SIG, it is a CSIG iff \(n\) is even. Also every cycle is a SIG but only \(C_ 3\) and even cycles (among cycles) are CSIG. No star \(K_{1,n}\) \((n \geq 3)\) is a SIG and not every induced subgraph of a SIG (CSIG) is a SIG (or CSIG). It is conjectured that the smallest \(K_ n\) which is not a SIG (CSIG) is \(K_ 9\). It is also proved that every tree on \(n\) vertices is an induced subgraph of a SIG, isomorphic to \(G(S)\) for some \(S\) with at most \(2n-3\) points. Possibility of generalization to other metrics and higher dimensions is suggested.