Graph Theory: Penn State Math 485 Lecture Notes

This is a set of lecture notes for Math 485–Penn State’s undergraduate Graph Theory course. Readers should have taken a course in combinatorial proof and ideally matrix algebra.

**Tag(s):**
Graph Theory

**Publication date**: 31 Dec 2012

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
173 pages

**Views**: 8,211

**Type**: Lecture Notes

**Publisher**:
n/a

**License**:
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States

**Post time**: 05 Dec 2016 09:00:00

Graph Theory: Penn State Math 485 Lecture Notes

This is a set of lecture notes for Math 485–Penn State’s undergraduate Graph Theory course. Readers should have taken a course in combinatorial proof and ideally matrix algebra.

You are free to:

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click**here** to read the full license.

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click

Excerpts from the Preface:

Christopher Griffin wrote:The lecture notes are loosely based on Gross and Yellen's Graph Theory and It's Applications, Bollobás' Graph Theory, Diestel's Graph Theory, Wolsey and Nemhauser's Integer and Combinatorial Optimization, Korte and Vygen's Combinatorial Optimization and several other books that are cited in these notes. All of the books mentioned are good books (some great). The problem is, they are either too complex for an introductory undergraduate course, have odd notation, do not focus enough on applications or focus too much on applications.

This set of notes correct some of the problems I mention by presenting the material in a format for that can be used easily in an undergraduate mathematics class. Many of the proofs in this set of notes are adapted from the textbooks with some minor additions. One thing that is included in these notes is a treatment of graph duality theorems from the perspective linear optimization. This is not covered in most graph theory books, while graph theoretic principles are not covered in many linear or combinatorial optimization books. I should note, Bondy and Murty discuss Linear Programming in their book Graph Theory, but it is clear they are not experts in optimization and their treatment is somewhat non sequitur, which is a shame. The best book on the topic of combinatorial optimization is by far Korte and Vygen's, who do cover linear programming in their latest edition. Note: Penn State has an expert in graph coloring problems, so there is no section on coloring in these notes, because I invited a guest lecturer who was the expert. I may add a section on graph coloring eventually.

Tweet

About The Author(s)

Assistant Professor of Mathematics at United States Naval Academy. Research interests include applications of game theorey, optimization and mathematical logic to problems of national security and the intelligence community.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Rexx
Microsoft .NET
Perl
PHP
R
Python
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors