Graph Theory: structural properties, labelings, and connections to applications

    The thickness of a graph is the minimum number of planar graphs into which the edges of G can be partitioned. A graph is thickness-$k$ if the minimum number of planar graphs into which the edges of G can be partitioned is $k$.

    For graphs $G$ and $H$, a covering map $f: V(H) \rightarrow V(G)$ is a surjection and a local isomorphism, that is, the neighborhood of a vertex $H$ in $G$ is mapped one-to-one onto the neighborhood of $f(v)$ in $G$. When such a mapping exists, we say that $H$ is a lift of $G$. The lift’s properties reflect the properties of the base graph. We want to consider properties such as having a certain labeling and a power dominating set.

    Let $d < k < \binom{n}{2}$ and let $G$ be a bipartite graph with partite sets $X$ and $Y$ where the vertices in $X$ correspond to all possible $d$ subsets of $[n]$ and the vertices in $Y$ correspond to all possible $k$ subsets of $[n]$. For $x \in X$ and $y \in Y$, the edge $xy \in E(G)$ if $l(x) \subseteq l(y)$ where $l(x)$ and $l(y)$ are the subsets of $[n]$ that correspond to $x$ and $y$, respectively.

    The homomorphisms of a graph $G$ give information on various invariants of $G$. For example, a $k$-coloring of $G$ is equivalent to a homomorphism $G \rightarrow K_k$. For a given tree $T$, we consider the set of homomorphisms $T \rightarrow G$. Let $S$ be the set of homomorphisms $T \rightarrow G$. It is known that star graphs admit the maximum cardinality of $S$.