# GRAPH THEORY

Academic Year 2023/2024 - Teacher: Mario GIONFRIDDO

## Expected Learning Outcomes

The couse has the following objectives:

Knowledge and understanding:

- Mathematic Instruments in graph theory such as theorems and algoritms will be provide in the course. They permit to develop mathematical abilities in reasoning and calculation. These abilities could permit to resolve known problems by mathematical model.

Applying and knowledge and understanding:

- At the end of course student will be able to get knowledge for a tightened use of new mathematical techniques and an understanding of treated arguments in such way to link them each other.

Making judgements:

- Course is based on logical-deductive method which wants to give to students authonomus judgement useful to understanding incorrect method of demonstration also, by logical reasoning, student will be able to face not difficult problems in graph theory with teacher's help.

Communication skills:

- In the final exam, student must show for learned different mathematical techniques an adapt maturity on oral communication using also multimedia tools.

Learning skills

- Autonomously student will be able to face application and theoretical arguments which could be studied in new classes or in different working fields; for example flow theory and connectivity have huge application on telecommunications field (Local Area Network and Metropolitan Area Network: LAN e MAN), on electrical and communication fields (Industrial design).

## Course Structure

Graph Theory 9 CFU

### total study 225 hours

152  hours of individual study
49  hours of frontal lectures
24 hours of exercises

The lessons will be held through classroom. In these lessons the program will be divided into the followingsections: basic notions, planar graphs, cycles and cocycles, different graph connections, graph fluxes,matchings and coverings, colorability.

In each of these sections first it will be discussed the main theoretical topics and then showed how these topicscan be linked to possible applications. Then algorithms can be presented, and they allow in many cases to

identify particular graphs or solutions proposed by the theoretical results

Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes withrespect to previous statements, in line with the programme planned and outlined in the syllabus.

Learning assessment may also be carried out on line, should the conditions require it.

Students with disability shoudl contact CINAP

## Required Prerequisites

basic notions of Linear Algebra

## Attendance of Lessons

strongly recommended

## Detailed Course Content

Basic definition on Graph Theory. Cycles and cocycles. Cyclomatic and cocyclomatic numbers. Planar graphand their property. Euler's formula. Tree and cotree. Spanning tree. Strongly and minimally connected graphsand their property. Maximum and perfect matchings. Covering and minimum covering of a graph. Matching inbipartite graph, Köenig's theorem. Hamiltonian and Eulerian graphs. Edge and vertex colourings, chromaticnumber and index number. Vizing's theorem. Basic notion on Hypergrapghs and G-designs. Properties of digraphs. Basin notion on Matroids

Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes withrespect to previous statements, in line with the programme planned and outlined in the syllabus.

Learning assessment may also be carried out on line, should the conditions require it.

## Textbook Information

1.  C. Berge, "Graph and Hypergraph", Elsevier.

2.  M. Gionfriddo, Notes on Graph Theory 2018 (disponibili con il consenso del Prof. Emerito M. Gionfriddo)

3.  D. West, Introduction to Graph Theory

4. V.Voloshin, Introduction to Graph Theory

## Course Planning

SubjectsText References
1graphs1,2,3
2Planar graphs1,2,3
3Factorization1,2,3
4vertex coloring1,2,3
5edge coloring1,2,3
6Chromatic polynomial1,2,3
7Stability1,2,3
8Digraphs1,2,3
9Flow Network1,2,3
10Strongly connected graphs1,2,3
11notions on Hypergraphs and G-Designs1,2,3

## Learning Assessment

### Learning Assessment Procedures

Final grades will be assigned taking into account the following crieria:

Rejected: Basic knowledges have not been acquired. The student is not able to solve simple exercises.

18-23: Basic knowledges have been acquired. The student solves simple exercises and has sufficient communications skills and making judgements.

24-27: All the  knowledges have been acquired. The student solves all the proposed exercises making few errors and has good communications skills and making judgements.

28-30 cum laude: All the knowledges have been completely acquired. The student applies knowledge and has excellent communications skills, learning skills and making judgements.

Learning assessment may also be carried out online, should the conditions require it.

### Examples of frequently asked questions and / or exercises

Basic definition on Graph Theory

Trees, Minimum Spanning trees

Eulerian and hamoltonian graphs

Planar graph and their property. Euler's formula.

Maximum and perfect matchings.

Matching in bipartite graph, Hall's Theorem Köenig's theorem.

Edge and vertex colourings, chromatic number and index number.

Properties of digraphs. Basic notion on Matroids