Skip to main content

Discrete Structures 2

2026/2027
Programme:
Interdisciplinary University Study Programme Computer Science and Mathematics
Year:
1 year
Semester:
second
Kind:
mandatory
ECTS:
6
Language:
slovenian
Lecturer (contact person):
Hours per week – 2. semester:
Lectures
3
Seminar
0
Tutorial
3
Lab
0
Prerequisites

 There are no prerequisites.

Content (Syllabus outline)

Basics of graph theory. Eulerian and Hamiltonian graphs. Digraphs and tournaments. Connectivity and planarity. Vertex and edge colorings. Basics of abstract algebra: groups, rings, polynomials, fields.

Readings
  1. G. Fijavž: Diskretne strukture, Ljubljana : Fakulteta za računalništvo in informatiko,  2015, e- knjiga: http://matematika.fri.uni-lj.si/ds/ds.pdf
  2. N. Herstein: Abstract algebra, 3rd ed., Hoboken : J. Wiley & Sons, cop. 1999.
  3. M. Juvan, P. Potočnik: Teorija grafov in kombinatorika : primeri in rešene naloge, 2. natis, Ljubljana: DMFA-založništvo, 2007.
  4. A. Tepeh, R. Škrekovski: Diskretna matematika, Maribor : Univerzitetna založba Univerze, 2018, e-knjiga: https://press.um.si/index.php/ump/catalog/book/323
Objectives and competences

In Discrete Structures 2 student gains the demanding contents from graph theory and learn the basics of abstract algebra.

Intended learning outcomes

Knowledge and understanding: The course is based on the knowledge gained in Discrete Structures 1 The contents of the course Discrete Structures 2 are part of the necessary background knowledge for the courses Coding theory and criptography, Combinatorics and Optimization methods.

Application: Graph theory is useful in the theory of algorithms as a tool for modeling various problems. Algebraic structures used in cryptography and coding.

Reflection: Students learn the difference between continuous and discrete mathematics.

Transferable skills: Modeling problems and network structures with graphs and trees. Mastering basic algebraic structures.

Learning and teaching methods

Lectures and tutorial sessions, homework.

Assessment

2 midterm exams instead of written exam, written exam,

oral exam / theoretical test.
5 - 10, a student passes the exam if he is graded from 6 to 10

Lecturer's references

Primož Potočnik:

– POTOČNIK, Primož. Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2004, vol. 91, no. 2, str. 289-300 [COBISS-SI-ID 13087321]

– POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of symbolic computation, ISSN 0747-7171, 2013, vol. 50, str. 465-477 [COBISS-SI-ID 16520537]

– POTOČNIK, Primož. Tetravalent arc-transitive locally-Klein graphs with long consistent cycles. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 270-281 [COBISS-SI-ID 16862041]

Riste Škrekovski:

– JUNGIĆ, Veselin, KRÁL', Daniel, ŠKREKOVSKI, Riste. Colorings of plane graphs with no rainbow faces. Combinatorica, ISSN 0209-9683, 2006, vol. 26, no. 2, str. 169-182 [COBISS-SI-ID 13954393]

– DVOŘÁK, Zdeněk, ŠKREKOVSKI, Riste. A theorem about a contractible and light edge. SIAM journal on discrete mathematics, ISSN 0895-4801, 2006, vol. 20, no. 1, str. 55-61 [COBISS-SI-ID 14249305]

– KAISER, Tomáš, ŠKREKOVSKI, Riste. T-joins intersecting small edge-cuts in graphs. Journal of graph theory, ISSN 0364-9024, 2007, vol. 56, no. 1, str. 64-71 [COBISS-SI-ID 14373977]

Sandi Klavžar:

BREŠAR, Boštjan, HENNING, Michael A., KLAVŽAR, Sandi, RALL, Douglas F. Domination games played on graphs. Cham: Springer Nature, cop. 2021. X, 122 str. [COBISS-SI-ID 60317443]

KLAVŽAR, Sandi, MOLLARD, Michel. Daisy cubes and distance cube polynomial. European journal of combinatorics. Aug. 2019, vol. 80, str. 214-223. [COBISS-SI-ID 18659161]

HENNING, Michael A., KLAVŽAR, Sandi, RALL, Douglas F. The 4/5 upper bound on the game total domination number. Combinatorica. 2017, vol. 37, iss. 2, str. 223-251. [COBISS-SI-ID 18018137]

BUJTÁS, Csilla, KLAVŽAR, Sandi. Improved upper bounds on the domination number of graphs with minimum degree at least five. Graphs and combinatorics. 2016, vol. 32, iss. 2, str. 511-519. [COBISS-SI-ID 17630041]

KLAVŽAR, Sandi. Structure of Fibonacci cubes: a survey. Journal of combinatorial optimization. 2013, vol. 25, iss. 4, str. 505-522. [COBISS-SI-ID 16603737]

BREŠAR, Boštjan, KLAVŽAR, Sandi, RALL, Douglas F. Domination game and an imagination strategy. SIAM journal on discrete mathematics. 2010, vol. 24, no. 3, str. 979-991. [COBISS-SI-ID 15648089]