# Which graphs have this property?

Which (finite, undirected) graphs have this property?

Every vertex $v$ can be labeled with a positive integer $l(v)$.

Variant 1: For each vertex $v$, $l(v) \geq \Sigma_{[v,w] \in E, w \neq v} l(w)/2$.

Variant 2: For each vertex $v$, $l(v) > \Sigma_{[v,w] \in E, w \neq v} l(w)/2$.

-
What is the motivation? What are some examples and counterexamples? –  lhf Jun 27 '12 at 1:09
Trivially, all graphs with maximum degree 2 work since you can set $l(v)$ to be constant. –  mhum Jun 27 '12 at 2:43
That's good mhum. I added another question so that this doesn't happen. –  Craig Feinstein Jun 27 '12 at 2:49
lhf, my motivation is that I have heard that the answer involves a whole branch of mathematics. I'm trying to understand why. –  Craig Feinstein Jun 27 '12 at 2:51
Instead of making us play guessing games, please put your cards on the table and tell us what you are really after - and preferably not in the comments, but by editing the question. –  Gerry Myerson Jun 27 '12 at 3:26

Here $G$ is a finite undirected graph.

Suppose wlog that $G$ is connected, with at least 2 vertices $1,\dots,n$ and no self-edges. There is no reason to forbid multiple edges. Define $M=A/2$ where $A$ is the adjacency matrix of $G$.

Theorem: $G$ satisfies the first condition (respectively the second condition) iff its index, that is the spectral radius of its adjacency matrix, is $\le 2$ (resp. $<2$).

Proof:

• Suppose $G$ has a labeling $x\in (\mathbb N^*)^n\subset\mathbb R_+^n\setminus\{0\}$. Then using the hypothesis it's clear by induction that each component of $M^k x$ is a non-negative non-increasing function of $k$ (respectively, exponentially decaying). Because $M$ is diagonalizable, the decay of the largest component is of the form $\Theta(\lambda^k)$, where $1/2\le\lambda\le 1$ (resp. $<1$) is an eigenvalue of $M$. But $\lambda^{-k} M^k x$ converges to a positive eigenvector $y$ of $M$ associated with $\lambda$, so that by Perron-Frobenius $\lambda\le 1$ (resp. $<1$) is the spectral radius of $M$. Therefore the spectral radius of $A$ must be at most 2 (resp. $<2$).

• Conversely, if the spectral radius of $A$ is at most 2, we can distinguish two cases. If the radius is exactly 2, then we can find an integer non-negative eigenvector of $M$ (as $\det M-I=0$ implies that $M-I$ has non-trivial kernel in $\mathbb Q^n$ thus in $\mathbb Z^n$), and therefore, because $G$ is connected and has at least one edge, a positive integer eigenvector. So there is a labeling for the first condition. If the radius is less than 2, take a positive real eigenvector $x$ of $M$ associated with $0<\lambda<1$. If $m>0$ is the smallest element of $x$, let $y = \left\lfloor\frac{2}{(1-\lambda)m}x\right\rfloor$. Then $(y-My)_i\ge 1$ so that the second condition holds.

We know a classification of such graphs, e.g. see here.

-
Thank you. This is exactly what I was looking for. But I can't seem to reach the link you provided though. –  Craig Feinstein Jun 27 '12 at 16:04
Weird, it works for me. Alternate link –  Generic Human Jun 27 '12 at 16:09
The alternate link works, thank you. –  Craig Feinstein Jun 27 '12 at 16:12
The simply laced Dynkin diagrams $A_n, D_n, E_6, E_7, E_8$ are precisely the connected (simple, undirected) graphs with spectral radius less than $2$. This is more or less equivalent to a closely related result I prove in this blog post describing the connected (simple, undirected) graphs of spectral radius exactly $2$.