Extremal Problems for Imbalanced Edges | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Extremal Problems for Imbalanced Edges

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |d G (u)−d G (v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |d G (u)−d G (v)|≥d for some given d.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alavi, Y., Chartrand, G., Chung, F.R.K., Erdős, P., Graham, R.L., Oellermann, O.R.: Highly irregular graphs. J. Graph Theory 11, 235–249 (1987)

    Google Scholar 

  2. Albertson, M.O.: The irregularity of a graph. Ars Combinatoria 46, 219–225 (1997)

    Google Scholar 

  3. Bell, F.K.: A note on the irregularity of graphs. Linear Algebra Appl. 161, 45–54 (1992)

    Google Scholar 

  4. Caro, Y., Yuster, R.: Graphs with large variance. Ars Combinatoria 57, 151–162 (2000)

    Google Scholar 

  5. Henning, M., Rautenbach, D.: On the Irregularity of Bipartite Graphs, to appear in Discrete Math.

  6. Rautenbach, D.: Propagation of mean degrees. Electr. J. Combin. 11, N11 (2004)

  7. Rautenbach, D., Volkmann, L.: How local irregularity gets global in a graph. J. Graph Theory 41, 18–23 (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 53113, Bonn, Germany

    Dieter Rautenbach

  2. Institut für Diskrete Mathematik und Algebra, Technische Universität Bergakademie Freiberg, 09596, Freiberg, Germany

    Ingo Schiermeyer

Authors
  1. Dieter Rautenbach
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Ingo Schiermeyer
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Dieter Rautenbach.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rautenbach, D., Schiermeyer, I. Extremal Problems for Imbalanced Edges. Graphs and Combinatorics 22, 103–111 (2006). https://doi.org/10.1007/s00373-005-0643-y

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-005-0643-y

Keywords