Drexel dragonThe Math ForumDonate to the Math Forum

The Math Forum Internet Mathematics Library

Browse and Search the Library
Home : Math Topics : Discrete Math : Graph Theory

_____________________________________
Library Home || Search || Full Table of Contents || Suggest a Link || Library Help
_____________________________________


  Selected Sites   (see also All Sites in this category)

  1. The Bridges of Königsberg - Isaac Reed
    This problem inspired the great Swiss mathematician Leonard Euler to create graph theory, which led to the development of topology. more>>

  2. The Four Colour Theorem - MacTutor Math History Archives
    Linked essay describing work on the theorem from its posing in 1852 through its solution in 1976, with two other web sites and 9 references (books/articles). more>>

  3. Graph Theory - Dave Rusin; The Mathematical Atlas
    A short article designed to provide an introduction to graph theory. A graph is a set V of vertices and a set E of edges - pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing (binary) relations on sets. Among the topics of interest are topological properties such as connectivity and planarity (can the graph be drawn in the plane?); counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the Four-Color Theorem); paths, cycles, and distances in graphs (can one cross the Königsberg bridges exactly once each?). Many graph-theoretic topics are the object of complexity studies in computation (e.g. the Travelling Salesman problem, sorting algorithms, the graph-isomorphism problem). The theory also extends to directed, labelled, or multiply-connected graphs. History; applications and related fields and subfields; textbooks, reference works, and tutorials; software and tables; other web sites with this focus. more>>

  4. Graph Theory Tutorials - Chris K. Caldwell
    A series of short interactive tutorials introducing the basic concepts of graph theory, designed with the needs of future high school teachers in mind and currently being used in math courses at the University of Tennessee at Martin. An Introduction to Graph Theory tutorial uses three motivating problems to introduce the definition of graph along with terms like vertex, arc, degree, and planar. Includes a glossary and a partially annotated bibliography of graph theory terms and resources. Euler Circuits and Paths; Coloring Problems (Maps). more>>

  5. Perfect Problems - Vasek Chvátal
    Unsolved problems on perfect graphs, a collection for people with at least a basic knowledge of the subject. Contents include: Perfection of special classes of Berge graphs; Recognition of special classes of Berge graphs; Decompositions of perfect graphs; Minimal imperfect graphs, partitionable graphs, and monsters; Parity problems; The P4-structure; Quantitative variations on the Strong Perfect Graph Conjecture; Intersection graphs; The Markosyan manoeuvre; Appendix: Odds and ends. With a bibliography, and home pages of people interested in perfect graphs. more>>


 
  All Sites - 178 items found, showing 1 to 50

  1. A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not 1-Transitive [PDF] - Peter Doyle
    A paper describing a 27-vertex graph that is vertex-transitive and edge-transitive but not 1-transitive. While all vertices and edges of the graph are similar, there are no edge-reversing automorphisms. PostScript, source, and PDF picture are available ...more>>

  2. Adventures in the MathZone - Ivars Peterson (MathTrek)
    Ivars Peterson and his wife, Nancy Henderson, have written "a book that introduces children to a variety of ideas also of interest to today's mathematicians: knots, map coloring, Möbius strips and topology, prime numbers, chaos, fractals, and more. Our ...more>>

  3. Algorithms Project - Institut National de Recherche en Informatique et en Automatique (INRIA)
    A small international group of people with interests in design and analysis of algorithms, computer algebra, combinatorial analysis and asymptotics. It aims at general methods in combinatorics and analysis, with which classes of problems can be treated ...more>>

  4. Application of Rayleigh's Short-Cut Method to Polya's Recurrence Problem [PDF] - Peter Doyle
    Doyle's Ph.D. thesis at Dartmouth College, June 1982. The goals of the presentation are to explain why Polya's theorem is true and to develop techniques for applying Rayleigh's method. The main results make sense of the notion that if two graphs look ...more>>

  5. Arbeitsgruppe Bachem/Schrader - University of Köln
    A working group of the Center for Parallel Computing (ZPR) at Köln. Site includes a list of members and contact address; informative write-ups on its projects, some in English. Topics include: Basic Research (meaning "pure" as opposed to "applied"); ...more>>

  6. Arnd Roth - Arnd Roth, Institute for Theoretical Physics, Heidelberg, Germany
    Arnd Roth studies computational physics and neuroscience. This page provides documentation and code for related Mathematica notebooks, and a notebook for the Knight's Tour chess problem, available online. Also links to abstracts or text of many of Roth's ...more>>

  7. Averting Instant Insanity - Ivars Peterson (MathTrek)
    Once called "The Great Tantalizer," the puzzle looks innocuous and sounds quite simple. It consists of a set of four cubes with one of four colors on each of their six faces. Your goal is to arrange the four cubes in a row so that all four colors appear ...more>>

  8. The Best Two Points in a Square (Math Chat) - Frank Morgan, MAA Online
    Solution to the challenge: Where do you think you should you place two points in a unit square to minimize the average distance in the square to the nearest of the two points? Computer calculations by Al Zimmermann yield configurations of 2-11 points ...more>>

  9. BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems - Ke Xu
    Benchmark graphs for testing several NP-hard graph algorithms: maximum clique, maximum independent set, minimum vertex cover and vertex coloring. All instances are expressed in DIMACS format and are planted with hidden optimum solutions. ...more>>

  10. Books: Professional & Technical: Professional Science: Mathematics - Amazon.com
    Browse bestselling math books from the Professional and Technical Bookstore at Amazon.com, in such categories as Applied; Chaos & Systems; Geometry & Topology; Mathematical Analysis; Mathematical Physics; Number Systems; Pure Mathematics; Transformations; ...more>>

  11. Brendan McKay
    Software includes nauty, a program for computing automorphism groups of graphs and digraphs, which can also produce a canonical labelling; and plantri, a program for generating planar triangulations. Also, skeptical treatment of claims made of miraculous ...more>>

  12. The Bridges of Königsberg - Jim Loy
    A brief introduction to Euler's Bridges of Königsberg problem, graph theory, and simple related puzzles. ...more>>

  13. Candy for Everyone - Ivars Peterson (MathTrek)
    Several students are sitting in a circle. Each student has an even (though not necessarily the same) number of wrapped pieces of candy. On a signal, each student passes half of his or her trove to the student on his or her right. Between signals, the ...more>>

  14. Clickmazes - Gilbert, Mitchell
    An extensive collection of interactive puzzles and mazes organized in the following categories: Maze gallery; Attic gallery; Maze of Life; HexaRoll; Oskar's four-bit mazes; 2D tilt mazes; Colour-zone mazes; 3D tilt mazes; Tilt puzzles; NEWS and RULES; ...more>>

  15. The Clique Algorithm - Ashay Dharwadker
    A polynomial-time algorithm for finding maximal cliques in a graph with new bounds on Ramsey numbers. ...more>>

  16. Colorful Mathematics - Claude Laflamme
    An educational software series presenting advanced mathematical concepts to K-12 students in a game-oriented approach. The five games offered use simple coloring and/or drawing techniques to illustrate mathematical concepts from graph theory. Downloadable ...more>>

  17. Coloring Penrose Tiles - Ivars Peterson (MathTrek)
    One set of Penrose tilings consists of a pair of diamond-shaped figures--one fat and one skinny. Attempts to color such Penrose diamond tilings led some people to conjecture that three colors suffice. Now, mathematicians Tom Sibley of Saint John's University ...more>>

  18. Coloring (The Geometry Junkyard) - David Eppstein, Theory Group, ICS, UC Irvine
    An extensive annotated list of links to material on coloring problems, including the Four Color Theorem and other graph coloring problems. ...more>>

  19. Combinatorics and Graph Theory - Department of Mathematics, Umeå University, Sweden
    Home page of the Combinatorics Group. Members and research projects, seminars, archives of downloadable software, combinatorial and graph theoretical data, and preprints. ...more>>

  20. Combinatorics, Probability & Computing - Cambridge University Press
    Now published bimonthly, the journal covers combinatorics, probability theory, and theoretical computer science. Topics covered include classical and algebraic graph theory, extremal set theory, matroid theory, probabilistic methods and random combinatorial ...more>>

  21. Combinatorics Research Group - Pure Maths Department, The Open University
    A group interested in graph theory, design theory, the history of combinatorics, and combinatorial computing. The Group runs the Open University Winter Combinatorics Meeting near the end of January each year. ...more>>

  22. A compendium of NP optimization problems - Crescenzi & Kann
    A continuously updated catalog of approximability results for NP optimization problems. Because no NP-complete problem can be solved in polynomial time (unless P=NP), many approximability results (both positive and negative) of NP-hard optimization problems ...more>>

  23. Computer Lab Courseware - University of Toronto
    Courseware to help in the teaching of various mathematical concepts. Most is made up of Mathematica notebooks and packages, but some consists of C programs written to run under X-Windows. A lab manual in TeX beginning with an introduction to UNIX and ...more>>

  24. Counting Hamilton Cycles in Product Graphs - Frans Faase
    Exploration of Hamilton paths through a program which draws a snake that starts at one place in a box, and then extends itself until it cannot go further, after which it shrinks again, to seek another path. The author coded these snake programs in Fortran, ...more>>

  25. A Course on the Web Graph - Anthony Bonato
    A comprehensive introduction to state-of-the-art research on the applications of graph theory to real-world networks such as the web graph. It is the first mathematically rigorous textbook discussing both models of the web graph and algorithms for searching ...more>>

  26. Cutting Corners - Ivars Peterson (MathLand)
    Go to just about any college campus or public park and you're bound to see two kinds of trails: "official" paths defined by paved or gravel surfaces and "unofficial" routes trodden into the grass or dirt marking where pedestrians have preferred to walk ...more>>

  27. David Bruce Wilson
    David Bruce Wilson researches probability, combinatorics, and theoretical computer science. Abstracts of his articles on these subjects are available on the web and may be downloaded in PostScript or .dvi formats. Software available for download includes ...more>>

  28. David Sumner's Home Page - David Sumner
    Study guides, exams, quizzes, problem sets, exam review materials, utilities, programs and simulations, syllabi, and other materials for courses such as calculus, sequences and series, graph theory, number theory and cryptography, and probability. The ...more>>

  29. DIMACS Research and Education Institute (DREI) - Rutgers University
    An institute from the Center for Discrete Mathematics and Theoretical Computer Science which takes the approach that research and education should work hand-in-hand, that collaborations between researchers and educators are formed by understanding each ...more>>

  30. Discrete and Computational Geometry - Springer-Verlag
    An international journal of mathematics and computer science that accepts research articles of high quality in discrete geometry and on the design and analysis of geometric algorithms; more specifically, DCG publishes papers on such topics as configurations ...more>>

  31. The Discrete Mathematics Project - Dominic Peressini; University of Colorado at Boulder
    Archived resources from the collaboration of the UC Boulder School of Education and Department of Applied Mathematics. Activities sketch goals, abstracts, brief problem statements, instructor suggestions, suggestions for curriculum integration and further ...more>>

  32. Discrete Mathematics & Theoretical Computer Science (DMTCS): An Electronic Journal - Jens Gustedt
    DMTCS is an electronic journal published by the Maison de l'Informatique et des Mathématiques Discrètes, MIMD. It is a peer-reviewed publication devoted to rapid publication of innovative research which covers discrete mathematics and theoretical computer ...more>>

  33. discretemath - Math Forum
    A discussion group for subject matter concerning teaching and researching of discrete mathematics at all levels. It began as a closed list for the researchers and educators who participated in the Rutgers University Discrete Math and Theoretical Computer ...more>>

  34. Discrete Math Problem of the Week (PoW) - Math Forum
    Discrete math problems from a variety of sources, including textbooks, math contests, NCTM books, and puzzle books, and real-life situations, designed to reflect different levels of difficulty. From 1999 until 2002, this service challenged students with ...more>>

  35. Discussiones Mathematicae - Borowiecki; Technical University of Zielona Góra, Poland
    Four journals: Differential Inclusions, Control and Optimization; General Algebra and Applications; Graph Theory; and Probability and Statistics. Information for each journal includes a general description, subscription information, list of editors, ...more>>

  36. Discussiones Mathematicae Graph Theory - Borowiecki; Technical University of Zielona Góra, Poland
    The journal publishes articles in English on all aspects of graph theory, especially concerning: colourings, partitions (general colourings), hereditary properties, independence and dominating structures (sets, paths, cycles, etc.), cycles, local properties, ...more>>

  37. The Distribution of the Knight - the Theoretical Research Institute
    For every given starting point in the knight's tour problem, evaluate every possible path that visits each square exactly once, and then count how many solutions exist. Illustrations and calculations of the distribution of solutions and dead ends across ...more>>

  38. Division by Three [PDF] - John Conway, Peter Doyle
    A formal proof that it is possible to divide by three. This assertion is easy to prove using the axiom of choice, but becomes a much more difficult problem if the axiom of choice is not allowed (as is the case here). From this proof, and the much simpler ...more>>

  39. Elementary Math Enrichment - Beth Schaubroeck
    Free mathematics enrichment materials for accelerated 4th and 5th graders. The 70 lessons, grouped into 12 different units, include solutions and teacher guides: Ancient Mathematics (Mayan math, in base 20; and Egyptian math, which lacks zero), Baseball ...more>>

  40. The Erdös Number Project - Jerry Grossman
    Paul Erdos wrote hundreds of mathematical research papers in many different areas, many in collaboration with others. His Erdos number is 0. Erdos's co-authors have Erdos number 1. People other than Erdos who have written a joint paper with someone with ...more>>

  41. Erich's Combinatorial Geometry Page - Erich Friedman
    Famous and infamous problems with diagrams and some solutions and proofs. Includes: tree planting problems; circles through points; maximizing squares; triangulating squares; triangulating triangles; lines avoiding squares; lines avoiding points; points ...more>>

  42. Five Triangles mathematics blog
    This blog, which dates back to April, 2012, posts problems for middle and junior high school students. Topics have ranged from ratios and fractions to area and paths to quadratic equations and linear equations. ...more>>

  43. Four Coloring Maps - Mario Stefanutti
    Personal notes and ideas from a computer software engineer in pursuit of a "very easy pencil and paper proof of the four color problem." Posts, which date back to January, 2011, have included "Four color theorem: slow motion maps" and "Counting maps." ...more>>

  44. Four-Color Map Theorem - Math Forum, Ask Dr. Math Common Question
    A selection of answers to questions about the four-color map theorem, such as explanations, proofs, and extensions to higher dimensions and to the mobius strip. ...more>>

  45. Four Colors Suffice: How the Map Problem Was Solved - Robin Wilson; Princeton University Press
    "On October 23, 1852, Professor Augustus De Morgan wrote a letter to a colleague, unaware that he was launching one of the most famous mathematical conundrums in history--one that would confound thousands of puzzlers for more than a century. This is the ...more>>

  46. Four Color Theorem Intro - Jim Loy
    This is a brief introduction to the Four Color Theorem, and the general problem of coloring graphs. ...more>>

  47. The Four Color Theorem - Robertson, Sanders, Seymour, Thomas; Georgia Tech
    A brief summary of a new proof of the Four Color Theorem, with a four-coloring algorithm found by Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas, illustrated using a map of the United States. Contents: History; Why a new proof?; Outline ...more>>

  48. Four Travelers Problem - Interactive Mathematics Miscellany and Puzzles, Alexander Bogomolny
    Four roads on a plane, each a straight line, are oriented so that no two are parallel and no three pass through the same point. A traveler walks along each road at a constant speed. The speeds, however, may not be the same. Traveler 1 meets Travelers ...more>>

  49. Fun, Puzzles, Travel - Paul Bourke
    Brain twisters, arranged by approximate level, and designed for the most part to require no particularly advanced mathematical skills. Illusions include impossible triangle, Muller-Lyer, bad box, and Colours. ...more>>

  50. Games on Graphs (MegaMath) - Nancy Casey; Los Alamos National Laboratory
    Students use algebraic methods to explore, model, and describe patterns and functions involving numbers, shapes, data, and graphs in problem-solving situations and communicate the reasoning used in solving these problems. Graphs, stories and games provide ...more>>


 
Page:  1  2  3  4 [next>]


Search for these keywords:
               

Click only once for faster results:

all keywords, in any order at least one, that exact phrase
parts of words whole words


Power Search

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Goodwin College of Professional Studies.The Math Forum is a research and educational enterprise of the Drexel University School of Education.