No description available.

Learning maps have been used to represent student knowledge for many years. These maps are usually hand made by experts in a given domain. However, these hand-made maps have not been found to be predictive of student performance. Several methods have been proposed to find bet-ter fitting learning maps. These methods include the Learning Factors Analysis (LFA) model and the Rule-space method. In this thesis we report on the application of one of the proposed operations in the LFA method to a small section of a skill graph and develop a greedy search algorithm for finding better fitting models for this graph. Additionally an investigation of the factors that influence the search for better data fitting models using the proposed algorithm is reported. We also present an empirical study in which PLACEments, an adaptive testing system that employs a skill graph, is modified to test the strength of prerequisite skill links in a given learning map and propose a method for refining learning maps based on those findings. It was found that the proposed greedy search algorithm performs as well as an original skill graph but with a smaller set of skills in the graph. Additionally it was found that, among other factors, the number of unnecessary skills, the number of items in the graph, and the guess and slip rates of the items tagged with skills in the graph have an impact on the search. Further, the size of the evaluation data set impacts the search. The more data there is for the search, the more predictive the learned skill graph. Additionally, PLACEments, an adaptive testing feature of ASSISTments, has been found to be useful for refining skill graphs by detecting the strengths of prerequisite links between skills in a graph.

The abelian sandpile model, or chip firing game, is a cellular automaton on finite directed graphs often used to describe the phenomenon of self organized criticality. Here we present a thorough introduction to the theory of sandpiles. Additionally, we define a symmetric sandpile configuration, and show that such configurations form a subgroup of the sandpile group. Given a graph, we explore the existence of a quotient graph whose sandpile group is isomorphic to the symmetric subgroup of the original graph. These explorations are motivated by possible applications to counting the domino tilings of a 2n × 2n grid.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.

A star graph consists of a vertex to which a set of edges are connected. Such an object can be used to, among other things, model the electromagnetic properties of quantum wires. A scalar field theory is constructed on the star graph and its properties are investigated. It turns out that there exist Kirchoff's rules for the conserved charges in the system leading to restrictions of the possible type of boundary conditions at the vertex. Scale invariant boundary conditions are investigated in detail. / En stjärngraf består av en nod på vilken vilken ett antal kanter är anslutna. Ett sådant objekt kan bland annat användas till att modellera de elektromagnetiska egenskaperna hos kvanttrådar. En skalärfältsteori konstrueras på stjärngrafen och dess egenskaper undersöks. Det visar sig att det exisisterar en typ av Kirchoffs lagar för de konserverade laddningarna i systemet. Detta leder till restriktioner på vilka randvillkor som är möjliga vid noden. Skalinvarianta randvillkor undersöks i detalj.

This thesis discusses the game chromatic number of Halin graphs. We shall prove that with a few exceptions, all Halin graphs have game chromatic number 4.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

Given a signed graph (G, Σ) with an embedding on a surface S, we are interested in "extending" (G, Σ) by adding edges and splitting vertices, such that the resulting graph has no embedding on S. We show (assuming 3-connectivity for (G, Σ)) that there are a small number of minimal extensions of (G, Σ) with no such embedding, and describe them explicitly. We also give conditions, for several surfaces S, for an embedding of a signed graph on S to extend uniquely. These results find application in characterizing the signed graphs with no odd-K_5 minor.

A 2-dipath k-colouring of an oriented graph G is an assignment of k colours, 1,2, . . . , k, to the vertices of G such that vertices joined by a directed path of length two are assigned different colours. The 2-dipath chromatic number is the minimum number of colours needed in such a colouring. There are two possible models, depending on whether adjacent vertices must also be assigned different colours. For both models of 2-dipath colouring we develop the basic theory, including characterizing the oriented graphs that can be 2-dipath coloured using a small number of colours, finding bounds on the 2-dipath chromatic number, determining the complexity of deciding the existence of a 2-dipath k-colouring, describing a homomorphism model, and showing how to determine the 2-dipath chromatic number of tournaments and bipartite tournaments. / Graduate

Thesis (Ph. D.)--Rutgers University, 2008. / "Graduate Program in Mathematics." Includes bibliographical references (p. 82-83).