Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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. –  Gerry Myerson Jun 27 '12 at 3:26
show 7 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
    
Yes, please post your answer. I answered your question above. –  Craig Feinstein Jun 27 '12 at 14:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.