DMS Combinatorics Seminar

Speaker: Andrei Pavelescu  (University of South Alabama)

Title: Topological Properties of Graphs and Connected Domination

Abstract: The connected domination number \(\gamma_c(G)\) of \(G\) is the minimum cardinality of dominating sets \(S\) of \(G\) which induces a connected subgraph \(G[S]\) of \(G\). We present some sharp bounds for \(\gamma_c(G)\), together with some open questions. We show how the connected domination can be used to establish results about topological properties of graphs and their complements. A graph \(G\) is called bi-knotlessly embeddable (bi-nIK), if both \(G\) and its complement, \(\overline{G}\), admit an embedding in \(\mathbb{R}^3\) with every cycle represented by a trivial knot. By size arguments, for large enough order \(n\), the complete graph \(K_n\) cannot be bi-nIK. We are asking for the smallest order \(n\), such that \(K_n\) is not bi-nIK. We prove that every graph of order 15 or more cannot be bi-nIK.