Raziskovalni matematični seminar - Arhiv
28.11.2011 Lecturer: dr. Štefko Miklavič
Title: Automorphism groups of the "Rose-window" graphs which are not edge-transitive.
Download the slides from the talk here: DOWNLOAD!
21.11.2011 Lecturer: Ademir Hujdurović
Title: Quasi m-Cayley graphs
14.11.2011 Lecturer: dr. Martin Milanič
Title: Hereditary efficiently dominatable graphs
Abstract: An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. It is NP-complete to determine whether a given graph contains an efficient dominating set. We study the class of hereditary
efficiently dominatable graphs, that is, graphs every induced subgraph of which contains an efficient dominating set. Based on a decomposition theorem for (bull, fork, C_4)-free graphs, we derive the forbidden induced subgraph characterization of hereditary efficiently dominatable graphs. We also present a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs, by reducing the problem to the maximum weight independent set problem in claw-free graphs.
DOWNLOAD THE SLIDES FROM THE TALK: DOWNLOAD!