Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Cryptanalysis (2)
- Cryptography (2)
- Game theory (2)
- Playing cards (2)
- Additive number theory (1)
-
- Alpha-labeling (1)
- B-nomial numbers (1)
- Bernoulli numbers; Voronoi congruences; Fermat quotients; Lehmer-Mirimanoff congruences. (1)
- Binomial (1)
- C++ (1)
- Cactus (1)
- Canonical remainders (1)
- Card cipher (1)
- Chi-square (1)
- Cluster graph (1)
- Columnar transposition (1)
- Combinatorial Designs (1)
- Combinatorial number theory (1)
- Combinatorially orthogonality (1)
- Complete multipartite graph (1)
- Coprime representations (1)
- Cycles (1)
- Cyclic snake (1)
- Dot product graphs (1)
- Edge packing (1)
- Edge-distinguishing (1)
- Exact counting formulas (1)
- Fan graphs (1)
- Friendship graph (1)
- Games on graphs (1)
- Publication
- Publication Type
Articles 1 - 16 of 16
Full-Text Articles in Discrete Mathematics and Combinatorics
A Note On The Voronoi Congruences And The Residue Of The Fermat Quotient, Claire Levaillant
A Note On The Voronoi Congruences And The Residue Of The Fermat Quotient, Claire Levaillant
Communications on Number Theory and Combinatorial Theory
We prove a congruence on the residue of the Fermat quotient in base a which arises from a generalization of the Voronoi congruences and other congruences on sums and weighted sums of divided Bernoulli numbers. As an application in the base 2 case, we recover a congruence for the generalized harmonic number H2,(p-1)/2, a generalization originally due to Z-H. Sun of a classical congruence known for the harmonic number H(p-1)/2 as a special case of the Lerch formula. We find a sharpening of the Voronoi congruences that is different from the one of …
Exact Formulas For Restricted Coprime Representations Of Even Integers, Andres Mauricio Salazar
Exact Formulas For Restricted Coprime Representations Of Even Integers, Andres Mauricio Salazar
Communications on Number Theory and Combinatorial Theory
Let p ≥ 5 be prime, and let g(2n,p) denote the number of unordered representations by positive integers 2n = h + k, with h ≤ k and gcd(h,6p) = gcd(k,6p) = 1. Every positive integer coprime to 6 belongs to exactly one of the families 6z + 1 and 6z + 5. In each family, divisibility by p excludes one explicit residue class of z modulo p. We use these two excluded classes to derive an exact formula for g(2n,p) from finite residue counts and nonnegative lift counts. The formula is valid for every positive integer n, including all …
The Edge-Distinguishing Game, Nathaniel Benjamin, Elisa Benthem, Cooper Burkel, Marissa E. Chesser, Mike Janssen
The Edge-Distinguishing Game, Nathaniel Benjamin, Elisa Benthem, Cooper Burkel, Marissa E. Chesser, Mike Janssen
Communications on Number Theory and Combinatorial Theory
In this paper, we introduce a graph coloring game called the Edge-Distinguishing Game (EDGe). The edge-distinguishing chromatic number of a graph is used to determine the moves each player can make. We determine which player has a winning strategy for particular graphs and graph families. Additionally, utilizing principles from game theory as well as previous work on a computational solution for the Game of Cycles.
On Realizability Of Some Graphs, Runze Wang
On Realizability Of Some Graphs, Runze Wang
Communications on Number Theory and Combinatorial Theory
A graph H is said to be realizable by a graph G if for any vertex v in G, the induced subgraph of G on the neighborhood of v is isomorphic to H. In this paper, we show that a complete multipartite graph is realizable if and only if each of its parts has the same size; characterize the graphs by which a complete multipartite graph with each part having the same size is realizable; show that all cluster graphs are realizable; prove that a wheel is realizable if and only if it has four vertices; prove that …
Two Families Of Graceful Cacti, Christian Barrientos
Two Families Of Graceful Cacti, Christian Barrientos
Communications on Number Theory and Combinatorial Theory
We present a graceful labeling for each member of a subfamily of quadrangular cacti whose underlying graph correspond to the subclass of rooted binary trees where every level has at most two vertices. We also prove the existence of an $\alpha$-labeling (the most restricted type of graceful labeling) for all cyclic snakes, i.e., those cacti whose blocks are copies of the cycle $C_{4n}$ and its maximum degree is four.
Big Two And N-Card Poker Probabilities, Brian Wu, Chai Wah Wu
Big Two And N-Card Poker Probabilities, Brian Wu, Chai Wah Wu
Communications on Number Theory and Combinatorial Theory
Between the poker hands of straight, flush, and full house, which hand is more common? In standard 5-card poker, the order from most common to least common is straight, flush, full house. The same order is true for 7-card poker such as Texas hold'em. However, is the same true for n-card poker for larger n? We study the probability of obtaining these various hands for n-card poker for various values of n≥5. In particular, we derive closed expressions for the probabilities of flush, straight and full house and show that the probability of a flush is less than a straight …
Combinatorially Orthogonal Paths, Sean A. Bailey, David E. Brown, Leroy Beaseley
Combinatorially Orthogonal Paths, Sean A. Bailey, David E. Brown, Leroy Beaseley
Communications on Number Theory and Combinatorial Theory
Vectors x=(x1,x2,...,xn)T and y=(y1,y2,...,yn)T are combinatorially orthogonal if |{i:xiyi≠0}|≠1. An undirected graph G=(V,E) is a combinatorially orthogonal graph if there exists f:V→ℝn such that for any u,v∈V, uv∉E iff f(u) and f(v) are combinatorially orthogonal. We will show that every graph has a combinatorially orthogonal representation. We will show …
A Pebbling Game On Powers Of Paths, Garth Isaak, Matthew Prudente, Joseph M. Marcinik Iii
A Pebbling Game On Powers Of Paths, Garth Isaak, Matthew Prudente, Joseph M. Marcinik Iii
Communications on Number Theory and Combinatorial Theory
Two Player Graph Pebbling is an extension of graph pebbling. Players Mover and Defender use pebbling moves, the act of removing two pebbles from one vertex and placing one pebble on an adjacent vertex, to win. If a specified vertex has a pebble on it, then Mover wins. If a specified vertex is pebble-free and there are no more valid pebbling moves, then Defender wins. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement of m pebbles and for any specified vertex, Mover can win. We specify the …
Meertens Number And Its Variations, Chai Wah Wu
Meertens Number And Its Variations, Chai Wah Wu
Communications on Number Theory and Combinatorial Theory
In 1998, Bird introduced Meertens numbers as numbers that are invariant under a map similar to the Gödel encoding. In base 10, the only known Meertens number is 81312000. We look at some properties of Meertens numbers and consider variations of this concept. In particular, we consider variations of Meertens numbers where there is a finite time algorithm to decide whether such numbers exist, exhibit infinite families of these variations and provide bounds on parameters needed for their existence.
On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik
On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik
Communications on Number Theory and Combinatorial Theory
Graph pebbling can be extended to a two-player game on a graph G, called Two-Player Graph Pebbling, with players Mover and Defender. The players each use pebbling moves, the act of removing two pebbles from one vertex and placing one of the pebbles on an adjacent vertex, to win. Mover wins if they can place a pebble on a specified vertex. Defender wins if the specified vertex is pebble-free and there are no more pebbling moves on the vertices of G. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement …
Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang
Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang
Communications on Number Theory and Combinatorial Theory
Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be …
Generating B-Nomial Numbers, Ji Young Choi
Generating B-Nomial Numbers, Ji Young Choi
Communications on Number Theory and Combinatorial Theory
This paper presents three new ways to generate each type of b-nomial numbers: We develop ordinary generating functions, we find a whole new set of recurrence relations, and we identify each b-nomial number as a single binomial coefficient or as an alternating sum of products of two binomial coefficients.
Skolem Number Of Subgraphs On The Triangular Lattice, Braxton Carrigan, Garrett Green
Skolem Number Of Subgraphs On The Triangular Lattice, Braxton Carrigan, Garrett Green
Communications on Number Theory and Combinatorial Theory
A Skolem sequence can be thought of as a labelled path where any two vertices with the same label are that distance apart. This concept has naturally been generalized to graph labelling. This brings rise to the question; “what is the smallest set of consecutive positive integers we can use to properly Skolem label a graph?” This is known as the Skolem number of the graph. In this paper we give the Skolem number for three natural vertex induced subgraphs of the triangular lattice graph.
Determining Biases In The Card-Chameleon Cryptosystem, Isaac Reiter, Eric Landquist
Determining Biases In The Card-Chameleon Cryptosystem, Isaac Reiter, Eric Landquist
Communications on Number Theory and Combinatorial Theory
Throughout history, spies, soldiers, and others have relied on so-called {\em hand ciphers} to send encrypted messages. Since the creation of Pontifex (also known as Solitaire) by Bruce Schneier in 1999, a number of hand ciphers utilizing a standard deck of playing cards have emerged. Since there are $52! \approx 2^{225.58}$ possible ways to order a deck of cards, there are over 225 bits of entropy in a well-shuffled deck of cards. Theoretically, this can provide enough security to rival modern computer-based cryptosystems. In this paper, we describe and analyze one such playing card cipher, Card-Chameleon, created by Matthew McKague. …
Analyzing And Creating Playing Card Cryptosystems, Isaac A. Reiter
Analyzing And Creating Playing Card Cryptosystems, Isaac A. Reiter
Honors Student Research
Before computers, military tacticians and government agents had to rely on pencil-and-paper methods to encrypt information. For agents that want to use low-tech options in order to minimize their digital footprint, non-computerized ciphers are an essential component of their toolbox. Still, the presence of computers limits the pool of effective hand ciphers. If a cipher is not unpredictable enough, then a computer will easily be able to break it. There are 52! ≈ 2^225.58 ways to mix a deck of cards. If each deck order is a key, this means that there are 52! ≈ 2^225.58 different ways to encrypt …
Super Sudoku Squares, Dean Hoffman
Super Sudoku Squares, Dean Hoffman
Communications on Number Theory and Combinatorial Theory
We refer to a completed Sudoku puzzle as a Sudoku Square of order 3. We define a more restricted, but natural, extension --- a Super Sudoku Square of order n, and determine for which orders n one exists.