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.