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

Discrete Mathematics and Combinatorics Commons

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

454 Full-Text Articles 535 Authors 41324 Downloads 57 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

454 full-text articles. Page 1 of 14.

Hybrid Proofs Of The Q-Binomial Theorem And Other Identities, Dennis Eichhorn, James McLaughlin, Andrew V. Sills 2016 University of California - Irvine

Hybrid Proofs Of The Q-Binomial Theorem And Other Identities, Dennis Eichhorn, James Mclaughlin, Andrew V. Sills

James McLaughlin

No abstract provided.


Polynomial Generalizations Of Two-Variable Ramanujan Type Identities, James McLaughlin, Andrew V. Sills 2016 West Chester University of Pennsylvania

Polynomial Generalizations Of Two-Variable Ramanujan Type Identities, James Mclaughlin, Andrew V. Sills

James McLaughlin

No abstract provided.


A New Summation Formula For Wp-Bailey Pairs, James McLaughlin 2016 West Chester University of Pennsylvania

A New Summation Formula For Wp-Bailey Pairs, James Mclaughlin

James McLaughlin

No abstract provided.


Graphs With Reciprocal Eigenvalue Properties, SWARUP KUMAR PANDA, Sukanta Pati 2016 IIT GUWAHATI

Graphs With Reciprocal Eigenvalue Properties, Swarup Kumar Panda, Sukanta Pati

Electronic Journal of Linear Algebra

In this paper, only simple graphs are considered. A graph G is nonsingular if its adjacency matrix A(G) is nonsingular. A nonsingular graph G satisfies reciprocal eigenvalue property (property R) if the reciprocal of each eigenvalue of the adjacency matrix A(G) is also an eigenvalue of A(G) and G satisfies strong reciprocal eigenvalue property (property SR) if the reciprocal of each eigenvalue of the adjacency matrix A(G) is also an eigenvalue of A(G) and they both have the same multiplicities. From the definitions property SR implies property R. Furthermore, for some classes of graphs (for ...


Kemeny's Constant And An Analogue Of Braess' Paradox For Trees, Steve Kirkland, Ze Zeng 2016 University of Manitoba

Kemeny's Constant And An Analogue Of Braess' Paradox For Trees, Steve Kirkland, Ze Zeng

Electronic Journal of Linear Algebra

Given an irreducible stochastic matrix M, Kemeny’s constant K(M) measures the expected time for the corresponding Markov chain to transition from any given initial state to a randomly chosen final state. A combinatorially based expression for K(M) is provided in terms of the weights of certain directed forests in a directed graph associated with M, yielding a particularly simple expression in the special case that M is the transition matrix for a random walk on a tree. An analogue of Braess’ paradox is investigated, whereby inserting an edge into an undirected graph can increase the value of ...


Regularity Of Mediatrices In Surfaces, Pilar Herreros, Mario Ponce, J.J. P. Veerman 2016 Portland State University

Regularity Of Mediatrices In Surfaces, Pilar Herreros, Mario Ponce, J.J. P. Veerman

J.J.P. Veerman

For distinct points p and q in a two-dimensional Riemannian manifold, one defines their mediatrix Lpq as the set of equidistant points to p and q. It is known that mediatrices have a cell decomposition consisting of a finite number of branch points connected by Lipschitz curves. This paper establishes additional geometric regularity properties of mediatrices. We show that mediatrices have the radial linearizability property, which implies that at each point they have a geometrically defined derivative in the branching directions. Also, we study the particular case of mediatrices on spheres, by showing that they are Lipschitz simple closed curves ...


Kernels Of Directed Graph Laplacians, John S. Caughman IV, J. J. P. Veerman 2016 Portland State University

Kernels Of Directed Graph Laplacians, John S. Caughman Iv, J. J. P. Veerman

J.J.P. Veerman

Let G denote a directed graph with adjacency matrix Q and in- degree matrix D. We consider the Kirchhoff matrix L = D − Q, sometimes referred to as the directed Laplacian. A classical result of Kirchhoff asserts that when G is undirected, the multiplicity of the eigenvalue 0 equals the number of connected components of G. This fact has a meaningful generalization to directed graphs, as was observed by Chebotarev and Agaev in 2005. Since this result has many important applications in the sciences, we offer an independent and self-contained proof of their theorem, showing in this paper that the algebraic ...


On A Convex Set With Nondifferentiable Metric Projection, Shyan S. Akmal, Nguyen Mau Nam, J.J. P. Veerman 2016 Portland State University

On A Convex Set With Nondifferentiable Metric Projection, Shyan S. Akmal, Nguyen Mau Nam, J.J. P. Veerman

J.J.P. Veerman

A remarkable example of a nonempty closed convex set in the Euclidean plane for which the directional derivative of the metric projection mapping fails to exist was constructed by A. Shapiro. In this paper, we revisit and modify that construction to obtain a convex set with smooth boundary which possesses the same property.


Tridiagonal Matrices And Boundary Conditions, J.J. P. Veerman, David K. Hammond 2016 Portland State University

Tridiagonal Matrices And Boundary Conditions, J.J. P. Veerman, David K. Hammond

J.J.P. Veerman

We describe the spectra of certain tridiagonal matrices arising from differential equations commonly used for modeling flocking behavior. In particular we consider systems resulting from allowing an arbitrary boundary condition for the end of a one-dimensional flock. We apply our results to demonstrate how asymptotic stability for consensus and flocking systems depends on the imposed boundary condition.


Classifying Resolving Lists By Distances Between Members, Paul Feit 2016 University of Texas of the Permian Basin

Classifying Resolving Lists By Distances Between Members, Paul Feit

Theory and Applications of Graphs

L

Let $G$ be a connected graph and let $w_1,\cdots w_r$ be a list of vertices. We refer the choice of a triple $(r;G;w_1,\cdots w_r)$, as a {\em metric selection.} Let $\rho$ be the shortest path metric of $G$. We say that $w_1,\cdots w_r$ {\em resolves $G$ (metricly)\/} if the function $c:V(G)\mapsto\bbz^r$ given by

\[ x\mapsto (\rho (w_1,x),\cdots ,\rho (w_r,x))\]

is injective. We refer to this function the {\em code map,} and to its image as the {\em codes\/} of the triple $(r;G;w_1,\cdots ,w_r ...


Group-Antimagic Labelings Of Multi-Cyclic Graphs, Dan Roberts, Richard M. Low 2016 Illinois Wesleyan University

Group-Antimagic Labelings Of Multi-Cyclic Graphs, Dan Roberts, Richard M. Low

Theory and Applications of Graphs

Let $A$ be a non-trivial abelian group. A connected simple graph $G = (V, E)$ is $A$-\textbf{antimagic} if there exists an edge labeling $f: E(G) \to A \backslash \{0\}$ such that the induced vertex labeling $f^+: V(G) \to A$, defined by $f^+(v) = \Sigma$ $\{f(u,v): (u, v) \in E(G) \}$, is a one-to-one map. The \textit{integer-antimagic spectrum} of a graph $G$ is the set IAM$(G) = \{k: G \textnormal{ is } \mathbb{Z}_k\textnormal{-antimagic and } k \geq 2\}$. In this paper, we analyze the integer-antimagic spectra for various classes of multi-cyclic graphs.


An Expansion Property Of Boolean Linear Maps, Yaokun Wu, Zeying Xu, Yinfeng Zhu 2016 Shanghai Jiao Tong University

An Expansion Property Of Boolean Linear Maps, Yaokun Wu, Zeying Xu, Yinfeng Zhu

Electronic Journal of Linear Algebra

Given a finite set $K$, a Boolean linear map on $K$ is a map $f$ from the set $2^K$ of all subsets of $K$ into itself with $f(\emptyset )=\emptyset$ such that $f(A\cup B)=f(A)\cup f(B)$ holds for all $A,B\in 2^K$. For fixed subsets $X, Y$ of $K$, to predict if $Y$ is reachable from $X$ in the dynamical system driven by $f$, one can assume the existence of nonnegative integers $h$ with $f^h(X)=Y$, find an upper bound $\alpha$ for the minimum of all such assumed integers $h ...


Ádám's Conjecture And Arc Reversal Problems, Claudio D. Salas 2016 California State University - San Bernardino

Ádám's Conjecture And Arc Reversal Problems, Claudio D. Salas

Electronic Theses, Projects, and Dissertations

A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address ...


Upset Paths And 2-Majority Tournaments, Rana Ali Alshaikh 2016 California State University, San Bernardino

Upset Paths And 2-Majority Tournaments, Rana Ali Alshaikh

Electronic Theses, Projects, and Dissertations

In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when ...


Hill's Diagrammatic Method And Reduced Graph Powers, Gregory D. Smith, Richard Hammack 2016 The College of William & Mary

Hill's Diagrammatic Method And Reduced Graph Powers, Gregory D. Smith, Richard Hammack

Biology and Medicine Through Mathematics Conference

No abstract provided.


Discrete Stability Of Dpg Methods, Ammar Harb 2016 Portland State University

Discrete Stability Of Dpg Methods, Ammar Harb

Dissertations and Theses

This dissertation presents a duality theorem of the Aubin-Nitsche type for discontinuous Petrov Galerkin (DPG) methods. This explains the numerically observed higher convergence rates in weaker norms. Considering the specific example of the mild-weak (or primal) DPG method for the Laplace equation, two further results are obtained. First, for triangular meshes, the DPG method continues to be solvable even when the test space degree is reduced, provided it is odd. Second, a non-conforming method of analysis is developed to explain the numerically observed convergence rates for a test space of reduced degree. Finally, for rectangular meshes, the test space is ...


The Distance Spectral Radius Of Graphs With Given Number Of Odd Vertices, Hongying Lin, Bo Zhou 2016 South China Normal University

The Distance Spectral Radius Of Graphs With Given Number Of Odd Vertices, Hongying Lin, Bo Zhou

Electronic Journal of Linear Algebra

The graphs with smallest, respectively largest, distance spectral radius among the connected graphs, respectively trees with a given number of odd vertices, are determined. Also, the graphs with the largest distance spectral radius among the trees with a given number of vertices of degree 3, respectively given number of vertices of degree at least 3, are determined. Finally, the graphs with the second and third largest distance spectral radius among the trees with all odd vertices are determined.


Math And Sudoku: Exploring Sudoku Boards Through Graph Theory, Group Theory, And Combinatorics, Kyle Oddson 2016 Portland State University

Math And Sudoku: Exploring Sudoku Boards Through Graph Theory, Group Theory, And Combinatorics, Kyle Oddson

Student Research Symposium

Encoding Sudoku puzzles as partially colored graphs, we state and prove Akman’s theorem [1] regarding the associated partial chromatic polynomial [5]; we count the 4x4 sudoku boards, in total and fundamentally distinct; we count the diagonally distinct 4x4 sudoku boards; and we classify and enumerate the different structure types of 4x4 boards.


Global Supply Sets In Graphs, Christian G. Moore 2016 East Tennessee State University

Global Supply Sets In Graphs, Christian G. Moore

Electronic Theses and Dissertations

For a graph G=(V,E), a set S⊆V is a global supply set if every vertex v∈V\S has at least one neighbor, say u, in S such that u has at least as many neighbors in S as v has in V \S. The global supply number is the minimum cardinality of a global supply set, denoted γgs (G). We introduce global supply sets and determine the global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.


Signed Graphs With Small Positive Index Of Inertia, Guihai Yu, Lihua Feng, Hui Qu 2016 Shandong Institute of Business and Technology

Signed Graphs With Small Positive Index Of Inertia, Guihai Yu, Lihua Feng, Hui Qu

Electronic Journal of Linear Algebra

In this paper, the signed graphs with one positive eigenvalue are characterized, and the signed graphs with pendant vertices having exactly two positive eigenvalues are determined. As a consequence, the signed trees, the signed unicyclic graphs and the signed bicyclic graphs having one or two positive eigenvalues are characterized.


Digital Commons powered by bepress