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

Discrete Mathematics and Combinatorics Commons

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

746 Full-Text Articles 915 Authors 73100 Downloads 80 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

746 full-text articles. Page 1 of 26.

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg 2018 Loyola University Chicago

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Ronald Greenberg

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.


An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg 2018 Loyola University Chicago

An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg

Ronald Greenberg

I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.


On The Inverse Of A Class Of Weighted Graphs, Swarup Kumar Panda, Sukanta Pati 2018 Indian Statistical Institute - Delhi Center

On The Inverse Of A Class Of Weighted Graphs, Swarup Kumar Panda, Sukanta Pati

Electronic Journal of Linear Algebra

In this article, only connected bipartite graphs $G$ with a unique perfect matching $\c{M}$ are considered. Let $G_\w$ denote the weighted graph obtained from $G$ by giving weights to its edges using the positive weight function $\w:E(G)\ar (0,\ity)$ such that $\w(e)=1$ for each $e\in\c{M}$. An unweighted graph $G$ may be viewed as a weighted graph with the weight function $\w\equiv\1$ (all ones vector). A weighted graph $G_\w$ is nonsingular if its adjacency matrix $A(G_\w)$ is nonsingular. The {\em inverse} of a nonsingular weighted graph ...


On The Second Least Distance Eigenvalue Of A Graph, Xueyi Huang, Qiongxiang Huang, Lu Lu 2018 College of Mathematics and Systems Science, Xinjiang University, Urumqi, Xinjiang 830046, P.R.China.

On The Second Least Distance Eigenvalue Of A Graph, Xueyi Huang, Qiongxiang Huang, Lu Lu

Electronic Journal of Linear Algebra

Let $G$ be a connected graph on $n$ vertices, and let $D(G)$ be the distance matrix of $G$. Let $\partial_1(G)\ge\partial_2(G)\ge\cdots\ge\partial_n(G)$ denote the eigenvalues of $D(G)$. In this paper, the connected graphs with @n􀀀1(G) at least the smallest root of $x^3=3x^2-11x-6 = 0$ are determined. Additionally, some non-isomorphic distance cospectral graphs are given.


Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer 2018 Southern CT State University

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory and Applications of Graphs

We say that a blinking node system modulo $n$ is an ordered pair $(G,L)$ where $G$ is a graph and $L$ is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of $G$ such that the position of each vertex modulo $n$ is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other ...


A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu 2018 Nankai University

A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu

Theory and Applications of Graphs

The concept of monochromatic connection of graphs was introduced by Caro and Yuster in 2011. Recently, a lot of results have been published about it.
In this survey, we attempt to bring together all the results that dealt with it.
We begin with an introduction, and then classify the results into the following categories: monochromatic connection coloring of edge-version, monochromatic connection coloring of vertex-version, monochromatic index, monochromatic connection coloring of total-version.


Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj 2018 Oakland University

Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

Theory and Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of ...


Lights Out! On Cartesian Products, Travis Peters, John Goldwasser, Michael Young 2017 Iowa State University

Lights Out! On Cartesian Products, Travis Peters, John Goldwasser, Michael Young

Electronic Journal of Linear Algebra

The game LIGHTS OUT! is played on a 5 by 5 square grid of buttons; each button may be on or off. Pressing a button changes the on/o state of the light of the button pressed and of all its vertical and horizontal neighbors. Given an initial configuration of buttons that are on, the object of the game is to turn all the lights out. The game can be generalized to arbitrary graphs. In this paper, Cartesian Product graphs (that is, graphs of the form G\box H, where G and H are arbitrary finite, simple graphs) are investigated ...


Upper Bounds On Q-Spectral Radius Of Book-Free And/Or $K_{S,T}$-Free Graphs, Qi Kong, Ligong Wang 2017 Northwestern Polytechnical University

Upper Bounds On Q-Spectral Radius Of Book-Free And/Or $K_{S,T}$-Free Graphs, Qi Kong, Ligong Wang

Electronic Journal of Linear Algebra

In this paper, we prove two results about the signless Laplacian spectral radius $q(G)$ of a graph $G$ of order $n$ with maximum degree $\Delta$. Let $B_{n}=K_{2}+\overline{K_{n}}$ denote a book, i.e., the graph $B_{n}$ consists of $n$ triangles sharing an edge. The results are the following: (1) Let $1< k\leq l< \Delta < n$ and $G$ be a connected \{$B_{k+1},K_{2,l+1}$\}-free graph of order $n$ with maximum degree $\Delta$. Then $$\displaystyle q(G)\leq \frac{1}{4}[3\Delta+k-2l+1+\sqrt{(3\Delta+k-2l+1)^{2}+16l(\Delta+n-1)}$$ with equality if and only if $G$ is a strongly regular graph with parameters ($\Delta$, $k$, $l$). (2) Let $s\geq t\geq 3$, and let $G$ be a connected $K_{s,t}$-free graph of order $n$ $(n\geq s+t)$. Then $$q(G)\leq n+(s-t+1)^{1/t}n^{1-1/t}+(t-1)(n-1)^{1-3/t}+t-3.$$


On The Distance Signless Laplacian Spectral Radius Of Graphs And Digraphs, Dan Li, Guoping Wang, Jixiang Meng 2017 Xinjiang University,Urumqi

On The Distance Signless Laplacian Spectral Radius Of Graphs And Digraphs, Dan Li, Guoping Wang, Jixiang Meng

Electronic Journal of Linear Algebra

Let \eta(G) denote the distance signless Laplacian spectral radius of a connected graph G. In this paper,bounds for the distance signless Laplacian spectral radius of connected graphs are given, and the extremal graph with the minimal distance signless Laplacian spectral radius among the graphs with given vertex connectivity and minimum degree is determined. Furthermore, the digraph that minimizes the distance signless Laplacian spectral radius with given vertex connectivity is characterized.


An Exploration Of The Chromatic Polynomial, Amanda Aydelotte 2017 Boise State University

An Exploration Of The Chromatic Polynomial, Amanda Aydelotte

Mathematics Undergraduate Theses

In 1912, George Birkhoff was studying the Four Color Problem, and in doing so introduced the concept of the chromatic polynomial. While this did not end up directly contributing to proving that every map could be colored with four colors such that no region shares a border with another region of the same color, the chromatic polynomial has been found to have some very interesting properties. In this paper, it will be our goal to examine some of these properties and use them to determine information about their corresponding graphs.


Optimal Layout For A Component Grid, Michael W. Ebert 2017 California Polytechnic State University, San Luis Obispo

Optimal Layout For A Component Grid, Michael W. Ebert

Computer Science

Several puzzle games include a specific type of optimization problem: given components that produce and consume different resources and a grid of squares, find the optimal way to place the components to maximize output. I developed a method to evaluate potential solutions quickly and automated the solving of the problem using a genetic algorithm.


Edge Colorings Of Complete Multipartite Graphs Forbidding Rainbow Cycles, Peter Johnson, Andrew Owens 2017 Auburn University

Edge Colorings Of Complete Multipartite Graphs Forbidding Rainbow Cycles, Peter Johnson, Andrew Owens

Theory and Applications of Graphs

It is well known that if the edges of a finite simple connected graph on n vertices are colored so that no cycle is rainbow, then no more than n-1 colors can appear on the edges. In previous work it has been shown that the essentially different rainbow-cycle-forbidding edge colorings of Kn with n-1 colors appearing are in 1-1 correspondence with (can be encoded by) the (isomorphism classes of) full binary trees with n leafs. In the encoding, the natural Huffman labeling of each tree arising from the assignment of 1 to each leaf plays a role. Very recently ...


An Alternate Approach To Alternating Sums: A Method To Die For, Arthur T. Benjamin, Jennifer J. Quinn 2017 Harvey Mudd College

An Alternate Approach To Alternating Sums: A Method To Die For, Arthur T. Benjamin, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.


Fibonacci Deteminants - A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn 2017 Harvey Mudd College

Fibonacci Deteminants - A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn

Jennifer J. Quinn

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.


Fibonacci Determinants — A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn 2017 Harvey Mudd College

Fibonacci Determinants — A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn

Jennifer J. Quinn

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.


A High Quality, Eulerian 3d Fluid Solver In C++, LeJon Anthony McGowan 2017 California Polytechnic State University, San Luis Obispo

A High Quality, Eulerian 3d Fluid Solver In C++, Lejon Anthony Mcgowan

Computer Science

Fluids are a part of everyday life, yet are one of the hardest elements to properly render in computer graphics. Water is the most obvious entity when thinking of what a fluid simulation can achieve (and it is indeed the focus of this project), but many other aspects of nature, like fog, clouds, and particle effects. Real-time graphics like video games employ many heuristics to approximate these effects, but large-scale renderers aim to simulate these effects as closely as possible.

In this project, I wish to achieve effects of the latter nature. Using the Eulerian technique of discrete grids, I ...


An Extended Formulation Of The Convex Recoloring Problem On A Phylogenetic Tree, Sangho Shim 2017 Illinois State University

An Extended Formulation Of The Convex Recoloring Problem On A Phylogenetic Tree, Sangho Shim

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Repeat And Return Patterns In Double Occurrence Words, Lukas Nabergall 2017 University of South Florida

Repeat And Return Patterns In Double Occurrence Words, Lukas Nabergall

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Some Results In Combinatorial Number Theory, Karl Levy 2017 The Graduate Center, City University of New York

Some Results In Combinatorial Number Theory, Karl Levy

All Dissertations, Theses, and Capstone Projects

The first chapter establishes results concerning equidistributed sequences of numbers. For a given $d\in\mathbb{N}$, $s(d)$ is the largest $N\in\mathbb{N}$ for which there is an $N$-regular sequence with $d$ irregularities. We compute lower bounds for $s(d)$ for $d\leq 10000$ and then demonstrate lower and upper bounds $\left\lfloor\sqrt{4d+895}+1\right\rfloor\leq s(d)< 24801d^{3} + 942d^{2} + 3$ for all $d\geq 1$. In the second chapter we ask if $Q(x)\in\mathbb{R}[x]$ is a degree $d$ polynomial such that for $x\in[x_k]=\{x_1,\cdots,x_k\}$ we have $|Q(x)|\leq 1$, then how big can its lead coefficient be? We prove that there is a unique polynomial, which we call $L_{d,[x_k]}(x)$, with maximum lead coefficient under these constraints and construct an algorithm that generates $L_{d,[x_k]}(x)$.


Digital Commons powered by bepress