MPŠ
MPŠ MP&Scaron MP&Scaron MP&Scaron Avtorji

Jožef Stefan
International
Postgraduate School

Jamova 39
SI-1000 Ljubljana
Slovenia

Phone: +386 1 477 31 00
Fax: +386 1 477 31 10
Email: info@mps.si

Search

Course Description

Selected Topics from Discrete Mathematics

Program

Information and Communication Technologies, second-level study programme

Lecturers:

prof. dr. Sandi Klavžar

Goals:

To present selected topic from contemporary discrete mathematics that have either already found applications or have a potential for applications in information-oommunication technologies.

Content:

1) Graph products
Basic properties. Some invariants on products (connectivity, domination.)

2) Model for interconnection networks
Hypercubes and their variants. Grid and torus graphs. Partial cubes, Hamming graphs and their applications. Fibonacci cubes.

3) Coding theory
Linear codes. Codes in graphs. 1-perfect codes in graphs. r-perfect codes in torus graphs.

4) Graph coloring
Frequency assignment problem. L(2,1)-colorings and generalizations.

Course literature:

• Biggs, Norman L. Discrete mathematics. Second edition. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1989.
• Gross, Jonathan L.; Yellen, Jay Graph theory and its applications. Second edition. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006.
• Imrich, W., Klavžar, S. Product graphs: structure and recognition, (Wiley-Intersciences series in discrete mathematics and optimization). New York [etc.]: J. Wiley & Sons, cop. 2000.
• Ling, San; Xing, Chaoping Coding theory. A first course. Cambridge University Press, Cambridge, 2004.
• Matoušek, J.; Nešetril, J. Invitation to discrete mathematics. The Clarendon Press, Oxford University Press, New York, 1998.

Significant publications and references:

• KLAVŽAR, Sandi, PETERIN, Iztok, YERO, Ismael G. Graphs that are simultaneously efficient open domination and efficient closed domination graphs. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2017, vol. 217, iss. 3, str. 613-621. http://dx.doi.org/10.1016/j.dam.2016.09.027. [COBISS.SI-ID 17827673], [JCR, SNIP, Scopus do 17. 12. 2016: št. citatov (TC): 0, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, KOŠMRLJ, Gašper, SCHMIDT, Simon. On graphs with small game domination number. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2016, vol. 10, no. 1, str. 30-45. http://dx.doi.org/10.2298/AADM160207003K. [COBISS.SI-ID 17666137], [JCR, SNIP, WoS do 1. 11. 2016: št. citatov (TC): 1, čistih citatov (CI): 0, Scopus do 30. 11. 2016: št. citatov (TC): 1, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, RHO, Yoomi. On the Wiener index of generalized Fibonacci cubes and Lucas cubes. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2015, vol. 187, str. 155-160. http://dx.doi.org/10.1016/j.dam.2015.02.002. [COBISS.SI-ID 17295961], [JCR, SNIP, WoS do 25. 12. 2016: št. citatov (TC): 4, čistih citatov (CI): 3, Scopus do 28. 11. 2016: št. citatov (TC): 5, čistih citatov (CI): 3]
• KLAVŽAR, Sandi, SHAO, Zehui. Local colorings of Cartesian product graphs. International journal of computer mathematics, ISSN 0020-7160, 2015, vol. 92, no. 4, str. 694-699. http://dx.doi.org/10.1080/00207160.2014.918609. [COBISS.SI-ID 17225049], [JCR, SNIP, WoS do 20. 2. 2015: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 20. 2. 2015: št. citatov (TC): 0, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, MOLLARD, Michel. Asymptotic properties of Fibonacci cubes and Lucas cubes. Annals of combinatorics, ISSN 0218-0006, 2014, vol. 18, no. 3, str. 447-457. http://dx.doi.org/10.1007/s00026-014-0233-x. [COBISS.SI-ID 17087065], [JCR, SNIP, WoS do 27. 11. 2016: št. citatov (TC): 5, čistih citatov (CI): 1, Scopus do 27. 11. 2016: št. citatov (TC): 5, čistih citatov (CI): 1]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. Computing distance moments on graphs with transitive Djoković-Winkler relation. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2014, vol. 166, str. 269-272. http://dx.doi.org/10.1016/j.dam.2013.10.006. [COBISS.SI-ID 16893273], [JCR, SNIP, WoS do 2. 5. 2015: št. citatov (TC): 1, čistih citatov (CI): 1, Scopus do 14. 10. 2015: št. citatov (TC): 1, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, RHO, Yoomi. Fibonacci (p,r)-cubes as Cartesian products. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2014, vol. 328, str. 23-26. http://dx.doi.org/10.1016/j.disc.2014.03.027. [COBISS.SI-ID 16970585], [JCR, SNIP, WoS do 30. 6. 2014: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 7. 9. 2015: št. citatov (TC): 0, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. On the difference between the revised Szeged index and the Wiener index. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2014, vol. 333, str. 28-34. http://dx.doi.org/10.1016/j.disc.2014.06.006. [COBISS.SI-ID 17065817], [JCR, SNIP, WoS do 3. 7. 2016: št. citatov (TC): 2, čistih citatov (CI): 2, Scopus do 28. 12. 2016: št. citatov (TC): 3, čistih citatov (CI): 3]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. Wiener index in weighted graphs via unification of [Theta] [sup] [ast]-classes. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 71-76. http://dx.doi.org/10.1016/j.ejc.2013.04.008. [COBISS.SI-ID 16768089], [JCR, SNIP, WoS do 25. 12. 2016: št. citatov (TC): 12, čistih citatov (CI): 8, Scopus do 17. 11. 2016: št. citatov (TC): 10, čistih citatov (CI): 5]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. Improved bounds on the difference between the Szeged index and the Wiener index of graphs. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 39, str. 148-156. http://dx.doi.org/10.1016/j.ejc.2014.01.005. [COBISS.SI-ID 16861017], [JCR, SNIP, WoS do 3. 7. 2016: št. citatov (TC): 6, čistih citatov (CI): 5, Scopus do 28. 12. 2016: št. citatov (TC): 7, čistih citatov (CI): 6]
• KLAVŽAR, Sandi, MA, Meijie. The domination number of exchanged hypercubes. Information processing letters, ISSN 0020-0190. [Print ed.], 2014, vol. 114, iss. 4, str. 159-162. http://dx.doi.org/10.1016/j.ipl.2013.12.005. [COBISS.SI-ID 16819289], [JCR, SNIP, WoS do 3. 6. 2016: št. citatov (TC): 5, čistih citatov (CI): 4, Scopus do 27. 11. 2016: št. citatov (TC): 9, čistih citatov (CI): 8]
• KLAVŽAR, Sandi, MA, Meijie. Average distance, surface area, and other structural properties of exchanged hypercubes. The journal of supercomputing, ISSN 0920-8542, 2014, vol. 69, no. 1, str. 306-317. http://dx.doi.org/10.1007/s11227-014-1153-6. [COBISS.SI-ID 17064793], [JCR, SNIP, WoS do 3. 2. 2016: št. citatov (TC): 2, čistih citatov (CI): 2, Scopus do 3. 5. 2016: št. citatov (TC): 2, čistih citatov (CI): 2]

Examination:

Seminar (20%)
Oral exam (80%)

Students obligations:

Seminar and oral exam.

Links: