Graphs and Graph Theory

Poster Session
  • [1] D. Liu, and X. Zhu, Multi-level Distance Labelings for Paths and Cycles, SIAM J. Disc. Math, to appear.
  • [2] W.K.Hale, Frequency Assignment: Theory and Applications, Proc IEEE, 68 (1980), 1497-1514.
  • [3] G. Chartrand, D. Erwin, F. Haray and P. Zhang,  Radio Lablings of Graphs, Bull.  Inst. Combin. Appl., 33 (2001), 77--85.
  • [4] G. Chartrand, D. Erwin, and P. Zhang, A Graph Labeling Problem Suggested by FM Channel Restrictions, Bull.  Inst. Combin. Appl., accepted.
  • [5] G. Chartrand, L. Nebesky and P. Zhang, Radio k-colorings of Paths, Discuss. Math. Graph Theory, accepted.
  • [6] D. Liu, M. Xie, Radio Numbers for Square of Paths, manuscript.
  • [7] D. Liu, M. Xie, Radio Numbers for Square of Cycles, manuscript.
  • [8] P. Zhang, Radio Labellings of Cycles,  Arc. Combin. 65 (2002)     21—32.
Historical Sketch
  • Brian Hopkins and Robin J. Wilson, "The Truth about Königsberg," The College Mathematics Journal, Vol. 35, No. 3, May 2004, pp. 198-207.   [Note:  The NCB thanks Hopkins and Wilson for this invaluable historical source and translations.]

Historical Sketch


 from Euler's paper of 1736

Euler's 1736 paper on the bridges of Königsberg is widely recognized as the origin of graph theory.

Euler was prompted to investigate the 'calculus of position' by a letter from the mayor of Danzig in Prussia (now Gdansk in Poland), some 80 miles west of Königsberg.
Euler replied to the mayor that this type of problem "bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it......(M)ost noble Sir, you have assigned this question to the geometry of position, but I am ignorant as to what this new discipline involves..."

Euler, being the genius that he was, clearly was captivated.  Soon thereafter he wrote an Italian mathematician . . . .

"A problem was posed to me about an island in the city of Königsberg, surrounded by a river spanned by seven bridges, and I was asked whether someone could traverse the separate bridges in a connected walk in such a way that each bridge is crossed only once.....This question is so banal, but seemed to be worthy of attention in that geometry, nor algebra, nor even the art of counting was sufficient to solve it.  In view of this, it occurred to me to wonder whether it belonged to the geometry of position which Leibniz had once so much longed for.  And so, after some deliberation, I obtained a simple, yet completely established, rule with whose help one can immediately decided for all examples of this kind, with any number of bridges in any arrangement ...."
Leonhard Euler to Giovanni Marinoni
March 13, 1736