Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Keyword
-
- Combinatorics (4)
- Graph theory (4)
- Coverings (3)
- Fibonacci numbers (3)
- Packings (3)
-
- Design theory (2)
- 1-Rotational System (1)
- 3-circuit (1)
- Alliance partition (1)
- Alquaddoomi conjecture (1)
- Barker array (1)
- Barker array conjecture (1)
- Bicyclic (1)
- Binary sequences (1)
- Board games (1)
- Braided tensor category (1)
- Cards (1)
- Chromatic number (1)
- Combinatorial analysis (1)
- Combinatorial identities (1)
- Competitive coloring (1)
- Crystal growth (1)
- De bruijn graph (1)
- Decomposition (1)
- Decompositions (1)
- Defensive alliance (1)
- Determinantal identities (1)
- Determinants (1)
- Digital electronics (1)
- Digraph (1)
- Publication
- Publication Type
Articles 1 - 20 of 20
Full-Text Articles in Discrete Mathematics and Combinatorics
Chromatic Number Of The Alphabet Overlap Graph, G(2, K , K-2)., Jerry Brent Farley
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, …
Decomposition, Packings And Coverings Of Complete Digraphs With A Transitive-Triple And A Pendant Arc., Janice Gail Lewenczuk
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.
Packings And Coverings Of Various Complete Digraphs With The Orientations Of A 4-Cycle., Melody Elaine Cooper
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.
Recounting Determinants For A Class Of Hessenberg Matrices, Arthur T. Benjamin, Mark A. Shattuck
Recounting Determinants For A Class Of Hessenberg Matrices, Arthur T. Benjamin, Mark A. Shattuck
All HMC Faculty Publications and Research
We provide combinatorial interpretations for determinants which are Fibonacci numbers of several recently introduced Hessenberg matrices. Our arguments make use of the basic definition of the determinant as a signed sum over the symmetric group.
Solution To Problem 1751, A Combinatorial Identity, Arthur T. Benjamin, Andrew Carman '09
Solution To Problem 1751, A Combinatorial Identity, Arthur T. Benjamin, Andrew Carman '09
All HMC Faculty Publications and Research
A combinatorial proof to Iliya Bluskov's proposed Problem 1751.
The Discrete Logarithm Problem And Ternary Functional Graphs, Max F. Brugger, Christina A. Frederick
The Discrete Logarithm Problem And Ternary Functional Graphs, Max F. Brugger, Christina A. Frederick
Mathematical Sciences Technical Reports (MSTR)
Encryption is essential to the security of transactions and communications, but the algorithms on which they rely might not be as secure as we all assume. In this paper, we investigate the randomness of the discrete exponentiation function used frequently in encryption. We show how we used exponential generating functions to gain theoretical data for mapping statistics in ternary functional graphs. Then, we compare mapping statistics of discrete exponentiation functional graphs, for a range of primes, with mapping statistics of the respective ternary functional graphs.
Decompositions, Packings, And Coverings Of Complete Directed Gaphs With A 3-Circuit And A Pendent Arc., Chrys Gwellem
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, 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 the two 3-circuit with a pendant arc orientations.
Tricyclic Steiner Triple Systems With 1-Rotational Subsystems., Quan Duc Tran
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.
Characterizing Sparse Graphs By Map Decompositions, Ruth Haas, Audrey Lee, Ileana Streinu, Louis Theran
Characterizing Sparse Graphs By Map Decompositions, Ruth Haas, Audrey Lee, Ileana Streinu, Louis Theran
Mathematics Sciences: Faculty Publications
A map is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into k edge-disjoint maps after: (1) the addition of any ℓ edges; (2) the addition of some ℓ edges. These graphs are identified with classes of sparse graphs; the results are also given in matroidal terms.
Proof Of The Barker Array Conjecture, James A. Davis, Jonathan Jedwab, Ken W. Smith
Proof Of The Barker Array Conjecture, James A. Davis, Jonathan Jedwab, Ken W. Smith
Department of Math & Statistics Faculty Publications
Using only elementary methods, we prove Alquaddoomi and Scholtz’s conjecture of 1989, that no s × t Barker array having s, t > 1 exists except when s = t = 2.
Nonlinear Dynamics In Combinatorial Games: Renormalizing Chomp, Eric J. Friedman, Adam S. Landsberg
Nonlinear Dynamics In Combinatorial Games: Renormalizing Chomp, Eric J. Friedman, Adam S. Landsberg
WM Keck Science Faculty Papers
We develop a new approach to combinatorial games that reveals connections between such games and some of the central ideas of nonlinear dynamics: scaling behaviors, complex dynamics and chaos, universality, and aggregation processes. We take as our model system the combinatorial game Chomp, which is one of the simplest in a class of "unsolved" combinatorial games that includes Chess, Checkers, and Go. We discover that the game possesses an underlying geometric structure that "grows" (reminiscent of crystal growth), and show how this growth can be analyzed using a renormalization procedure adapted from physics. In effect, this methodology allows one to …
Closed-Neighborhood Anti-Sperner Graphs, John P. Mcsorley, Alison Marr, Thomas D. Porter, Walter D. Wallis
Closed-Neighborhood Anti-Sperner Graphs, John P. Mcsorley, Alison Marr, Thomas D. Porter, Walter D. Wallis
Articles and Preprints
For a simple graph G let NG[u] denote the closed-neighborhood of vertex u ∈ V (G). Then G is closed-neighborhood anti-Sperner (CNAS) if for every u there is a v ∈ V (G)\{u} with NG [u] ⊆ NG [v] and a graph H is closed-neighborhood distinct (CND) if every closed-neighborhood is distinct, i.e., if NH[u] ≠ NH[v] when u ≠ v, for all u and v ∈ V (H).
In this paper we …
On The Gauge Equivalence Of Twisted Quantum Doubles Of Elementary Abelian And Extra-Special 2-Groups, Christopher Goff, Geoffrey Mason, Siu-Hung Ng
On The Gauge Equivalence Of Twisted Quantum Doubles Of Elementary Abelian And Extra-Special 2-Groups, Christopher Goff, Geoffrey Mason, Siu-Hung Ng
Christopher Goff
Alliance Partitions In Graphs., Jason Lachniet
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 …
A Combinatorial Proof Of Vandermonde's Determinant, Arthur T. Benjamin, Gregory P. Dresden
A Combinatorial Proof Of Vandermonde's Determinant, Arthur T. Benjamin, Gregory P. Dresden
All HMC Faculty Publications and Research
No abstract provided in this article.
A Combinatorial Solution To Intertwined Recurrences, Arthur T. Benjamin, Michael D. Hirschhorn
A Combinatorial Solution To Intertwined Recurrences, Arthur T. Benjamin, Michael D. Hirschhorn
All HMC Faculty Publications and Research
We provide combinatorial derivations of solutions to intertwined second order linear recurrences (such as an = pbn-1 + qan-2, bn = ran-1 + sbn-2) by counting tilings of length n strips with squares and dominoes of various colors and shades. A similar approach can be applied to intertwined third order recurrences with coefficients equal to one. Here we find that all solutions can be expressed in terms of tribonacci numbers. The method can also be easily extended to solve and combinatorially comprehend kth order Fibonacci recurrences.
Fibonacci Deteminants - A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn
Fibonacci Deteminants - A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn
All HMC Faculty Publications and Research
In this paper, we provide combinatorial interpretations for some determinantal identities involving Fibonacci numbers. We use the method due to Lindström-Gessel-Viennot in which we count nonintersecting n-routes in carefully chosen digraphs in order to gain insight into the nature of some well-known determinantal identities while allowing room to generalize and discover new ones.
The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn
The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn
Faculty Publications
The (r, d)-relaxed coloring game is a two-player game played on the vertex set of a graph G. We consider a natural analogue to this game on the edge set of G called the (r, d)-relaxed edge-coloring game. We consider this game on trees and more generally, on k-degenerate graphs. We show that if G is k-degenerate with ∆(G) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆+k−1 and d≥2k2 + 4k.
Towards The Computation Of The Convex Hull Of A Configuration From Its Corresponding Separating Matrix, Elie Feder, David Garber
Towards The Computation Of The Convex Hull Of A Configuration From Its Corresponding Separating Matrix, Elie Feder, David Garber
Publications and Research
In this paper we cope with the following problem compute the size of the convex hull of a configuration C where the given data is the number of separating lines between any two points of the configuration (where the lines are generated by pairs of other points of the configuration)
We give an algorithm for the case that the convex hull is of size 3 and a partial algorithm and some directions for the case that the convex hull is of size bigger than 3.
Carathéodory Functions In The Banach Space Setting, Daniel Alpay, Olga Timoshenko, Dan Volok
Carathéodory Functions In The Banach Space Setting, Daniel Alpay, Olga Timoshenko, Dan Volok
Mathematics, Physics, and Computer Science Faculty Articles and Research
We prove representation theorems for Carathéodory functions in the setting of Banach spaces.