Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Graph theory

Discipline
Institution
Publication Year
Publication
Publication Type

Articles 91 - 97 of 97

Full-Text Articles in Discrete Mathematics and Combinatorics

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

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, K3∪{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.

Go to article

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

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 Dv, packing and covering complete bipartite digraphs, Dm,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 C4, X, and Y.

Go to article

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

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 = (v1v2...vk); vi ∊ {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, …

Go to article

Alliance Partitions In Graphs., Jason Lachniet May 2007

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 …

Go to article

Third Order Degree Regular Graphs, Leslie D. Hayes Apr 1994

Third Order Degree Regular Graphs, Leslie D. Hayes

Honors Theses

A graph G is regular of degree d if for every vertex v in G there exist exactly d vertices at distance 1 from v. A graph G is kth order regular of degree d if for every vertex v in G, there exist exactly d vertices at distance k from v. In this paper, third order regular graphs of degree 1 with small order are characterized.

Go to article

Another Way Of Counting Nᴺ, Arthur T. Benjamin, Fritz Juhnke Aug 1992

Another Way Of Counting Nᴺ, Arthur T. Benjamin, Fritz Juhnke

All HMC Faculty Publications and Research

An original combinatorial proof of a combinatorial identity is presented.

Go to article

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis Jan 1984

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Πk-formulae of size n for which every Σk-formula has size exp Ω(n1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σk-formula of size exp O(n1/(k-1)). Thus our hierarchy theorem is the best possible.

Go to article

First Prev