Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017. Book of Abstracts Editors: dr. Boštjan Brešar dr. Tanja Gologranc dr. Marko Jakovac dr. Iztok Peterin Tim Kos Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts Editors: dr. Boštjan Brešar dr. Tanja Gologranc dr. Marko Jakovac dr. Iztok Peterin Tim Kos November 2017 Title: Subtitle: Editors: Review: Proofreading: Technical editor: Cover design: Conference: Organized by: Co-organized by: Program Committee: Organizing Committee: Co-published by / Izdajateljica Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts prof. Boštjan Brešar, Ph.D., (University of Maribor, Faculty of Natural Sci­ ences and Mathematics), assist. prof. Tanja Gologranc, Ph.D., (University of Maribor, Faculty of Natural Sciences and Mathematics), asist. prof. Marko Jakovac, Ph.D., (University of Maribor, Faculty of Natural Sciences and Mathematics), assoc. prof. Iztok Peterin (University of Maribor, Faculty of Electrical Engi­neering and Computer Science), assist. Tim Kos (Institute of Mathematics, Physics and Mechanics, Ljubljana) prof. Aleksander Vesel, PhD., (University of Maribor, Faculty of Natural Sciences and Mathematics) assoc. prof. Iztok Peterin, Ph.D., (University of Maribor, Faculty of Electrical Engineering and Computer Science) Tim Kos (Institute of Mathematics, Physics and Mechanics, Ljubljana) Tim Kos (Institute of Mathematics, Physics and Mechanics, Ljubljana) 30th Ljubljana -Leoben Graph Theory Seminar University of Maribor, Faculty of Natural Sciences and Mathematics Institute of Mathematics, Physics and Mechanics, Ljubljana prof. dr. Boštjan Brešar (University of Maribor, Faculty of Natural Sci­ ences and Mathematics), O. Univ. Prof. Dr. phil. Wil.ed Imrich (Monta­nuniversität Leoben, Department Mathematics and Information Technology), prof. dr. Sandi Klavžar (University of Ljubljana, Faculty of Mathematics and Physics), assoc. prof. dr. Iztok Peterin (University of Maribor, Faculty of Electrical Engineering and Computer Science). prof. dr. Boštjan Brešar (University of Maribor, Faculty of Natural Sciences and Mathematics), assist. prof. dr. Tanja Gologranc (University of Maribor, Faculty of Natural Sciences and Mathematics), asist. prof. dr. Marko Jako­vac (University of Maribor, Faculty of Natural Sciences and Mathematics), assoc. prof. dr. Iztok Peterin (University of Maribor, Faculty of Electrical En­gineering and Computer Science), assist. Tim Kos (Institute of Mathematics, Physics and Mechanics, Ljubljana). University of Maribor, Faculty of Natural Sciences and Mathematics Koroška cesta 160, 2000 Maribor, Slovenia tel. +386 2 229 38 44, fax +386 2 251 81 80 http://www.fnm.um.si, dekanat.fnm@um.si First published in 2017 by / Založnik University of Maribor Press Slomškov trg 15, 2000 Maribor, Slovenia tel. +386 2 250 42 42, fax +386 2 252 32 45 http://press.um.si, zalozba@um.si Edition: 1st Available at: http://press.um.si/index.php/ump/catalog/book/295 Published in: November 2017 @University of Maribor Press All rights reserved. No part of this book may be reprinted or reproduced or utilized in any form or by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying and recording, or in any information storage or retrieval system, without permission in writing from the publisher. CIP -Kataložni zapis o publikaciji Univerzitetna knjižnica Maribor 519.17(0.034.2) LJUBLJANA -Leoben Graph Theory Seminar (30 ; 2017 ; Maribor) Book of abstracts [Elektronski vir] / 30th Ljubljana -Leoben Graph Theory Seminar, Maribor, 13. – 15. September, 2017 ; editors Boštjan Brešar . . . [et al.]. -1st ed. -El. zbornik. -Maribor : University of Maribor Press, 2017 Način dostopa (URL): http://press.um.si/index.php/ump/catalog/book/295 ISBN 978-961-286-113-1 doi: 10.18690/978-961-286-113-1 1. Brešar, Boštjan COBISS.SI-ID 93440513 ISBN: 978-961-286-113-1 (PDF) DOI: https://doi.org/10.18690/978-961-286-113-1 Price: Free copy For publisher: prof. Igor Tičar, Ph.D., Rector (University of Maribor) DOI https://doi.org/10.18690/978-961-286-113-1 ISBN 978-961-286-113-1 @2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts Boštjan Brešar, Tanja Gologranc, Marko Jakovac, Iztok Peterin & Tim Kos AbstractThe booklet contains the abstracts of the talks given at the 30th Ljubljana-Leoben Graph Theory Seminar that was held at the Faculty of Natural Sciences and Mathematics in Maribor between 13-15 September, 2017. The seminar attracted more than 30 participants from eight countries, all of which are researchers in di.erent areas of graph theory. The topics of the talks encompass a wide range of contemporary graph theory research, notably, various types of graph colorings (b-coloring, packing coloring, edge colorings), graph domi­nation (rainbow domination, Grundy domination, graph security), distinguishing problems, algebraic graph theory, graph algorithms, chemical graph theory, coverings, matchings and also some classical extremal problems. Beside the abstracts of the four invited speakers (Csilla Bujtás, Přemysl Holub, Jakub Przybyło, Zsolt Tuza), the booklet contains also the abstracts of 18 contributed talks given at the event. Keywords: • mathematics • graph theory • Ljubljana-Leoben seminar • Maribor • Slovenia Correspondence address: Boštjan Brešar, Ph.D., Full Professor, University of Maribor, Fac­ulty of Natural Sciences and Mathematics, Koroška cesta 160, 2000 Maribor, Slovenia, e-mail: bost­jan.bresar@um.si. Tanja Gologranc, Ph.D., Assistant Professor, University of Maribor, Faculty of Natural Sciences and Mathematics, Koroška cesta 160, 2000 Maribor, Slovenia, e-mail: tanja.gologranc1@um.si. Marko Jakovac, Assistant Professor, University of Maribor, Faculty of Natural Sciences and Mathemat­ics, Koroška cesta 160, 2000 Maribor, Slovenia, e-mail: marko.jakovac@um.si. Iztok Peterin, Ph.D., Associate Professor, University of Maribor, Faculty of Electrical Engineering and Computer Science, Ko­roška cesta 46, 2000 Maribor, Slovenia, e-mail: iztok.peterin@um.si. Tim Kos, Assistant, Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia, e-mail: tim.kos@imfm.si. DOI https://doi.org/10.18690/978-961-286-113-1 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 iii Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Seminar Ljubljana -Leoben s področja teorije grafov Maribor, 13.-15. September, 2017 Knjiga povzetkov Boštjan Brešar, Tanja Gologranc, Marko Jakovac, Iztok Peterin & Tim Kos Povzetek Knjižica vsebuje povzetke predavanj, ki so bili predstavljeni na 30. seminarju Ljubljana-Leoben s področja teorije grafov. Seminar je potekal na Fakulteti za naravoslovje in matematiko v Mariboru med 13. in 15. septembrom 2017. Seminar je privabil več kot 30 udeležencev iz osmih držav. Udeleženci so raziskovalci, ki pokrivajo različna področja teorije grafov. Teme predavanj obsegajo veliko področij sodobne teorije grafov, predvsem različne tipe barvanj grafov (b-barvanja, pakirna barvanja, barvanja povezav), dominacije na gra.h (mavrična dominacija, Grundyjeva dominacija, varne množice na gra.h), razlikovalne probleme, algebraično teorijo grafov, algoritme na gra.h, kemijsko teorijo grafov, pokritja, prirejanja in klasične ekstremalne probleme. Knjižica poleg povzetkov štirih vabljenih preda­vateljev (Csilla Bujtás, Přemysl Holub, Jakub Przybyło, Zsolt Tuza), vsebuje tudi 18 drugih povzetkov, ki so bili predstavljeni na seminarju. Ključne besede: • matematika • teorija grafov • Ljubljana-Leoben seminar • Maribor • Slovenija Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Welcome The Ljubljana-Leoben or Leoben-Ljubljana series of graph theory seminars celebrates its 30th seminar. What began in the early 1980s as informal meetings of a handful of graph theorists from Slovenia and Austrian Styria has become, in the following decades, a successful meeting point for an ever growing number of central European researches in this .eld of mathematics. This year’s seminar will be held in Maribor for the .rst time in its history. Graph theory is one of the strongest mathematical areas of the University of Maribor, and is one of the keys that the University of Maribor was ranked on the QS World University Rankings 2017 among the 400 top universities in the .eld of mathematics. The graph theory community in Maribor has bene.ted a lot from connections with Austrian mathematics. In particular, the Ljubljana-Leoben seminar was a starting point for many young graph theorists who gave their .rst talks to an international audience at that seminar. The meeting is organized by the Faculty of Natural Sciences and Mathematics at University of Maribor (FNM UM) in collaboration with the Institute of Mathematics, Physics and Mechanics (IMFM), and supported by graph theorists from several faculties of the University of Maribor. We wish you a pleasant stay in Maribor, and a lot of new ideas and mathematical results! Program committee: Boštjan Brešar Wilfried Imrich Sandi Klavžar Iztok Peterin Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. General information The 30th Ljubljana -Leoben Graph Theory Seminar takes place at the Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia. Program Committee: Boštjan Brešar (University of Maribor, Faculty of Natural Sciences and Mathematics), Wilfried Im­rich (Montanuniversität Leoben), Sandi Klavžar (University of Ljubljana, Faculty of Mathematics and Physics), Iztok Peterin (University of Maribor, Faculty of Electrical Engineering and Computer Science). Organizing Committee: Boštjan Brešar (University of Maribor, Faculty of Natural Sciences and Mathematics), Tanja Gologranc (University of Maribor, Faculty of Natural Sciences and Mathematics), Marko Jakovac (University of Maribor, Faculty of Natural Sciences and Mathematics), Tim Kos (Institute of Mathematics, Physics and Mechanics, Ljubljana), Iztok Peterin (University of Maribor, Faculty of Electrical Engineering and Computer Science). Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Organized by: University of Maribor, Faculty of Natural Sciences and Mathematics Co-organized by: Institute of Mathematics, Physics and Mechanics, Ljubljana Invited speakers: • Csilla Bujtás (University of Pannonia, Veszprém, Hungary) • Přemysl Holub (University of West Bohemia, Plzeń, Czech Republic) • Jakub Przybyło (AGH University, Krakow, Poland) • Zsolt Tuza (University of Pannonia, Veszprém, Hungary) Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Contents Welcome v General information vi Abstracts 1 On the b-chromatic number of proper interval graphs (Dragana Božović ) . . . . . . . . . . . 1 Packing and covering triangles (Csilla Bujtás) . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Packing coloring of Sierpiński-type graphs (Jasmina Ferme) . . . . . . . . . . . . . . . . . . . 3 Forbidden induced subgraphs (Přemysl Holub) . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Direct product of automorphism groups of digraphs (Wilfried Imrich) . . . . . . . . . . . . . 5 Secure sets in graphs (Marko Jakovac) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Mixed metric dimension of graphs (Aleksander Kelenc ) . . . . . . . . . . . . . . . . . . . . . 7 Distinguishing graphs of maximum valence 3 (Judith Kloas) . . . . . . . . . . . . . . . . . . 8 Grundy total domination number of bipartite k-regular graphs (Tim Kos) . . . . . . . . . . . 9 On k-rainbow independent domination in graphs (Tadeja Kraner Šumenjak ) . . . . . . . . . . 10 Breaking graph symmetries by edge colourings (Florian Lehner ) . . . . . . . . . . . . . . . . 11 Edge-colorings as edge-decompositions (Borut Lužar ) . . . . . . . . . . . . . . . . . . . . . . 12 Maximum number of colourings and Tomescu’s conjecture (Bojan Mohar ) . . . . . . . . . . . 13 Recognizing (generalized) Sierpiński graphs (Iztok Peterin) . . . . . . . . . . . . . . . . . . . 14 List neighbour set distinguishing edge colourings (Jakub Przybyło) . . . . . . . . . . . . . . . 15 Perfect matchings in regular highly cyclically edge-connected graphs (Edita Rollová) . . . . . 16 On k-arc-transitive digraphs (Norbert Seifter ) . . . . . . . . . . . . . . . . . . . . . . . . . . 17 On facial unique-maximum (edge-)coloring (Riste Škrekovski ) . . . . . . . . . . . . . . . . . 18 Distance-Based Molecular Descriptors and the Cut Method (Niko Tratnik ) . . . . . . . . . . 19 Classical extremal problems with additional degree constrains (Zsolt Tuza) . . . . . . . . . . . 20 (d, n)-packing colorings of in.nite lattices (Aleksander Vesel ) . . . . . . . . . . . . . . . . . . 21 The Hosoya Polynomial of Double Weighted Graphs (Janez Žerovnik ) . . . . . . . . . . . . . 22 Participant List 23 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Abstracts On the b-chromatic number of proper interval graphs Dragana Božović Abstract The b-chromatic number of a graph G, denoted .b(G), is the largest integer k such that G admits a proper k-coloring in which every color class contains at least one vertex that has a neighbor in each of the other color classes. In this work we concentrate on b-chromatic number of proper interval graphs. A natural upper bound for .b(G) is m-degree of a graph G which is the largest integer m(G) such that G has m(G) vertices of degree at least m(G) - 1. For several graph classes m(G) - 1 . .b(G) . m(G) holds. But that is not the case with proper interval graphs. Therefore we have developed some new tools that are applicable when .b(G) < m(G) - 1. In particular we determined a lower bound for .b(G) and several exact results. Joint work with Aleksander Kelenc, Iztok Peterin and Niko Tratnik. Keywords: vertex coloring, proper coloring, b-chromatic number, m-degree, proper interval graph Correspondence Address: Dragana Božović, Assistant, University of Maribor, Faculty of Electrical Engineering and Computer Science, Koroška cesta 46, 2000 Maribor, Slovenia, e-mail: dragana.bozovic@um.si DOI https://doi.org/10.18690/978-961-286-113-1.1 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Packing and covering triangles Csilla Bujtás Abstract In a graph G, a triangle packing is a set of pairwise edge-disjoint triangles, and a triangle covering is a set of edges which contains at least one edge from each triangle of the graph. The maximum size ..(G) of a triangle packing and the minimum size ..(G) of a triangle covering clearly satis.es ..(G) . 3..(G). It was conjectured by Zsolt Tuza in 1984 that the following stronger statement ..(G) . 2..(G) is also valid for every graph. For the complete graphs K4 and K5, the relation holds with equality as ..(K4) = 2, ..(K4) = 1, and ..(K5) = 4, ..(K5) = 2. Moreover, for every positive . there exists a K4-free graph G with ..(G) > (2 - .)..(G). Although the problem was extensively studied by many authors, the conjecture is still open. In fact, the best general upper bound which has been published so far is ..(G) . (3 - 3 )..(G). On the other hand, the conjecture is proved to be true on several graph classes, 23 and for some subclasses of K4-free graphs upper bounds better than 2..(G) have been established. In the talk, we survey the earlier results and discuss some recent ones. Keywords: triangle packing, triangle covering, complete graphs, K4-free graphs, planar graphs Correspondence Address: Csilla Bujtás, Ph.D., Associate Professor, University of Pannonia, De­partment of Computer Science and Systems Technology, Egyetem u. 10 Veszprém, Hungary, e-mail: bujtas@dcs.vein.hu DOI https://doi.org/10.18690/978-961-286-113-1.2 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Packing coloring of Sierpiński-type graphs Jasmina Ferme Abstract Let S(n, k), where n . 1, k . 1, be the Sierpiński graph of dimension n and base k, and S(G, n), n . 1, the generalized Sierpiński graph of G of dimension n. We prove, that for a .xed k, k . 4, the sequence (..(S(n, k)))n.N is unbounded from above. Further, generalized Sierpiński graphs of the other, connected graphs on 4 vertices are considered. The packing chromatic numbers of S(C4, n), S(P4, n) and S(K1,3, n) are given for each n . 1, and also for the generalized Sierpiński graph of K4 - e of dimensions 1, 2 and 3. In addition, lower and upper bounds for ..(S(K4 - e, n)), n . 4, and ..(S(paw, n)), n . 1, are presented. Finally, it is proven that the packing chromatic number of Sierpiński triangle graph of dimension n is at most 31 for any n . 1; moreover, the precise values for n . {1, 2, 3} are determined. Joint work with Boštjan Brešar. Keywords: Sierpiński graphs, generalized Sierpiński graphs, k-packing coloring, packing chromatic number, i-packing Correspondence Address: Jasmina Ferme, Assistant, University of Maribor, Faculty of Agriculture and Life Sciences, Pivola 10, 2311 Hoče, Slovenija, e-mail: jasmina.ferme@um.si DOI https://doi.org/10.18690/978-961-286-113-1.3 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Forbidden induced subgraphs Přemysl Holub AbstractBeineke in 1969 characterized the class of line graphs in terms of forbidden induced subgraphs. For given graphs G and H, G is said to be H-free if G does not contain an induced subgraph isomorphic to H. Analogously, for graphs H1, . . . , Hk, a graph G is (H1, . . . , Hk)-free if G contains none of H1, . . . , Hk as an induced subgraph. In the graph theory, various classes of graphs and several graph properties have been studied in terms of forbidden induced sugraphs. In this talk we focus on some of these classes and properties, which are characterized or at least have some connections to forbidden induced subgraphs, e.g. some hamiltonian properties and some graph colouring problems. Among others, we list some known results on forbidden pairs and triples implying hamiltonian properties, we discuss families of forbidden induced subgraphs for rainbow connection, and some forbidden pairs and triples for perfect graphs and some graph colouring parameters. Keywords: forbidden induced subgraphs characterization, line graphs, hamiltonian proper­ties, rainbow connection, perfect graphs Correspondence Address: Přemysl Holub, Ph.D., Assistant Professor, University of West Bohemia, Faculty of Applied Sciences, Univerzitni 8, 306 14 Plzen, Czech Republic, e-mail: holubpre@kma.zcu.cz DOI https://doi.org/10.18690/978-961-286-113-1.4 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Direct product of automorphism groups of digraphs Wilfried Imrich Abstract It is shown that, except for the in.nite family of permutation groups Sn × Sn, n . 2, and four other permutation groups, namely D4 × S2, D4 × D4, S4 × S2 × S2, and C3 × C3, the direct product of automorphism groups of two digraphs is itself the automorphism group of a digraph. In the course of the proof, for each set of conditions on the groups A and B that are considered, a speci.c digraph product is needed. Joint work with Mariusz Grech, Anna Dorota Krystek and Lukasz Jan Wojakowski, all from Wroclaw. Keywords: digraph, graph product, direct product, automorphism group, permutation group Correspondence Address: Wilfried Imrich, Ph.D., Emer. Professor, Montanuniversität Leoben, Department Mathematics and Information Technology, Franz Josef-Strasse 18, 8700 Leoben, Austria, e-mail: imrich@unileoben.ac.at DOI https://doi.org/10.18690/978-961-286-113-1.5 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Secure sets in graphs Marko Jakovac Abstract The concept of a secure set is a generalization of defensive alliances in graphs. Defensive alliances are related to the defense of a single vertex. However, in a general realistic settings, a defensive alliance should be formed so that any attack on the entire alliance or any subset of the alliance can be defended. In this sense, secure sets represent an attempt to develop a model of this situation. Given a graph G = (V , E) and a set of vertices S . V of G, the set S is a secure set if it can defend every attack of vertices outside of S, according to an appropriate de.nition of »attack« and »defense«. The minimum cardinality of a secure set in G is the security number s(G). In this talk several results will be presented on the security number of graphs and graph products. Joint work with Tanja Gologranc, Ismael González Yero, Dorota Kuziak and Iztok Peterin. Keywords: defensive alliances, secure set, security number, Cartesian product, lexico­graphic product Correspondence Address: Marko Jakovac, Ph.D., Assistant Professor, University of Maribor, Faculty of Natural Sciences and Mathematics, Koroška cesta 160, 2000 Maribor, Slovenia, e-mail: marko.jakovac@um.si DOI https://doi.org/10.18690/978-961-286-113-1.6 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Mixed metric dimension of graphs Aleksander Kelenc AbstractLet G = (V, E) be a connected graph. A vertex w . V distinguishes two elements (vertices or edges) x, y . E . V if dG(w, x) = dG(w, y). A set S of vertices in a connected graph G is a mixed metric generator for G if every two distinct elements (vertices or edges) of G are distinguished by some vertex of S. The smallest cardinality of a mixed metric generator for G is called the mixed metric dimension and is denoted by dimm(G). The problem of determining the mixed metric dimension of a graph is NP-hard in the general case. In this talk we will consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. The mixed metric dimension of some families of graphs and an upper bound with respect to the girth of a graph will be presented. Joint work with Ismael González Yero, Dorota Kuziak and Andrej Taranenko. Keywords: metric generator, locating set, metric basis, metric dimension, edge metric dimension, mixed metric dimension Correspondence Address: Aleksander Kelenc, Assistant, University of Maribor, Faculty of Electrical Engineering and Computer Science, Koroška cesta 46, 2000 Maribor, Slovenia, e-mail: aleksander.kelenc@um.si DOI https://doi.org/10.18690/978-961-286-113-1.7 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Distinguishing graphs of maximum valence 3 Judith Kloas Abstract How much colors do we need to color a graph such that the only color preserving automorphism is the identity? The smallest such quantity of colors is called the distin­guishing number. Since its introduction by Albertson and Collins more than 20 years ago, there has developed an extensive literature on this topic. We will present how we can color connected graphs G of maximum valence 3 and give results regarding its distinguishing number. Joint work with Svenja Hüning, Wilfried Imrich, Hannah Schreiber and Tom Tucker. Keywords: coloring, distinguishing number, canonical 2-coloring, maximum degree, girth Correspondence Address: Judith Kloas, Ph.D. Student, Graz University of Technology, Institute for Discrete Mathematics, Steyrergasse 30/III, 8010 Graz, Austria, e-mail: kloas@math.tugraz.at DOI https://doi.org/10.18690/978-961-286-113-1.8 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Grundy total domination number of bipartite k-regular graphs Tim Kos Abstract A sequence of vertices in a graph without isolated vertices G is called a total dominating sequence if every vertex in the sequence totally dominates at least one vertex that was not totally dominated by preceding vertices in the sequence and, at the end all vertices of G are totally dominated. The maximum length of a total dominating sequence is called the Grundy total domination number, .t (G), of G. gr It is proved that if G is bipartite k-regular graph of order n other than Kk,k , then .t (G) . gr (n + 2lk sequences in graphs. Discrete Math. 339 (2016), 1665–1676]. For k = 3 (resp. k = 4) 2 l - 4)/(k - 1) [B. Brešar, M. A. Henning and D. F. Rall. Total dominating and G not Kk,k , the above bound is 1 2 n (resp. 1 3 n). In this talk we will characterize the connected bipartite 3-regular and 4-regular graphs with equality in the above bound. Joint work with Graciela Nasini and Pablo Torres. Keywords: domination, total dominating sequence, Grundy total domination number, bi­partite graphs, regular graphs Correspondence Address: Tim Kos, Assistant, Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia, e-mail: tim.kos@imfm.si DOI https://doi.org/10.18690/978-961-286-113-1.9 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. On k-rainbow independent domination in graphs Tadeja Kraner Šumenjak Abstract In this talk, we de.ne a new graph invariant, called the k-rainbow independent domination number. Some bounds and exact values concerning this domination concept will be presented. As a main result, we study a sum Nordhaus-Gaddum-type result for 2-rainbow independent domination number. Joint work with Douglas F. Rall and Aleksandra Tepeh. Keywords: domination number, independent domination number, k-rainbow domination number, independent k-rainbow domination number, Nordhaus-Gaddum-type result Correspondence Address: Tadeja Kraner Šumenjak, Ph.D., Assistant Professor, University of Mari­bor, Faculty of Agriculture and Life Sciences, Pivola 10, 2311 Hoče, Slovenija, e-mail: tadeja.kraner@um.si DOI https://doi.org/10.18690/978-961-286-113-1.10 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Breaking graph symmetries by edge colourings Florian Lehner Abstract An (edge or vertex) colouring of a graph is said to be distinguishing, if it is not preserved by any automorphism apart from the identity. Tucker conjectured that if every automorphism of an in.nite locally .nite graph moves in.nitely many vertices, then there is a distinguishing vertex colouring with 2 colours. While this conjecture has been veri.ed in many special cases it is still wide open in its full generality. Recently, Pilsniak and Broere proposed an analogous conjecture for edge colourings. We prove this conjecture which also implies Tucker’s conjecture for line graphs. We also in­dicate, why the problem of .nding a distinguishing colouring is probably easier for edge colourings than for vertex colourings. Keywords: vertex coloring, edge coloring, distinguishing coloring, authomorphism, line graphs Correspondence Address: Florian Lehner, Ph.D., Research Fellow, University of Warwick, Math­ematics Institute, Gibbet Hill Rd, Coventry CV4 7AL, Great Britain, e-mail: mail@.orian-lehner.net DOI https://doi.org/10.18690/978-961-286-113-1.11 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Edge-colorings as edge-decompositions Borut Lužar Abstract An edge-coloring of a graph G can be viewed as an edge-decomposition, where the edges of each color class represent a subgraph H of G. Di.erent types of edge-colorings induce di.erent subgraphs. In an ordinary proper edge-coloring, for example, every subgraph H is a matching. In the talk, we will discuss several types of edge-colorings, each having the property of the corresponding chromatic index being bounded from above by a small constant. In particular, we will mainly, but not exclusively, focus on locally irregular edge-coloring, odd edge-coloring, and vertex-parity edge-coloring. In these colorings, each color class respectively induces a locally irregular graph, an odd graph, and a graph in which the parity of each vertex degree corresponds to a given initial parity signature on vertices. Apart from discussing basic results for these colorings, we will also show, how the aforementioned results have been used to improve upper bounds in (at .rst sight non-related) edge-coloring types. Joint work with Mirko Petruševski, Jakub Przybyło and Riste Škrekovski. Keywords: edge-coloring, edge-decomposition, locally irregular edge-coloring, odd edge-coloring, vertex-parity edge-coloring Correspondence Address: Borut Lužar, Ph.D., Assistant Professor, Faculty of Information Studies, Ljubljanska cesta 31a, 8000 Novo mesto, Slovenia, e-mail: borut.luzar@gmail.com DOI https://doi.org/10.18690/978-961-286-113-1.12 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Maximum number of colourings and Tomescu’s conjecture Bojan Mohar AbstractIt is proved that every connected graph G on n vertices with .(G) . 4 has at most k(k - 1)n-3(k - 2)(k - 3) k-colourings for every k . 4. Equality holds for some (and then for every) k if and only if the graph is formed from K4 by repeatedly adding leaves. This con.rms (a strengthening of) the 4-chromatic case of a long-standing conjecture of Tomescu [Le nombre des graphes connexes k-chromatiques minimaux aux sommets étiquetés, C. R. Acad. Sci. Paris 273 (1971), 1124–1126]. Proof methods may be of independent interest. In particular, one of our auxiliary results about list-chromatic polynomials solves a recent conjecture of Brown, Erey, and Li. Joint work with Fiachra Knox. Keywords: vertex coloring, chromatic number, k-coloring, Tomescu’s conjecture, list-chromatic polynomials Correspondence Address: Bojan Mohar, Ph.D., Full Professor, Simon Fraser University, Depart­ment of Mathematics, Burnaby, BC, V5A 1S6, Canada, e-mail: mohar@sfu.ca DOI https://doi.org/10.18690/978-961-286-113-1.13 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Recognizing (generalized) Sierpiński graphs Iztok Peterin Abstract Let H be an arbitrary graph with vertex set V (H) = [nH ] = {1, . . . , nH }. The generalized Sierpiński graph Sn H , n . N, is de.ned on the vertex set [nH ]n, two di.erent vertices u = un . . . u1 and v = vn . . . v1 being adjacent if and only if there exists an h . [n] such that • ut = vt, for t > h, • uh = vh and uhvh . E(H), and • ut = vh and vt = uh for t < h. If H is isomorphic to a complete graph Kt, then we speak about Sierpiński graph Sn . We Kt present an algorithm which recognize Sierpiński graphs Sn in O(|V (Sn )|1+1/n) time. A Kt Kt polynomial time algorithm is given for generalized Sierpiński graphs when H is a graph in which every edge is contained in a triangle and izomorphism problem for H is polynomial. We also describe how to derive a base graph H from an arbitrary Sn H . Joint work with Wilfried Imrich. Keywords: Sierpiński graphs, generalized Sierpiński graphs, recognition algorithm, com­plete graphs, base graph Correspondence Address: Iztok Peterin, Ph.D., Associate Professor, University of Maribor, Faculty of Electrical Engineering and Computer Science, Koroška cesta 46, 2000 Maribor, Slovenia, e-mail: iztok.peterin@um.si DOI https://doi.org/10.18690/978-961-286-113-1.14 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. List neighbour set distinguishing edge colourings Jakub Przybyło Abstract The colouring c is called adjacent vertex distinguishing if it is proper and Sc(u) = Sc(v) for every edge uv . E. It exists if G contains no isolated edges. The least number of colours in C necessary to provide such a colouring is then denoted by .. (G) and called a the adjacent vertex distinguishing edge chromatic number of G. Obviously, .. (G) . a ..(G) . ., while it was conjectured that .. (G) . . + 2 for every connected graph a G of order at least three di.erent from C5. Hatami proved that .. (G) . . + 300 for a every graph G with no isolated edges with . > 1020. Suppose that every edge e . E is endowed with a list of colours Le. The adjacent vertex distinguishing edge choice number of G (without isolated edges) is de.ned as the least k so that for every set of lists of size k associated to the edges of G we are able to choose colours from the respective lists to obtain an adjacent vertex distinguishing edge colouring of G, denoted by ch. (G). a Analogously, ch. (G) . ch.(G), while the best general result on the edge choosability a implies that ch.(G) 1 2 log4 .). A four-stage probabilistic argument granting = .+ O(. ch. a (G) = .+ O(. 1 2 log4 .) for the class of all graphs without isolated edges shall be presented. Joint work with Jakub Kwaśny. Keywords: edge coloring, adjacent vertex distinguishing coloring, adjacent vertex distin­guishing edge chromatic number, adjacent vertex distinguishing edge choice number, prob­abilistic method Correspondence Address: Jakub Przybyło, Ph.D., Associate Professor, AGH University of Science and Technology, Department of Mathematics, al. Mickiewicza 30, 30-059 Krakow Poland, e-mail: jakubprz@agh.edu.pl DOI https://doi.org/10.18690/978-961-286-113-1.15 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Perfect matchings in regular highly cyclically edge-connected graphs Edita Rollová Abstract For k . 0, let G be a d-regular cyclically (d - 1 + 2k)-edge-connected graph of even order. A leaf matching operation on G consists of removing a vertex of degree 1 together with its neighbour from G. We prove that for any given set X of d - 1 + k edges, there is no 1-factor of G avoiding X if and only if either an isolated vertex can be obtained by a series of leaf matching operations in G - X or G - X has an independent set that contains more than half of the vertices of G. This result generalises theorem of Plesník [J. Plesník, Connectivity of regular graphs and the existence of 1-factors, Mat. Časopis 22 (1972), 310-318.], who proved the special case k = 0. Joint work with Robert Lukotka. Keywords: regular graphs, perfect matching, leaf matching operation, independent set, 1-factor Correspondence Address: Edita Rollová, Ph.D., PostDoc, University of West Bohemia, Faculty of Applied Sciences, Univerzitni 8, 306 14 Plzen, Czech Republic, e-mail: rollova@ntis.zcu.cz DOI https://doi.org/10.18690/978-961-286-113-1.16 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. On k-arc-transitive digraphs Norbert Seifter Abstract For undirected graphs most of the problems concerning high symmetry are more or less solved. For digraphs the situation is much more complicated. We will present some results and open problems concerning k-arc-transitivity of in.nite locally .nite digraphs. The contents of the talk depends on the progress we make until September. Whatever we will present will be an outcome of the collaboration with A. Malnič, R. Möller, P. Potočnik and P. Šparl. Keywords: digraphs, k-arc, k-arc transitive digraphs, in.nite locally .nite digraphs, growth of a graph Correspondence Address: Norbert Seifter, Ph.D., Associate Professor, Montanuniversität Leoben, Department Mathematics and Information Technology, Franz Josef-Strasse 18, 8700 Leoben, Austria, e-mail: seifter@unileoben.ac.at DOI https://doi.org/10.18690/978-961-286-113-1.17 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. On facial unique-maximum (edge-)coloring Riste Škrekovski Abstract In the talk some results on facial unique-maximum (edge-)colorings will be pre­sented. Keywords: graph coloring, Four color theorem, planar graphs, facial unique-maximum chromatic number,outerplanar graphs Correspondence Address: Riste Škrekovski, Ph.D., Associate Professor, University of Ljubljana, Faculty of Mathematics and Physics, Jadranska 19. 1000 Ljubljana, Slovenia, e-mail: skrekovski@gmail.com DOI https://doi.org/10.18690/978-961-286-113-1.18 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Distance-Based Molecular Descriptors and the Cut Method Niko Tratnik Abstract Theoretical molecular structure-descriptors (also called topological indices) are usually graph invariants calculated based on the molecular graph of a chemical compound. In the talk, some recent results on the cut method for some distance-based molecular descriptors will be presented. The cut method is a powerful tool for the investigation of such graph invariants. We will show how the cut method can be used to compute the (edge-)Wiener index, the (edge-)Szeged index, and the PI index of benzenoid systems in (sub-)linear time. Moreover, it will be shown that the problem of calculating the Szeged index of a partial cube can be reduced to the problem of calculating the Szeged indices of weighted quotient graphs with respect to a partition coarser than .-partition. Finally, a method for computing the edge-hyper-Wiener index of partial cubes will be demonstrated. Joint work with Matevž Črepnjak, Aleksander Kelenc and Sandi Klavžar. Keywords: Distance-Based Molecular Descriptors, Cut method, (edge-)Wiener index, (edge­)Szeged index, PI index Correspondence Address: Niko Tratnik, Ph.D. Student, University of Maribor, Faculty of Natural Sciences and Mathematics, Koroška cesta 160, 2000 Maribor, Slovenia, e-mail: niko.tratnik@gmail.com DOI https://doi.org/10.18690/978-961-286-113-1.19 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Classical extremal problems with additional degree constrains Zsolt Tuza Abstract Two fundamental results in extremal graph theory are Ramsey’s theorem and Turán’s theorem. Starting from the early 1990’s, several of their variants involving conditions on vertex degrees appeared. We survey those works, and also propose a new approach which opens an area for further research. All new results are joint work with Yair Caro. Keywords: Ramsey’s theorem, Turán’s theorem, vertex degree, singular set, singular Ram­sey number Correspondence Address: Zsolt Tuza, Ph.D. Full Professor, University of Pannonia, Department of Computer Science and Systems Technology, Egyetem u. 10, Veszprém, Hungary, e-mail: tuza@dcs.uni-pannon.hu DOI https://doi.org/10.18690/978-961-286-113-1.20 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. (d, n)-packing colorings of in.nite lattices Aleksander Vesel AbstractFor a nondecreasing sequence of integers S = (s1, s2, . . .) an S-packing k-coloring of a graph G is a mapping from V (G) to {1, 2, . . . , k} such that vertices with color i . {1, 2, . . . , k} have pairwise distance greater than si. A natural restriction of this concept obtained by setting si = d + li-1 J is called a (d, n)-packing coloring of a graph G. The n smallest integer k for which there exists a (d, n)-packing coloring of G is called the (d, n)­packing chromatic number of G. We study (d, n)-packing chromatic colorings of several lattices including the in.nite square, hexagonal, triangular, eight-regular, octagonal and two-row square lattice. Joint work with Danilo Korže. Keywords: k-coloring, i-packing, packing chromatic number, S-packing chromatic number, (d, n)-packing soloring, in.nite lattices Correspondence Address: Aleksander Vesel, Ph.D., Full Professor, University of Maribor, Faculty of Natural Sciences and Mathematics, Koroška cesta 160, 2000 Maribor, Slovenia, e-mail: aleksander.vesel@um.si DOI https://doi.org/10.18690/978-961-286-113-1.21 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. The Hosoya Polynomial of Double Weighted Graphs Janez Žerovnik Abstract The modi.ed Hosoya polynomial of double weighted graphs, i.e. edge and vertex weighted graphs, is introduced that enables derivation of closed expressions for Hosoya polynomial of some special graphs including unicyclic graphs. Furthermore, the Hosoya polynomial is given as a sum of edge contributions generalizing well known analogous results for the Wiener number. A linear algorithm for computing the Hosoya polynomial on cactus graphs is provided. Hosoya polynomial is extensively studied in chemical graph theory, and in particular its weighted versions have interesting applications in theory of communication networks. Joint work with Tina Novak and Darja Rupnik Poklukar. Keywords: Hosoya Polynomial, double weighted graphs, unicyclic graphs, Wiener number, cactus graphs Correspondence Address: Janez Žerovnik, Ph.D., Full Professor, University of Ljubljana, Faculty Of Mechanical Engineering, Aškerčeva 6, 1000 Ljubljana, Slovenia, e-mail: janez.zerovnik@fs.uni-lj.si DOI https://doi.org/10.18690/978-961-286-113-1.22 ISBN 978-961-286-113-1 @c2017 University of Maribor Press Available at: http://press.um.si/index.php/ump/catalog/book/295 Ljubljana -Leoben Graph Theory Seminar Maribor, 13.-15. September, 2017 Book of Abstracts B. Brešar, T. Gologranc, M. Jakovac, I. Peterin & T. Kos. Participant List • Dragana Božović (dragana.bozovic@um.si), • Boštjan Brešar (bostjan.bresar@um.si), • Csilla Bujtás (bujtas@dcs.vein.hu), • Jasmina Ferme (jasmina.ferme1@um.si), • Tanja Gologranc (tanja.gologranc1@um.si), • Přemysl Holub (holubpre@kma.zcu.cz), • Wilfried Imrich (imrich@unileoben.ac.at), • Marko Jakovac (marko.jakovac@um.si), • Aleksander Kelenc (aleksander.kelenc@um.si), • Sandi Klavžar (sandi.klavzar@fmf.uni-lj.si), • Judith Kloas (kloas@math.tugraz.at), • Tim Kos (tim.kos@imfm.si), • Tadeja Kraner Šumenjak (tadeja.kraner@um.si), • Florian Lehner (mail@.orian-lehner.net), • Borut Lužar (borut.luzar@gmail.com), • Bojan Mohar (mohar@sfu.ca), • Iztok Peterin (iztok.peterin@um.si), • Jakub Przybyło (jakubprz@agh.edu.pl), • Polona Repolusk (polona.repolusk@um.si), • Edita Rollová (rollova@ntis.zcu.cz), • Norbert Seifter (seifter@unileoben.ac.at), • Riste Škrekovski (skrekovski@gmail.com), • Simon Špacapan (simon.spacapan@gmail.com), • Daša Štesl (dasa.stesl@gmail.com), • Andrej Taranenko (andrej.taranenko@um.si), • Aleksandra Tepeh (aleksandra.tepeh@gmail.com) • Niko Tratnik (niko.tratnik@gmail.com), • Zsolt Tuza (tuza@dcs.uni-pannon.hu), • Aleksander Vesel (aleksander.vesel@um.si), • Janez Žerovnik (janez.zerovnik@fs.uni-lj.si), • Petra Žigert Pleteršek (petra.zigert@um.si).