ACTA issues

The slope parameter of graphs

Gergely Ambrus, János Barát, Péter Hajnal

Acta Sci. Math. (Szeged) 72:3-4(2006), 875-889

Abstract. Any point set ${\cal A}$ of the plane defines a simple graph on its elements as follows: let $P$ and $Q$ be adjacent if and only if the slope of their connecting line $\ell_{PQ}$ belongs to a prescribed set ${\cal S}$. A graph $G$ is $k$-slope if there exist a proper ${\cal A}$ and a set ${\cal S}$ of size $k$ realizing $G$. The slope parameter $sl(G)$ is the minimal such $k$. We completely characterize the $2$-slope graphs in terms of excluded induced subgraphs. For any tree $T$, we observe that $sl(T)=\Delta(T)$. We also show that if $G$ is an outerplanar graph with maximum degree at most three, then $sl(G)\leq3$. We also establish some general lower bounds, for instance ${2\over\omega (G)-1}\cdot{|E(G)|\over |V(G)|}\leq sl (G)$, where $\omega(G)$ is the size of the maximal clique of $G$.

AMS Subject Classification (1991): 05C62, 05C75

Received October 3, 2005, and in final form May 5, 2006. (Registered under 5947/2009.)