Raziskovalni matematični seminar

Predavanje bo v Angleščini.

Vljudno vabljeni k udeležbi na predavanju!

 

Title: Graphs of separability at most two: structural characterizations and their consequences

Abstract: We introduce graphs of separability at most k as graphs in which every two non-adjacent vertices can be separated by a set of at most k other vertices. Graphs of separability at most k arise in connection with the parsimony haplotyping problem from computational biology. For k = 0 or k = 1, the only connected graphs of separability at most k are complete graphs and block graphs, respectively. For values of k greater than 2, graphs of separability at most k form a rich class of graphs containing all graphs of maximum degree k.

We prove several characterizations of graphs of separability at most 2, which generalize complete graphs, cycles and trees. The main result is that every connected graph of separability at most 2 can be constructed from complete graphs and cycles by pasting along vertices or edges, and vice-versa, every graph constructed this way is of separability at most 2. The structure theorem has nice algorithmic implications – some of which cannot be extended to graphs of higher separability – however certain optimization problems remain intractable on graphs of separability 2. Finally, we characterize graphs of separability at most 2 in terms of minimal forbidden induced subgraphs and minimal forbidden induced minors.