# Discrete Mathematics and Combinatorics Commons™

## All Articles in Discrete Mathematics and Combinatorics

791 full-text articles. Page 1 of 27.

Vector Partitions, 2018 East Tennessee State University

#### Vector Partitions, Jennifer French

##### Electronic Theses and Dissertations

Integer partitions have been studied by many mathematicians over hundreds of years. Many identities exist between integer partitions, such as Euler’s discovery that every number has the same amount of partitions into distinct parts as into odd parts. These identities can be proven using methods such as conjugation or generating functions. Over the years, mathematicians have worked to expand partition identities to vectors. In 1963, M. S. Cheema proved that every vector has the same number of partitions into distinct vectors as into vectors with at least one component odd. This parallels Euler’s result for integer partitions. The ...

On Passing The Buck, 2018 Cedarville University

#### On Passing The Buck, Adam J. Hammett, Anna Joy Yang

Imagine there are n>1 people seated around a table, and person S starts with a fair coin they will flip to decide whom to hand the coin next -- if "heads" they pass right, and if "tails" they pass left. This process continues until all people at the table have "touched" the coin. Curiously, it turns out that all people seated at the table other than S have the same probability 1/(n-1) of being last to touch the coin. In fact, Lovasz and Winkler ("A note on the last new vertex visited by a random walk," J. Graph Theory ...

On Passing The Buck, 2018 Cedarville University

#### On Passing The Buck, Adam J. Hammett, Anna Joy Yang

##### The Research and Scholarship Symposium

Imagine there are n>1 people seated around a table, and person S starts with a fair coin they will flip to decide whom to hand the coin next -- if "heads" they pass right, and if "tails" they pass left. This process continues until all people at the table have "touched" the coin. Curiously, it turns out that all people seated at the table other than S have the same probability 1/(n-1) of being last to touch the coin. In fact, Lovasz and Winkler ("A note on the last new vertex visited by a random walk," J. Graph Theory ...

Characterizing Graphs Of Maximum Principal Ratio, 2018 Carnegie Mellon University

#### Characterizing Graphs Of Maximum Principal Ratio, Michael Tait, Josh Tobin

##### Electronic Journal of Linear Algebra

The principal ratio of a connected graph, denoted γ(G), is the ratio of the maximum and minimum entries of its Perron eigenvector. Cioaba and Gregory (2007) conjectured that the graph on n vertices maximizing γ(G) is a kite graph, that is, a complete graph with a pendant path. In this paper, their conjecture is proved

2018 Department of Mathematics, Komi Science Centre UD RAS

#### The Hafnian And A Commutative Analogue Of The Grassmann Algebra, Dmitry Efimov

##### Electronic Journal of Linear Algebra

A close relationship between the determinant, the pfaffian, and the Grassmann algebra is well-known. In this paper, a similar relation between the permanent, the hafnian, and a commutative analogue of the Grassmann algebra is described. Using the latter, some new properties of the hafnian are proved.

Policy-Preferred Paths In As-Level Internet Topology Graphs, 2018 University of Louisiana at Lafayette

#### Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

##### Theory and Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to ...

Families Of Graphs With Maximum Nullity Equal To Zero Forcing Number, 2018 Iowa State University

#### Families Of Graphs With Maximum Nullity Equal To Zero Forcing Number, Joseph S. Alameda, Emelie Curl, Armando Grez, Leslie Hogben, O'Neill Kingston, Alex Schulte, Derek Young, Michael Young

##### Mathematics Publications

The maximum nullity of a simple graph G, denoted M(G), is the largest possible nullity over all symmetric real matrices whose ijth entry is nonzero exactly when fi, jg is an edge in G for i =6 j, and the iith entry is any real number. The zero forcing number of a simple graph G, denoted Z(G), is the minimum number of blue vertices needed to force all vertices of the graph blue by applying the color change rule. This research is motivated by the longstanding question of characterizing graphs G for which M(G) = Z(G). The ...

Educational Magic Tricks Based On Error-Detection Schemes, 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, 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, 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, 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, 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 ...

The Graphs And Matroids Whose Only Odd Circuits Are Small, 2018 Louisiana State University

#### The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

##### LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph ...

A Survey On Monochromatic Connections Of Graphs, 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.

Zero Forcing And Power Domination For Graph Products, 2018 Westminster College - Fulton

#### Zero Forcing And Power Domination For Graph Products, Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben, Violeta Vasilevska, Brian Wissman

##### Mathematics Publications

The power domination number arose from the monitoring of electrical networks, and methods for its determination have the associated application. The zero forcing number arose in the study of maximum nullity among symmetric matrices described by a graph (and also in control of quantum systems and in graph search algorithms). There has been considerable effort devoted to the determination of the power domination number, the zero forcing number, and maximum nullity for specific families of graphs. In this paper we exploit the natural relationship between power domination and zero forcing to obtain results for the power domination number of tensor ...

The Relationship Between K-Forcing And K-Power Domination, 2018 Texas State University

#### The Relationship Between K-Forcing And K-Power Domination, Daniela Ferrero, Leslie Hogben, Franklin H.J. Kenter, Michael Young

##### Mathematics Publications

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of k-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, k-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of k-forcing and k-power domination, providing a new approach to analyze both ...

Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, 2018 Iowa State University

#### Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhart, Theodore Tranel

##### Mathematics Publications

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.

Generalized Matching Preclusion In Bipartite Graphs, 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 ...

2018 Georgia Southern University

#### A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

##### Theory and Applications of Graphs

Given a graph $H$ and a positive integer $k$, the $k$-color Gallai-Ramsey number $gr_{k}(K_{3} : H)$ is defined to be the minimum number of vertices $n$ for which any $k$-coloring of the complete graph $K_{n}$ contains either a rainbow triangle or a monochromatic copy of $H$. The behavior of these numbers is rather well understood when $H$ is bipartite but when $H$ is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs $H$ to a value that we conjecture to be sharp ...

Lights Out! On Cartesian Products, 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 ...