A graph G is domination bicritical if the removal of any pair of vertices decreases the domination number. Properties of bicritical graphs are studied. We show that a connected bicritical graph has domination number at least 3, minimum degree at least 3, and edge-connectivity at least 2. Ways of constructing a bicritical graph from smaller bicritical graphs are presented.

An E-graph is constructed by replacing each edge in a core graph G with a copy of a graph H. An important property of E-graphs is that their invariant values can be determined from parameters of the original graphs G and H. We determine chromatic number, clique number, vertex and edge cover numbers, vertex and edge independence numbers, circumference, and girth of E-graphs. A characterization of hamiltonian E-graphs is also given.

Doctor of Philosophy / Department of Mathematics / Gerald H. Höhn / We classify the genera of doubly even binary codes, the genera of even lattices, and the genera of rational vertex operator algebras (VOAs) arising from the modular tensor categories (MTCs) of rank up to 4 and central charges up to 16. For the genera of even lattices, there are two types of the genera: code type genera and non code type genera. The number of the code type genera is finite. The genera of the lattices of rank larger than or equal to 17 are non code type. We apply the idea of a vector valued modular form and the representation of the modular group SL[subscript]2(Z) in [Bantay2007] to classify the genera of the VOAs arising from the MTCs of ranks up to 4 and central charges up to 16.

Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2011. / Includes bibliography. / Please refer to full text to view abstract.

A feasibility study is presented which measures the masses of the chargino X̃₁^± and neutralinos X̃₁⁰ and X̃₂⁰ using the processes of e⁺e⁻→ X̃₁⁺X̃₁^- → X̃₁⁰X̃₁⁰W⁺W⁻ and e⁺e⁻→ X̃₂⁰X̃₂⁰ → X̃₁⁰X₁⁰ZZ at the International Linear Collider. The detector simulation is based on the Silicon Detector (SiD) concept and an integrated luminosity of 500 fb⁻¹ is considered at the centre-of-mass energy of 500 GeV. A template-fitting method is employed to measure the chargino and neutralino masses, which results in uncertainties of 0.16 GeV, 0.5 GeV and 1.0 GeV for the mass of X̃₁⁰, X̃₁^± and X̃₂⁰ respectively. A study on the ISIS2 sensor, a technology for the ILC vertex detector, is also presented. The characteristic of the sensors are studied for both its test structure and main array pixels. The operation conditions are optimized and the sensor successfully demonstrated its capabilities of in-situ charge storage and charge transfer. The charge transfer efficiency is measured to be better than 98%.

Graphs can effectively model biomolecules, computer systems, and other applications. A weighted graph is a graph in which values or labels are assigned to the edges of the graph. However, in this thesis, we assign values to the vertices of the graph rather than the edges and we modify several standard graphical measures to incorporate these vertex weights. In particular, we designate the degree of each vertex as its weight. Previous research has not investigated weighting vertices by degree. We find the vertex weighted domination number in connected graphs, beginning with trees, and we define how weighted vertices can affect eccentricity, independence number, and connectivity.

For a graph G = (V,E), we consider a bipartition {V1,V2} of the vertex set V by placing constraints on the vertices as follows. For every vertex v in Vi, we place a constraint on the number of neighbors v has in Vi and a constraint on the number of neighbors it has in V3-i. Using three values, namely 0 (no neighbors are allowed), 1 (at least one neighbor is required), and X (any number of neighbors are allowed) for each of the four constraints, results in 27 distinct types of bipartitions. The goal is to characterize graphs having each of these 27 types. We give characterizations for 21 out of the 27. Three other characterizations appear in the literature. The remaining three prove to be quite difficult. For these, we develop properties and give characterization of special families.

For the past few years, with the rapid advance of VLSI and multimedia technology, the applications of three-dimensional (3D) graphic applications have been widely and rapidly spread into various areas, and not longer limited into specific technical areas performed by high-end workstations. In near future, the 3D graphic engine will become an indispensable part of most multimedia systems including the entertainment television sets, the personal electronic appliances etc. A general 3D graphics engine can be divided into the geometry subsystem and the raster sub- system. The main contribution of this thesis is to design an efficient fragment pipeline process. It also helps the development of the vertex processor, and the integration of geometry and raster subsystem. In the design of the per-fragment processor, since it contains vary processing stages, such as fog blending, visible test, and alpha blending. This thesis analyzes the dependence relationship between these stages to allow several stages to run in parallel to reduce the overall pipeline latency and adjust the processing order of these stages to avoid unnecessary texturing access. This thesis also proposes two memory buffer access mechanisms suitable for the tile-based 3D graphic rendering engine to reduce the overall system memory bandwidth. The first method is to include some additional control flags for each tile such that the frequent buffer clear operations can be integrated with the normal rendering processes to avoid the additional memory clear access. The second approach is to identify the non-modified pixels in each tile by building the dirty table to reduce the number of updated pixels. The experimental results show that the proposed methods can cause more than 50% reduction of memory access. The proposed design has been realized using 0.18um technology. The gate count of the vertex processor without special functions and per-fragment processor is 201k and 118k, respectively.

With technology increasingly and the needs of high performance and multiple functionalities, power dissipation has be a bottleneck in microprocessors. And clock power is the most percentage of total power dissipation. In our thesis, we will provide an effective clock gating methodology that has not more overhead possibly to decrease total power dissipations based on SIMD 3D vertex shader. Except for classify all instructions according the instruction flow, we also consider the relationship of pipeline stage and are based on register bank to control execution units more flexibility. Using clock gating not only can decrease clock power, but also decrease the power of hardware modules succeed the registers with clock gating that be controlled. In our thesis, we will analysis which clock gating version is suitable because there is not definitely to disable the clock of all pipeline registers of all pipeline stages and hold all opportunities that can disable the clock. We will explain on experimental results and show the final low power version. With experimental results, the clock gating methodology that we bring can decrease almost 30% power with increase less than 2% area. And collection of instruction schedule algorithm for high performance that can decrease 41% energy at most. In new version of four vertexes execute sequentially, using clock gating can also decrease almost 10% power dissipation. And collection of instruction schedule algorithm for this version not only has better performance result but also can decrease 16% energy at most.

Vertex shader, one of the core parts in 3D graphics systems, is to speed up the operations of coordinate transformation and lighting in 3D graphics pipeline, and vector ALU is the key part of a vertex shader. This thesis proposes several unified architectures that integrate the floating-point vector arithmetic unit and special function unit in order to share some hardware resource. We propose three different architectures for the design of the unified vector ALU. The first architecture includes a single-instruction-multiple-data (SIMD) vector arithmetic unit, and uses table-based method with first-order approximation to calculate some special functions. The second architecture use higher-order approximation to reduce the table sizes and share the floating-point multipliers in the SIMD vector unit. The proposed third architecture has two copies of hardware that can compute two dot-product operations in parallel and thus increase the throughput of the matrix computation by a factor of two. Furthermore, the two dot-product units can be used to perform the interpolation for special function calculation.