Course teached as: B018796 - TEORIA DEI GRAFI E COMBINATORIA Second Cycle Degree in MATHEMATICS Curriculum APPLICATIVO
Teaching Language
Italian
Course Content
Graph Theory, especially simple non-directed graphs.
Basic and advanced notions of Graph Theory.
Planar Graphs.Euleria Graphs. Hamiltonian Graphs. Classic Combinatorics. Designs and their parameters.Finite Projective Planes. Fundamental theorems of Graph Theory and Comnbinatorics. Some important open problems and conjectures in Graph Theory and Combinatorics
Chartrand-Lesniak-
Zhang "Graphs and Digraphs" Fifth Edition
Learning Objectives
Obtaining some knowledge of the basic notions of Graph Theory and Combinatorics
Being able to devise proofs of simple propositions regarding Graphs, Designs and other Combinatorial Structures
Being able to apply some ideas from Graph Theory and Combinatorics to problems of various
kinds
Prerequisites
Basic notions in Group Theory and Algebra (as
obtained from the courses Algebra I and Algebra II)
Teaching Methods
Class lectures with
student participation to the discovery and proof of mathematical concepts and Propositions
Type of Assessment
Mid-term and final written exams
Course program
Definition of a Graph
Definition of a Group
Automorphism Group of a Graph
Vertex-transitive Graphs
Examples and Exercises
Adjacency Matrix of a Graph
Eigenvalues of a Graph
Basic Propositions on eigenvalues and cycles in a Graph.
Planar Graphs. Eulerian Graphs. Hamiltonian Graphs.
Important Problems in Graph Theory:
-- Lovasz Conjecture
-- Reconstruction Comjecture
-- The Conjecture on Three Longest Paths
-- Lauri Conjecture on pseudo-similar vertices
Definition of a Design
Parameters of a Design
Basic Propositions on the Symmetric Balanced Designs
Projective Planes
The Conjecture on the Order of a Projective Plane
Bruck-Ryser Theorem
Chvatal Conjecture