Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The imbalance of an edge $(u,v) \in E(G)$ of a graph $G$ is defined as $|d(u)-d(v)|$ ($d$ being, as usual the degree). (This concept was introduced by Albertson in 1997)

I'm interested in the set of possible imbalances in a graph. In particular I am looking for examples of graphs where all edges have the same imbalance. Regular graphs trivially have this property and so does the path $P_{3}$.

Is it true that if all edges of $G$ have the same imbalance, then $G$ is either regular or $P_{3}$?

I have an inkling that this ought to be true by some sort of pigeonhole principle but can't think up a proof. A counterexample will be even more welcome :)

share|improve this question
    
Complete bipartite graph? –  Yoav Kallus Jun 22 '13 at 21:43
2  
More generally, any biregular graph: en.wikipedia.org/wiki/Biregular_graph –  Yoav Kallus Jun 22 '13 at 21:48
2  
You need that $G$ is connected, of course. Furthermore, there are graphs with constant imbalance that are not even biregular (for example. the graph on 7 vertices with 3 vertices of degree 1 each attached to a vertex of degree 2 each attached to a unique vertex of degree 3). –  Thomas Bloom Jun 22 '13 at 23:52
    
And, in fact, that idea can be generalised easily to construct arbitrarily large graphs with arbitrarily large constant imbalance (take a bunch of vertices with degree 1, connect them to a bunch with degree 1+n, connect those to a bunch of 1+2n, and so on, just throwing enough vertices at each stage to make this possible). –  Thomas Bloom Jun 23 '13 at 0:03
1  
The simplest example I can think of (included in biregular graphs) is the star graph; can be arbitrarily large, and has largest possible constant imbalance. Any edge transitive, not vertex-transitive graph gives an example. –  Benoît Kloeckner Jun 24 '13 at 11:07
add comment

1 Answer

As Kallus and Thomas Bloom mentioned it in the comments: NO.

For example there are biregular graphs see: http://en.wikipedia.org/wiki/Biregular_graph

And, (as Thomas Bloom said) that idea can be generalised easily to construct arbitrarily large graphs with arbitrarily large constant imbalance (take a bunch of vertices with degree 1, connect them to a bunch with degree 1+n, connect those to a bunch of 1+2n, and so on, just throwing enough vertices at each stage to make this possible).

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