0
$\begingroup$

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

  • 0
    Since you replied to Qiaochu that you were looking for Dynkin diagrams and those can often be directed, it was far from obvious, especially given the total lack of context.2012-06-27

2 Answers 2

3

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.

  • 0
    The alternate link works, thank you.2012-06-27
2

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.

  • 0
    Yes, please post your answer. I answered your question above.2012-06-27