M.Sc. Mathematics and Statisticshttp://hdl.handle.net/10464/28832016-08-25T04:30:17Z2016-08-25T04:30:17ZA game-theoretic network formation modelAtabati, Omidhttp://hdl.handle.net/10464/55192016-02-17T19:38:00Z2014-07-23T00:00:00ZA game-theoretic network formation model
Atabati, Omid
We study the dynamics of a game-theoretic network formation
model that yields large-scale small-world networks. So far,
mostly stochastic frameworks have been utilized to explain
the emergence of these networks. On the other hand, it is
natural to seek for game-theoretic network formation models in
which links are formed due to strategic behaviors of individuals,
rather than based on probabilities. Inspired by Even-Dar and
Kearns (2007), we consider a more realistic model in which the
cost of establishing each link is dynamically determined during
the course of the game. Moreover, players are allowed to put
transfer payments on the formation of links. Also, they must
pay a maintenance cost to sustain their direct links during the
game. We show that there is a small diameter of at most 4 in
the general set of equilibrium networks in our model. Unlike
earlier model, not only the existence of equilibrium networks is
guaranteed in our model, but also these networks coincide with
the outcomes of pairwise Nash equilibrium in network formation.
Furthermore, we provide a network formation simulation that
generates small-world networks. We also analyze the impact of
locating players in a hierarchical structure by constructing a
strategic model, where a complete b-ary tree is the seed network.
2014-07-23T00:00:00ZEdge-choosability of Planar GraphsMashhadi Avaz Tehrani, Hediyehhttp://hdl.handle.net/10464/50042015-08-06T04:23:37Z2013-09-26T00:00:00ZEdge-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 GraphsAliniaeifard, Faridhttp://hdl.handle.net/10464/49582015-03-14T04:42:17Z2013-09-05T00:00:00ZRings, 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 CyclesFerreri, Susannahttp://hdl.handle.net/10464/49572015-08-06T04:23:37Z2013-09-05T00:00:00ZAcyclic 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:00Z