M.Sc. Mathematics and Statistics
http://hdl.handle.net/10464/2883
2015-07-07T17:38:59ZEdge-choosability of Planar Graphs
http://hdl.handle.net/10464/5004
Edge-choosability of Planar Graphs
Mashhadi Avaz Tehrani, Hediyeh
According to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without 7-cycles with ∆(G)≠5,6 , or without adjacent 4-cycles with ∆(G)≠5, or with no 3-cycles adjacent to 5-cycles, then G is edge-(∆ + 1)-choosable.
2013-09-26T00:00:00ZRings, Group Rings, and Their Graphs
http://hdl.handle.net/10464/4958
Rings, Group Rings, and Their Graphs
Aliniaeifard, Farid
We associate some graphs to a ring R and we investigate the interplay between the ring-theoretic properties of R and the graph-theoretic properties of the graphs associated to R. Let Z(R) be the set of zero-divisors of R. We define an undirected graph ᴦ(R) with nonzero zero-divisors as vertices and distinct vertices x and y are adjacent if xy=0 or yx=0. We investigate the Isomorphism Problem for zero-divisor graphs of group rings RG. Let Sk denote the sphere with k handles, where k is a non-negative integer, that is, Sk is an oriented surface of genus k. The genus of a graph is the minimal integer n such that the graph can be embedded in Sn. The annihilating-ideal graph of R is defined as the graph AG(R) with the set of ideals with nonzero annihilators as vertex such that two distinct vertices I and J are adjacent if IJ=(0). We characterize Artinian rings whose annihilating-ideal graphs have finite genus. Finally, we extend the definition of the annihilating-ideal graph to non-commutative rings.
2013-09-05T00:00:00ZAcyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles
http://hdl.handle.net/10464/4957
Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles
Ferreri, Susanna
The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.
2013-09-05T00:00:00ZResponse curves of deterministic and probabilistic cellular automata in one and two dimensions
http://hdl.handle.net/10464/3953
Response curves of deterministic and probabilistic cellular automata in one and two dimensions
Skelton, Andrew
One of the most important problems in the theory of cellular automata (CA) is
determining the proportion of cells in a specific state after a given number of time
iterations. We approach this problem using patterns in preimage sets - that is, the
set of blocks which iterate to the desired output. This allows us to construct a
response curve - a relationship between the proportion of cells in state 1 after niterations
as a function of the initial proportion. We derive response curve formulae
for many two-dimensional deterministic CA rules with L-neighbourhood. For all
remaining rules, we find experimental response curves. We also use preimage sets to
classify surjective rules. In the last part of the thesis, we consider a special class of
one-dimensional probabilistic CA rules. We find response surface formula for these
rules and experimental response surfaces for all remaining rules.
2012-04-02T00:00:00Z