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
    What is the motivation? What are some examples and counterexamples?2012-06-27
  • 0
    Trivially, all graphs with maximum degree 2 work since you can set $l(v)$ to be constant.2012-06-27
  • 0
    That's good mhum. I added another question so that this doesn't happen.2012-06-27
  • 0
    lhf, my motivation is that I have heard that the answer involves a whole branch of mathematics. I'm trying to understand why.2012-06-27
  • 0
    @Craig: are you sure the condition is correct? This looks like, but doesn't seem to be quite, a condition that defines Dynkin diagrams (http://en.wikipedia.org/wiki/Dynkin_diagram), which are related to _multiple_ branches of mathematics (representation theory, Lie theory, algebraic geometry...).2012-06-27
  • 0
    Qiaochu, that is correct that I'm trying to get an answer that will be the Dynkin diagrams. Then I want to understand why. What is the condition that I'm looking for?2012-06-27
  • 5
    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.2012-06-27
  • 0
    I'm not making anyone play guessing games. I asked a question, didn't get the answer I wanted, and then added another question. It is still a valid question, regardless of my motivations. Do you know the answer?2012-06-27
  • 0
    Can you please at least clarify whether you are talking about finite, undirected graphs?2012-06-27
  • 0
    Yes, finite undirected graphs.2012-06-27
  • 0
    Aren't graphs always assumed to be finite and undirected unless told otherwise?2012-06-27
  • 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
    Thank you. This is exactly what I was looking for. But I can't seem to reach the link you provided though.2012-06-27
  • 0
    Weird, it works for me. [Alternate link](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152.9602&rep=rep1&type=pdf)2012-06-27
  • 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
    I think I found the answer here: http://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."2012-06-27
  • 0
    @CraigFeinstein: You do realize that this is a stronger condition? (there is an equality instead of an inequality)2012-06-27
  • 0
    @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.2012-06-27
  • 0
    Yes, please post your answer. I answered your question above.2012-06-27