# 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$.

The condition you wrote down might be equivalent to this condition, but I can't easily see the equivalence if it is. The Wikipedia article suggests that there is a characterization using the Laplacian (the spectral radius is defined using the adjacency matrix) that looks like what you're saying and gives references.

-
I think I found the answer here: en.wikipedia.org/wiki/Discrete_Laplace_operator It says, "The ordinary ADE graphs are the only graphs that admit a positive labeling with the following property: Twice any label minus two is the sum of the labels on adjacent vertices." – Craig Feinstein Jun 27 '12 at 14:11
@CraigFeinstein: You do realize that this is a stronger condition? (there is an equality instead of an inequality) – Generic Human Jun 27 '12 at 14:27
@GenericHuman, It's actually too strong a condition because it says "minus two" instead of inequality. But I'm guessing that the "two" in "minus two" could be replaced by any even number, so the inequality would still hold. – Craig Feinstein Jun 27 '12 at 14:52