Upper bounds of Steklov eigenvalues on graphs

Let $\mathrm{\Delta }$ and $B$ be the maximum vertex degree and a subset of vertices in a graph $G$ respectively. In this paper, we study the first (non-trivial) Steklov eigenvalue ${\sigma }_2$ of $G$ with boundary $B$. Using metrical deformation via flows, we first show that ${\sigma }_2=\mathcal{O}\left(\frac{\mathrm{\Delta }(g+1{)}^3}{\mathrm{\mid }B\mathrm{\mid }}\right)$ for graphs of orientable genus $g$ if $\mathrm{\mid }B\mathrm{\mid }\ge \max \{3\sqrt{g},\mathrm{\mid }V{\mathrm{\mid }}^{\frac{1}{4}+\epsilon },9\}$ for some $\epsilon >0$. This can be seen as a discrete analogue of Karpukhin’s bound. Secondly, we prove that ${\sigma }_2\le \frac{8\mathrm{\Delta }+4X}{\mathrm{\mid }B\mathrm{\mid }}$ based on planar crossing number $X$. Thirdly, we show that ${\sigma }_2\le \frac{\mathrm{\mid }B\mathrm{\mid }}{\mathrm{\mid }B\mathrm{\mid }-1}\cdot {\delta }_B$, where ${\delta }_B$ denotes the minimum degree for boundary vertices in $B$. At last, we compare several upper bounds on Laplacian eigenvalues and Steklov eigenvalues.