5
$\begingroup$

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 :)

Improve this question
$\endgroup$
5
  • $\begingroup$ Complete bipartite graph? $\endgroup$
    – Yoav Kallus
    Commented Jun 22, 2013 at 21:43
  • 2
    $\begingroup$ More generally, any biregular graph: en.wikipedia.org/wiki/Biregular_graph $\endgroup$
    – Yoav Kallus
    Commented Jun 22, 2013 at 21:48
  • 2
    $\begingroup$ 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). $\endgroup$
    – Thomas Bloom
    Commented Jun 22, 2013 at 23:52
  • $\begingroup$ 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). $\endgroup$
    – Thomas Bloom
    Commented Jun 23, 2013 at 0:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Benoît Kloeckner
    Commented Jun 24, 2013 at 11:07

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .