No description available.

Let $G$ be any graph and let $\overline{G}$ be its complement. The complementary prism of $G$ is formed from the disjoint union of a graph $G$ and its complement $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. An Italian dominating function on a graph $G$ is a function such that $f \, : \, V \to \{ 0,1,2 \}$ and for each vertex $v \in V$ for which $f(v)=0$, it holds that $\sum_{u \in N(v)} f(u) \geq 2$. The weight of an Italian dominating function is the value $f(V)=\sum_{u \in V(G)}f(u)$. The minimum weight of all such functions on $G$ is called the Italian domination number. In this thesis we will study Italian domination in complementary prisms. First we will present an error found in one of the references. Then we will define the small values of the Italian domination in complementary prisms, find the value of the Italian domination number in specific families of graphs complementary prisms, and conclude with future problems.

Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths. In this thesis we show a way to represent such graphs in terms of an array with two colors and a labeled graph. Using this representation and the techniques of Polya counting we will then be able to get upper and lower bounds for graphs containing a long path as an induced subgraph. In particular, if we let P(n,k) be the number of graphs on n+k vertices which contains P_n, a path on n vertices, as an induced subgraph then using our upper and lower bounds for P(n,k) we will show that for any fixed value of k that P(n,k)~2^(nk+k_C_2)/(2k!).

This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the "Sandwich Theorem". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal. First I am going to describe the proof of the equality of theta, theta_1 and theta_2 and then I will show the calculation of the theta function for some specific graphs: K_n, graphs related to K_n, and C_n. This will help us understand the theta function, an important function for graph theory. Some of the results are calculated in different ways. This will benefit students who have a basic knowledge of graph theory and want to learn more about the theta function.

Virtually all genome assemblers to date are designed for use with data from haploid or homozygous diploid genomes. Their use on heterozygous genomic datasets generally results in highly-fragmented, error-prone assemblies, owing to the violation of assumptions during both the contigging and scaffolding phases. Of the two phases, scaffolding is more particularly impacted and algorithms to facilitate the scaffolding of heterozygous data are lacking. We present a stand-alone scaffolding algorithm, ScaffoldScaffolder, designed specifically for scaffolding diploid genomes. A fundamental step in the scaffolding phase is the assignment of sequence orientations to contigs within scaffolds. Deciding such an assignment in the presence of ambiguous evidence is what is termed the contig orientation problem. We define this problem using bidirected graph theory and show that it is equivalent to the weighted MAX-CUT problem. We present a greedy heuristic solution which we comparatively assess with other solutions to the contig orientation problem, including an advanced MAX-CUT heuristic. We illustrate how a solution to this problem provides a simple means of simultaneously identifying inverted haplotypes, which are uniquely found in diploid genomes and which have been shown to be involved in the genetic mechanisms of several diseases. Ultimately our findings show that due to the inherent biases in the underlying biological model, a greedy heuristic algorithm performs very well in practice, retaining a higher total percent of edge weight than a branch-and-bound semidefinite programming heuristic. This application exemplifies how existing graph theory algorithms can be applied in the development of new algorithms for more accurate assembly of heterozygous diploid genomes.

Let G be a simple graph on n vertices, and let S(G) be the class of all real-valued symmetric nxn matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The smallest rank achieved by a matrix in S(G) is called the minimum rank of G, denoted mr(G). The maximum nullity achieved by a matrix in S(G) is denoted M(G). For each graph G, there is an associated minimum rank class, MR(G) consisting of all matrices A in S(G) with rank A = mr(G). Although no restrictions are applied to the diagonal entries of matrices in S(G), sometimes diagonal entries corresponding to specific vertices of G must be zero for all matrices in MR(G). These vertices are known as nil vertices (see [6]). In this paper I discuss some basic results about nil vertices in general and nil vertices in cographs and prove that cographs with a nil vertex of a particular form contain two other nil vertices symmetric to the first. I discuss several open questions relating to these results and a counterexample. I prove that for all cographs G without an induced complete tripartite graph with independent sets all of size 3, the zero-forcing number Z(G), a graph theoretic parameter, is equal to M(G). In fact this result holds for a slightly larger class of cographs and in particular holds for all threshold graphs. Lastly, I prove that the maximum of the minimum ranks of all cographs on n vertices is the floor of 2n/3.

Graph theory is a mathematical study of objects and their pairwise relations, known as nodes and edges respectively. The birth of graph theory is often considered to take place in 1736 when the Swiss mathematician Leonhard Euler tried to solve a routing problem involving seven bridges of Königsberg in Prussia. In more recent times, graph theory has caught the attention of companies from all types of industries due to its power of modelling and analysing exceptionally large networks. This thesis investigates the usage of graph theory in the energy sector for a utility company, in particular Fortum whose activities consist of, but not limited to, production and distribution of electricity and heat. The output of the thesis is a wide overview of graph-theoretic concepts and their practical applications, as well as a study of a use-case where some concepts are put into deeper analysis. The chosen use-case within the scope of this thesis is feature selection - a process for reducing the number of features, also known as input variables, typically before a regression model is built to avoid overfitting and increase model interpretability. Five graph-based feature selection methods with different points of view are studied. Experiments are conducted on realistic data sets with many features to verify the legitimacy of the methods. One of the data sets is owned by Fortum and used for forecasting the electricity price, among other important quantities. The obtained results look promising according to several evaluation metrics and can be used by Fortum as a support tool to develop prediction models. In general, a utility company can likely take advantage graph theory in many ways and add value to their business with enriched mathematical knowledge. / Grafteori är ett matematiskt område där objekt och deras parvisa relationer, även kallade noder respektive kanter, studeras. Grafteorins födsel anses ofta äga rum år 1736 när den schweiziske matematikern Leonhard Euler försökte lösa ett vägsökningsproblem som involverade sju broar av Königsberg i Preussen. På senare tid har grafteori fått uppmärksamhet från företag inom flera branscher på grund av dess kraft att modellera och analysera väsentligt stora nätverk. Detta arbete undersöker användningen av grafteori inom energisektorn för ett allmännyttigt företag, närmare bestämt Fortum vars verksamhet består av, dock ej begränsat till, produktion och distribution av elektricitet och värme. Arbetet resulterar i en bred översiktlig genomgång av grafteoretiska begrepp och deras praktiska tillämpningar, samt ett fallstudium där några begrepp sätts in i en djupare analys. Det valda fallstudiet inom ramen för arbetet är variabelselektering - en process för att minska antalet ingångsvariabler, vilket vanligtvis genomförs innan en regressionsmodell skapas för att undvika överanpassning och öka modellens tydbarhet. Fem grafbaserade metoder för variabelselektering med olika ståndpunkter studeras. Experiment genomförs på realistiska datamängder med många ingångsvariabler för att verifiera metodernas giltighet. En av datamängderna ägs av Fortum och används för att prognostisera elpriset, bland andra viktiga kvantiteter. De erhållna resultaten ser lovande ut enligt flera utvärderingsmått och kan användas av Fortum som ett stödverktyg för att utveckla prediktionsmodeller. I allmänhet kan ett energiföretag sannolikt dra fördel av grafteori på många sätt och skapa värde i sin affär med hjälp av berikad matematisk kunskap.

The success of Online Social Networks (OSN) is influenced by having the ability to understand who is important. An OSN can be viewed as a graph where users are vertices and their interactions are edges. Graph-based methods can enable identification of people in these networks who for example exhibit the characteristics of leaders, influencers, or information brokers. A Massively Multiplayer Online game (MMO) is a type of OSN. It is a video game where a large number of players interact with each other in a virtual world. Using behavioral data of players' interactions within the space-based MMO EVE Online, the aim of this thesis is to conduct an experimental study to evaluate the effectiveness of a number graph-based methods at finding important players within different behavioral contexts. For that purpose we extract behavioral data to construct four distinct graphs: Fleet, Aggression, Mail, and Market. We also create a ground truth data set of important players based on heuristics from key gameplay categories. We experiment on these graphs with a selection of graph centrality, Influence Maximization, and heuristic methods. We explore how they perform in terms of ground truth players found per graph and execution time, and when combining results from all graphs. Our results indicate that there is no optimal method across graphs but rather the method and graph should be chosen according to the business intention at each time. To that end we provide recommendations as well as potential business case usages. We believe that this study serves as a starting point towards more graph based analysis within the EVE Online virtual universe where there are many unexplored research opportunities. / Framgången hos Online Sociala Nätverk (OSN) påverkas av förmågan att förstå vem som är viktig. Ett OSN kan ses som en graf där användarna är noder och deras interaktioner ärbågar. Grafbaserade metoder kan möjliggöra identifiering av personer i dessa nätverk somtill exempel uppvisar egenskaper hos ledare, påverkare eller informationsförmedlare. Ett Massively Multiplayer Online game (MMO) representerar en typ av OSN. Det är ett datorrollspel där ett stort antal spelare interagerar med varandra i en virtuell värld. Genomatt använda beteendedata om spelarnas interaktioner i den rymdbaserade MMO:n EVE Online är målet med denna avhandling att genomföra en experimentell studie för att utvärdera effektiviteten hos ett antal grafbaserade metoder för att hitta viktiga spelare inom olika beteendemässiga sammanhang. För det ändamålet extraherar vi beteendedata för att konstruera fyra distinkta grafer: Fleet, Aggression, Mail och Market. Vi skapar också ett ground truth" dataset av viktiga spelare baserat på heuristik från viktiga spelkategorier. Vi utför experiment på dessa grafer med ett urval av grafcentralitet, Influence Maximization och heuristiska metoder. Vi undersöker hur metoderna presterar i termer av antal ground truth spelare som finns per graf och över grafer, och i termer av exekveringstid. Våra resultat tyder på att det inte finns någon optimal metod för alla grafer. Metoden och grafen bör väljas beroende på intentionen vid varje tillfälle. För detta ändamål tillhandahåller vi rekommendationer samt potentiella affärsmässiga användningsområden. Vi tror att denna studie tjänar som utgångspunkt för mer grafbaserad analys inom EVEOnlines virtuella universum där det finns många outforskade forskningsmöjligheter.

In this thesis, we provide a self contained introduction to the theory of random matrices and matrix models. Our analysis has a chronological order and it begins with the study of nuclear energy levels and ensemble averaging which yields the famous Wigner surmise. Then, the standard Gaussian theory of the orthogonal, unitary and symplectic ensemble is derived from symmetry arguments of the corresponding physical system, which is then followed by the explicit calculation of Wigner's semicircle distribution. Moreover, interactions are introduced to the free theory which leads to the topological expansion, a diagrammatic way of evaluating certain expectation values. Also, it is shown that there exists a duality between the resulting graphs and the quantization of a two dimensional surface through mapping as well as a method for solving a specific family of potentials. Finally, the numerical confirmation for some observables is carried out using the Hamburger moment problem, and the derivation of critical points for some theories.

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G = (V, E) is a non empty set S ⊆ V where, for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc [Sha01, FLG00, SX07]. In [GK98, GK00], Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NP-complete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in [DF99]. In addition to parameterized algorithms for alliance related problems, we study the partition of series-parallel graphs into alliances. The class of series-parallel graphs is a special class in graph theory since many problems known to be NP-complete on general graphs have been shown to have polynomial time algorithms on series-parallel graphs [ZLL04, Hoj95, DS99, HHL87, TNS82]. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to series-parallel graphs . Series-parallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning series-parallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of series-parallel graphs that allow a partition into defensive alliances and a subclass of series-parallel graphs with a satisfactory partitions.