KZ
K.B. Zeven
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
For a family of graphs $\mathcal{H}$, the maximum size of a collection of graphs $\mathcal{F}$ for which the symmetric difference $\oplus$ of two distinct graphs $G_1, G_2$ has the property $G_1 \oplus G_2 \not\in \mathcal{H}$ (or $\in \mathcal{H}$) is denoted by $D_{\mathcal{H}}(n)$ (or $M_{\mathcal{H}}(n)$ respectively).
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
...
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
...
For a family of graphs $\mathcal{H}$, the maximum size of a collection of graphs $\mathcal{F}$ for which the symmetric difference $\oplus$ of two distinct graphs $G_1, G_2$ has the property $G_1 \oplus G_2 \not\in \mathcal{H}$ (or $\in \mathcal{H}$) is denoted by $D_{\mathcal{H}}(n)$ (or $M_{\mathcal{H}}(n)$ respectively).
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
For this thesis, we consider two $k$-colorings of a graph $G$ adjacent if one can recolor one into the other by changing the color of one vertex. The reconfiguration graph of a graph $G$ on $k$ colors $\mathcal{C}_{k}(G)$ is the graph for which the vertices are the $k$-colorings of $G$, and an edge is between two $k$-colorings if they are adjacent. We further investigate the diameter of the reconfiguration graph on $k$ colors: $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$.
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs. ...
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs. ...
For this thesis, we consider two $k$-colorings of a graph $G$ adjacent if one can recolor one into the other by changing the color of one vertex. The reconfiguration graph of a graph $G$ on $k$ colors $\mathcal{C}_{k}(G)$ is the graph for which the vertices are the $k$-colorings of $G$, and an edge is between two $k$-colorings if they are adjacent. We further investigate the diameter of the reconfiguration graph on $k$ colors: $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$.
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs.
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs.