Mathematics Commons^™

Finding Edge And Vertex Induced Cycles Within Circulants., Trina Marcella Wooten

Electronic Theses and Dissertations

Let H be a graph. G is a subgraph of H if V (G) ⊆ V (H) and E(G) ⊆ E(H). The subgraphs of H can be used to determine whether H is planar, a line graph, and to give information about the chromatic number. In a recent work by Beeler and Jamison [3], it was shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As …

Double Domination Of Complementary Prisms., Lamont D. Vaughan

Electronic Theses and Dissertations

The complementary prism of a graph G is obtained from a copy of G and its complement G̅ by adding a perfect matching between the corresponding vertices of G and G̅. For any graph G, a set D ⊆ V (G) is a double dominating set (DDS) if that set dominates every vertex of G twice. The double domination number, denoted γ_×2(G), is the cardinality of a minimum double dominating set of G. We have proven results on graphs of small order, specific families and lower bounds on γ_{×2 …}

On The Attainability Of Upper Bounds For The Circular Chromatic Number Of K4-Minor-Free Graphs., Tracy Lance Holt

Electronic Theses and Dissertations

Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χ_c(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and …

Decomposition, Packings And Coverings Of Complete Digraphs With A Transitive-Triple And A Pendant Arc., Janice Gail Lewenczuk

Electronic Theses and Dissertations

In the study of design theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K₃∪{e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings and coverings of the complete digraph with each of the six transitive triples with a pendant arc.

Chromatic Number Of The Alphabet Overlap Graph, G(2, K , K-2)., Jerry Brent Farley

Electronic Theses and Dissertations

A graph G(a, k, t) is called an alphabet overlap graph where a, k, and t are positive integers such that 0 ≤ t < k and the vertex set V of G is defined as, V = {v : v = (v₁v₂...v_k); v_i ∊ {1, 2, ..., a}, (1 ≤ i ≤ k)}. That is, each vertex, v, is a word of length k over an alphabet of size a. There exists an edge between two vertices u, …

Packings And Coverings Of Various Complete Digraphs With The Orientations Of A 4-Cycle., Melody Elaine Cooper

Electronic Theses and Dissertations

There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs D_v, packing and covering complete bipartite digraphs, D_m,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C₄, X, and Y.

Decompositions, Packings, And Coverings Of Complete Directed Gaphs With A 3-Circuit And A Pendent Arc., Chrys Gwellem

Electronic Theses and Dissertations

In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K₃ ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings, and coverings of the complete digraph with the two 3-circuit with a pendant arc orientations.

Tricyclic Steiner Triple Systems With 1-Rotational Subsystems., Quan Duc Tran

Electronic Theses and Dissertations

A Steiner triple system of order v, denoted STS(v), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic STS(v) when one of the cycles is of length one. In this case, the STS(v) will contain a subsystem which admits an automorphism consisting of a fixed point and a single cycle. The subsystem is said to be 1-rotational.

Alliance Partitions In Graphs., Jason Lachniet

Electronic Theses and Dissertations

For a graph G=(V,E), a nonempty subset S contained in V is called a defensive alliance if for each v in S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. If there are strictly more vertices from the closed neighborhood of v in S as in V-S, then S is a strong defensive alliance. A (strong) defensive alliance is called global if it is also a dominating set of G. The alliance partition number (respectively, strong …

Double Domination Edge Critical Graphs., Derrick Wayne Thacker

Electronic Theses and Dissertations

In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and …

Trees With Unique Minimum Locating-Dominating Sets., Stephen M. Lane

Electronic Theses and Dissertations

A set S of vertices in a graph G = (V, E) is a locating-dominating set if S is a dominating set of G, and every pair of distinct vertices {u, v} in V - S is located with respect to S, that is, if the set of neighbors of u that are in S is not equal to the set of neighbors of v that are in S. We give a construction of trees that have unique minimum locating-dominating sets.

On The Chromatic Number Of The Ao(2, K , K-1) Graphs., Navya Arora

Electronic Theses and Dissertations

The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs.

We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k …