Thesis (M.S.)--West Virginia University, 2003. / Title from document title page. Document formatted into pages; contains vi, 41 p. : ill. (some col.). Vita. Includes abstract. Includes bibliographical references (p. 40-41).

Given a graph G=(V,E), a vertex ordering of G is a total order v1,v2,...,vn of V. A graph search algorithm is a systematic method for visiting each vertex in a graph, naturally producing a vertex ordering of the graph. We explore the problem of determining whether a given vertex in a graph can be the end (last) vertex of a search ordering for various common graph search algorithms when restricted to various graph classes, as well as the related problem of determining if a vertex is an end-vertex when a start vertex is specified for the search. The former is referred to as the end-vertex problem, and the latter is the beginning-end-vertex problem. For the beginning-end-vertex problem, we show it is NP-complete on bipartite graphs as well as degree restricted bipartite graphs for Lexicographic Breadth First Search, but solvable in polynomial time on split graphs for Breadth First Search. We show that the end-vertex problem is tractable for Lexicographic Breadth First Search on proper interval bigraphs and for Lexicographic Depth First Search on chordal graphs. Further, we show that the problem is NP-complete for Lexicographic Breadth First Search and Depth First Search on bipartite graphs. / Graduate

Research Doctorate - Doctor of Philosophy (PhD) / In this thesis, a number of new methods for constructing vertex-magic total-labelings of graphs are presented. These represent an advance on existing methods since they are general constructions rather than ad hoc constructions for specific families of graphs. Broadly, five new kinds of construction methods are presented. Firstly, we present a class of methods characterized by adding 2- or 4-factors to a labeled graph, reassigning vertex labels to the edges of these factors and then adding new vertex labels to create a VMTL of the new graph. The major result is a unified method for constructing VMTL of large families of regular graphs, providing strong evidence for MacDougall's conjecture that, apart from a few minor exceptions, all regular graphs possess vertex-magic total-labelings. Secondly, we present methods for obtaining a labeling of a union of two graphs, one of which possesses a strong labeling, and then building on this labeling to create a labeling of an irregular graph. These methods as well as results in the Appendices provide strong evidence against an early conjecture regarding labelings and vertex degrees. Thirdly, constructions are presented for a new kind of magic square, containing some zeroes, which can be used to build labelings of graphs from labeled spanning subgraphs. Next, constructions are presented for a new kind of anti-magic square, containing some zeroes, which is equivalent to a strong labeling of certain kinds of bipartite graphs which can in turn be built upon to produce labelings of graphs with more edges. Finally, we present a method of mutating a graph labeling by reassigning edges in a way that preserves the magic constant to obtain a labeling of a different graph. This method provides a prolific source of new labelings.

RODRIGUES, Carlos Diego. Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas. 2008. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2005. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-08T19:45:39Z No. of bitstreams: 1 2008_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-08T19:45:58Z (GMT) No. of bitstreams: 1 2008_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Made available in DSpace on 2016-06-08T19:45:58Z (GMT). No. of bitstreams: 1 2008_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) Previous issue date: 2008 / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have a connected complement. Also, the column generation algorithm proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported. / Neste trabalho abordamos o problema de coloração de vértices via programação inteira. Uma versão expandida da formulação por conjuntos independentes é utilizada para abrigar outras sub-estruturas do grafos além dos vértices. Cada uma dessas sub-estruturas define uma restrição que determina quantos conjuntos independentes são necessarios para cobrir aquele subgrafo. Experimentos com um método de geração de cortes e colunas para o problema são feitos para determinar um limite inferior para um conjunto de instâncias classicas para esse problema a biblioteca DIMACS.

RODRIGUES, Carlos Diego. Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas. 2008. 79 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T11:50:40Z No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:28:23Z (GMT) No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Made available in DSpace on 2016-07-14T15:28:23Z (GMT). No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) Previous issue date: 2008 / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have a connected complement. Also, the column generation algorithm proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported. / Neste trabalho abordamos o problema de coloração de vértices via programação inteira. Uma versão expandida da formulação por conjuntos independentes é utilizada para abrigar outras sub-estruturas do grafos além dos vértices. Cada uma dessas sub-estruturas define uma restrição que determina quantos conjuntos independentes são necessarios para cobrir aquele subgrafo. Experimentos com um método de geração de cortes e colunas para o problema são feitos para determinar um limite inferior para um conjunto de instâncias classicas para esse problema a biblioteca DIMACS.

This thesis presents two analyses of data recorded by the ATLAS detector during proton-proton collisions at the LHC. The first is the implementation of a vertex counting algorithm to measure the luminosity recorded by ATLAS during collisions at a centre-of-mass energy of √s = 8 TeV in 2012. This comprises a Monte Carlo closure test for validation of the method and its corrections, the calibration of the method using the van der Meer scans performed in 2012 and the application of the method to physics runs. It also includes tests of the internal and external consistency of the algorithm and the potential to use this algorithm to measure the luminosity of data collected during proton-proton collisions at √s = 13 TeV.The second analysis is the measurement of the inclusive and purely electroweak production of dijets in association with a Z boson, performed using the 3.2 fb−1 of data collected during collisions at a centre-of-mass energy of √s = 13 TeV in 2015. Cross-section measurements are presented for five fiducial regions, each of which has a different sensitivity to the electroweak component of the Zjj production. Data and Monte Carlo predictions are compared and found to be in reasonable agreement for most cases. The electroweak Zjj production cross-section is then extracted in a fiducial region where this contribution is enhanced. This measurement is also in good agreement with the Monte Carlo prediction. These first 13 TeV measurements will set the scene for studies of weak boson fusion, both within the Standard Model and in new phenomena searches, which will become even more important in Run 2 and the future of the LHC due to the electroweak sector not being as constrained yet, compared to the strong sector, and due to the larger enhancements as a result of a higher √s, where electroweak physics can be most easily extracted.

The LHCb experiment, based at the Large Hadron Collider at CERN, is primarily designed to make precision measurements of the decays of heavy flavour hadrons, such as B and D mesons. This thesis is composed of two parts: the first consists of two studies of LHCb's vertex locator (VELO) and the second describes the development of methods for recording the decay D0->K-mu+nu_mu. The first VELO study involves calibration and monitoring of the gain (i.e. the detector response to input charge from particles). We propose a robust method to measure the gain response of each silicon sensor using calibration bits output by the sensors, and a method to recalibrate the gain simple enough to be followed by non-expert VELO users. This is followed by an investigation into into the prospects of using the VELO to perform particle identification using the characteristic energy deposition of each particle species (dE/dx). Finally, studies into the development of a trigger and a so-called 'stripping line' for recording D0->K-mu+nu_mu decays is presented. The relatively high cross-section for charm decays in LHCb mean this decay (with a branching fraction of 3%) occurs frequently, and the challenge of a trigger is to reduce this to a rate acceptable to write to disk. Finally, based on a sample of data from July and August 2011, the measured q 2 distribution for this decay is compared to the simple single-pole theoretical model, and the pole mass is measured to bem_pole=2.35 + 0.81 - 0.35 GeV/c 2.

The distance d(u,v) from vertex u to vertex v in a digraph G is the length of the shortest directed path from u to v. The eccentricity e(v) of vertex v is the maximum distance of v to any other vertex of G. A vertex u is an eccentric vertex of vertex v if the distance from v to u is equal to the eccentricity of v. The eccentric digraph ED(G) of a digraph G is the digraph that has the same vertex set as G and the arc set defined by: there is an arc from u to v iff v is an eccentric vertex of u. The idea of the eccentric digraph of a graph was introduced by Buckley (Congr. Numer. 149 (2001) 65) and the idea of the eccentric digraph of a digraph by Boland and Miller (Proceedings of AWOCA'01, July 2001, p. 66). In this paper, we examine eccentric digraphs of digraphs for various families of digraphs and we consider the behaviour of an iterated sequence of eccentric digraphs of a digraph. The paper concludes with several open problems.

A coalition in a graph G =(V, E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1 ∪ V2 is a dominating set of G.A coalition partition in a graph G of order n = |V| is a vertex partition π= {V1, V2,⋯, Vk} of V such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition πof a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G, π), the vertices of which correspond one-to-one with the sets V1, V2,⋯, Vk of πand two vertices are adjacent in CG(G, π) if and only if their corresponding sets in πform a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs.

In this thesis, we report on two projects applying representation theoretic techniques to solve enumerative and geometric problems, which were carried out by the author during his pursuit of Ph.D. at Columbia. We first study the relative Gromov-Witten theory on T*P¹ x P¹ and show that certain equivariant limits give relative invariants on P¹ x P¹. By formulating the quantum multiplications on Hilb(T*P¹) computed by Davesh Maulik and Alexei Oblomkov as vertex operators and computing the product expansion, we demonstrate how to get the insertion operator computed by Yaim Cooper and Rahul Pandharipande in the equivariant limits. Brenti proves a non-recursive formula for the Kazhdan-Lusztig polynomials of Coxeter groups by combinatorial methods. In the case of the Weyl group of a split group over a finite field, a geometric interpretation is given by Sophie Morel via weight truncation of perverse sheaves. With suitable modifications of Morel's proof, we generalize the geometric interpretation to the case of finite and affine partial flag varieties. We demonstrate the result with essentially new examples using sl₃ and sl₄..