<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 3" %>
Polytopes of Magic Labelings of Graphs and the Faces of the Birkhoff Polytope
Maya Mohsin Ahmed
Mechanical Engineering Department, Manipal Institute of Technology, Manipal 576 104, Karnataka, India
Annals of Combinatorics 12 (3) pp.241-269 September, 2008
AMS Subject Classification: 05E
In this article, we construct and enumerate magic labelings of graphs using Hilbert bases of polyhedral cones and Ehrhart quasi-polynomials of polytopes. This enables us to generate and enumerate perfect matchings of a graph via magic labelings of the graph. We explore the correspondence of magic labelings of graphs with magic squares and define polytopes of magic labelings to give a description of the faces of the Birkhoff polytope as polytopes of magic labelings of digraphs.
Keywords: symmetric magic squares, magic labelings of graphs, Polyhedral cones, Polytopes, Hilbert basis, Ehrhart quasi-polynomials, Invariant rings, Birkhoff polytope


1. G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1-4) (1912/13) 42–46.

2. B. Bollob´as, L. Pebody, and O. Riordan, Contraction-deletion invariants for graphs, J. Combin. Theory Ser. B 80 (2) (2000) 320–345.

3. T. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, In: Matroid Applications, N.L. White Ed., Cambridge Univ. Press, Cambridge, (1992) pp. 123–225.

4. P. Erdos, L. Lov´asz, and J. Spencer, Strong independence of graphcopy functions, In: Graph Theory and Related Topics, Academic Press, New York, (1979) pp. 165–172.

5. G.E. Farr, Tutte-Whitney polynomials: some history and generalizations, In: Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh, G. Grimmett and C. MacDiarmid, Eds., Oxford Univ. Press, Oxford, (2007) pp. 28–52.

6. R.M. Foster, The Foster Census, Charles Babbage Research Centre, Winnipeg, Manitoba, 1988.

7. C.M. Fortuin and P.W. Kasteleyn, On the random-cluster model. I. Introduction and relations to other models, Physica 57 (4) (1972) 536–564.

8. W.H. Haemers and E. Spence, Enumeration of cospectral graphs, Europ. J. Combin. 25 (2) (2004) 199–211.

9. J.P.S. Kung, Twelve views of matroid theory, In: Combinatorial & Computational Mathematics (Pohang 2000), S. Hong, J.H. Kwak, K.H. Kim, and F.W. Roush, Eds., World Scienti fic, River Edge, NJ, (2001) pp. 56–96.

10. M. Noy, Graphs determined by polynomial invariants, Theoret. Comput. Sci. 307 (2) (2003) 365–384.

11. P. Orlik and L. Solomon, Combinatorics and topology of complements of hyperplanes, Invent. Math. 56 (2) (1980) 167–189.

12. R.C. Read and W.T. Tutte, Chromatic Polynomials, In: Selected Topics in Graph Theory, Vol. 3, L.W. Beineke and R.J. Wilson, Eds., Academic Press, San Diego, CA, (1988) pp. 15–42.

13. R.C. Read and E.G. Whitehead, The Tutte polynomial for homeomorphism classes of graphs, Discrete Math. 243 (1-3) (2002) 267–272.

14. L. Traldi, A dichromatic polynomial for weighted graphs and link polynomials, Proc. Amer. Math. Soc. 106 (1) (1989) 279–286.

15. W.T. Tutte, Graph Theory as I Have Known It, Oxford Univ. Press, New York, 1998.

16. W.T. Tutte, Graph-polynomials, Adv. Appl. Math. 32 (1-2) (2004) 5–9.

17. A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, In: Surveys in Combinatorics 2005, Cambridge Univ. Press, Cambridge, (2005) pp. 173– 226.

18. H. Whitney, The coloring of graphs, Ann. of Math. 33 (2) (1932) 688–718.