GraphData Source Information

GraphData contains a number of simple undirected graphs compiled from various sources. Most properties have been computed using Mathematica, although a number have been taken from the literature. Properties have been checked for consistency using a variety of known mathematical relations and formulas.

Among principal sources for GraphData are:

Aichholzer, O. "On the Rectilinear Crossing Number." 2004. »

Aldred, R. E. L., S. Bau, D. A. Holton, and B. D. McKay. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM Journal of Discrete Mathematics 13 (2000): 25-32.

Aldred, R. E. L., B. D. McKay, and N. C. Wormald. "Small Hypohamiltonian Graphs." Journal of Combinatorial Mathematics and Combinatorial Computing 23 (1997), 143-152.

Babic, D., D. J. Klein, I. Lukovits, S. Nikolic, and N. Trinajstic. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." International Journal of Quantum Chemistry 90 (2002): 166-176.

Beresford, R. "Regular Graph Synthesis & Visualization." Mathematica notebook. Pers. comm., May 6, 2004.

Biggs, N. Algebraic Graph Theory. Cambridge University Press, 1993.

Brandstädt, A., V. B. Le, and J. P. Spinrad. Graph Classes: A Survey. SIAM, 1999.

Brimkov, V.E., B. Codenotti, V. Crespi, and M. Leoncini, "On the Lovász Number of Certain Circulant Graphs." In Algorithms and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome, March 1-3, 2000 (Eds. G. Bongiovanni, G. Gambosi, and R. Petreschi), 291-305, 2000.

Brouwer, A. E. "Descriptions of Various Graphs." 2006. »

Brouwer, A. E., A. M. Cohen, and A. Neumaier. Distance-Regular Graphs. Springer-Verlag, 1989.

Chvátal, V. "Flip-Flops in Hypohamiltonian Graphs." Canadian Mathematical Bulletin 16 (1973): 33-41.

Colbourn, C. J. and J. H. Dinitz (Eds.). CRC Handbook of Combinatorial Designs. CRC Press, 647-648, 1996.

Conder, M., A. Malnic, D. Marusic, T. Pisanski, and P. Potocnik. "The Ljubljana Graph." 2002. »

Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bulletin of the American Mathematical Society 56 (1950): 413-455.

Devillers, J. and A. T. Balaban (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. CRC Press, 2000.

Ellis-Monaghan, J. A. and C. Merino. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. »

Ellis-Monaghan, J. A. and C. Merino. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. »

Eppstein, D. "Topology of xyz Graphs." 9 Jun 2006. »

Eppstein, D. "Cubic Symmetric xyz Graphs." 16 Oct 2007. »

Eppstein, D. "The Many Faces of the Nauru Graph." 12 Dec 2007. »

Exoo, G. "Regular Graphs of Given Degree and Girth." 2006. »

Exoo, G. "Rectilinear Drawings of Famous Graphs." 2006. »

Exoo, G. "Rectilinear Crossing Number Computations." Personal communication, Jan. 2010.

Frucht, R. "A One-Regular Graph of Degree Three." Canadian Journal of Mathematics 4 (1952): 240-247.

Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics DS6 (Jan. 3, 2007): 1-58. »

Georges, J. P. "Non-Hamiltonian Bicubic Graphs." Journal of Combinatorial Theorem B 46 (1989): 121-124.

Gerbracht, E. H.-A. "Minimal Polynomials for the Coordinates of the Harborth Graph." 2006. »

Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Unpublished lecture notes. Kolloquium über Kombinatorik, Magdeburg, Germany, Nov. 15, 2008.

Gerbracht, E. H.-A. "Eleven Unit Distance Embeddings of the Heawood Graph." 2009. »

Gethner, E. and W. M. Springer II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congressus Numerantium 164 (2003): 159-175.

Grünbaum, B. "3-Connected Configurations (n_3) with No Hamiltonian Circuit." Bulletin of the Institute of Combinatorics and its Applications 46, (2006) 15-26.

Grünbaum, B. Configurations of Points and Lines. American Mathematical Society, 2009.

Guy, R. K. and T. A. Jenkyns. "The Toroidal Crossing Number of ." Journal of Combinatorial Theory 6, (1969): 235-250.

Hall, J. I. "Locally Petersen Graphs." Journal of Graph Theory 4, (1980): 173-187.

Harary, F. Graph Theory. Addison-Wesley, 1969.

Harary, F., S. Hedetniemi, and R. Robinson. "Uniquely Colorable Graphs." Journal of Combinatorial Theory 6 (1969): 264-270.

Harary, F., S. Hedetniemi, and R. Robinson. "Erratum to 'Uniquely Colorable Graphs.'" Journal of Combinatorial Theory 9 (1970): 221.

Harborth, H. and M. Möller. "Minimum Integral Drawings of the Platonic Graphs." Mathematics Magazine 67 (1994): 355-358.

Hatzel, H. "Ein planarer hypohamiltonscher Graph mit 57 Knoten." Math Annalen 243 (1979): 213-216.

Ho, P. T. "The Crossing Number of on the Real Projective Plane." Discrete Mathematics 304, no. 1-3 (2005): 23-33.

Horvat, B. "Predstavitve grafov z enotsko razdaljo'' ("Representations of Unit-Distance Graphs''). Ph.D. thesis, Faculty of Computer and Information Science. Ljubljana, Slovenia: University of Ljubljana, June 2009. »

Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions. Addison-Wesley, in preparation.

Levit, V. E. and E. Mandrescu. "The Independence Polynomial of a Graph—A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Eds. S. Bozapalidis, A. Kalampakas, and G. Rahonis), 233-254, 2005.

Lindgren, W. F. "An Infinite Class of Hypohamiltonian Graphs." American Mathematical Monthly 74 (1967): 1087-1089.

Lovász, L. "On the Shannon Capacity of a Graph." IEEE Transanctions on Information Theory IT-25 (1979): 1-7.

Marui, D. and T. Pisanski. "The Gray Graph Revisited." Journal of Graph Theory 35 (2000): 1-7.

Marui, D., T. Pisanski, and S. Wilson. "The Genus of the GRAY Graph Is 7." European Journal of Combinatorics 26 (2005): 377-385.

McKay, B. "Combinatorial Data: Graphs." 2006. »

Meringer, M. "Connected Regular Graphs." »

Müller, A. "Auf einem Kreis liegende Punktmengen ganzzahliger Entfernungen." Elemente der Mathematik 8 (1953): 37-38.

Pan, S. and R. B. Richter. "The Crossing Number of K_(11) is 100." Journal of Graph Theory (2007): 128-134.

Pegg, E. Jr. and G. Exoo. "Crossing Number Graphs." Mathematica Journal 11 (2009): 161-170.

Pemmaraju, S. and S. Skiena. "Computational Graph Theory with Combinatorica." 2003. »

Pemmaraju, S. and S. Skiena. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press, 2003.

Pisanski, T. and M. Randi. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Mathematical Association of America, 2000.

Rajasekaran, S. and D. S. L. Wei. "Selection, Routing, and Sorting on the Star Graph." Journal of Parallel and Distributed Computing 41 (1997): 225-233.

Read, R. C. and R. J. Wilson. An Atlas of Graphs. Oxford University Press, 1998.

Research Group on Graph Theory and Combinatorics. Applied Mathematics IV Department of the Universitat Politècnica de Catalunya. "The (Degree, Diameter) Problem for Graphs." 2006. »

Royle, G. "Cubic Graphs." 1996. »

Royle, G. "Cages of Higher Valency." 1997. »

Royle, G. "Cubic Cages." 2003. »

Royle, G. "Cubic Symmetric Graphs (The Foster Census)." 2001. »

Royle, G. "Snarks". 1996. »

Séquin, C. H. "Symmetrical Hamiltonian Manifolds on Regular 3D and 4D Polytopes." In Proceedings of Coxeter Day, 463-472, 2005.

Skiena, S. "A Database of Graphs in Combinatorica Format." 2006. »

Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. Springer, pp. 19-20, 2008.

Spence, E. "Strongly Regular Graphs on at Most 64 Vertices." 2000. »

Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Discrete Mathematics 10 (1974): 91-96.

Thomassen, C. "On Hypohamiltonian Graphs." Discrete Mathematics 10 (1974): 383-390.

Thomassen, C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Discrete Mathematics 14 (1976): 377-389.

Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." Journal of Combinatorial Theory, Series B 30 (1981): 36-44.

Tutte, W. T. "A Family of Cubical Graphs." Proceedings of the Cambridge Philosophical Society 43 (1947): 459-474.

Van Dam, E. R. and W. H. Haemers. "Which Graphs Are Determined by Their Spectrum?" Linear Algebra and its Applications 373 (2003): 241-272.

Wagon, S. Mathematica in Action, 2nd ed. Springer-Verlag, 1999. »

Wagon, S. "Chromatic and Edge Chromatic Numbers of Graphs." Personal communication, Oct. 2011.

Watts, D. J. "Networks, Dynamics, and the Small-World Phenomenon." American Journal of Sociology 105 (1999): 493-527.

Weisstein, E. W. "MathWorld: A Wolfram Web Resource." 2008. »

West, D. B. Introduction to Graph Theory. Prentice Hall, Inc., 1996.

Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. »

Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Mathematica Scandinavica 38 (2007): 211-239.

Zamfirescu, C. T. and T. I. Zamfirescu. "A Planar Hypohamiltonian Graph with 48 Vertices." Journal of Graph Theory 48 (2007): 338-342.

CapitalZHacekitnik, A., B. Horvat, and T. Pisanski. "All Generalized Petersen Graphs are Unit-Distances Graphs." University of Ljubljana, Department of Mathematics. Preprint series vol. 48, no. 1109. Jan. 4, 2010. »

To report an error or suggest an addition to GraphData, contact the Wolfram Research GraphData team.

New to Mathematica? Find your learning path »
Have a question? Ask support »