Discrete Mathematics and Combinatorics Commons^™

Structural Properties Of Power Digraphs Modulo N, Joseph Kramer-Miller

Mathematical Sciences Technical Reports (MSTR)

We define G(n, k) to be a directed graph whose set of vertices is {0, 1, ..., n−1} and whose set of edges is defined by a modular relation. We say that G(n, k) is symmetric of order m if we can partition G(n, k) into subgraphs, each containing m components, such that all the components in a subgraph are isomorphic. We develop necessary and sufficient conditions for G(n, k) to contain symmetry when n is odd and square-free. Additionally, we use group theory to describe the structural properties of the subgraph of G(n, k) containing only those vertices relatively …

Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke

Computer Science: Faculty Publications

The Yao graph for k = 4, Y₄, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three properties: planarity, connectedness, and whether the directed graphs are spanners.

Cyclic, F-Cyclic, And Bicyclic Decompositions Of The Complete Graph Into The 4-Cycle With A Pendant Edge., Daniel Shelton Cantrell

Electronic Theses and Dissertations

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of:

(1) a single cycle of length v,

(2) f fixed points and a cycle of length v − f, or

(3) two disjoint cycles.

The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of K_v.

Decompositions Of Mixed Graphs With Partial Orientations Of The P4., Adam M. Meadows

Electronic Theses and Dissertations

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x …

Locating-Domination In Complementary Prisms., Kristin Renee Stone Holmes

Electronic Theses and Dissertations

Let G = (V (G), E(G)) be a graph and G̅ be the complement of G. The complementary prism of G, denoted GG̅, is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. A set D ⊆ V (G) is a locating-dominating set of G if for every u ∈ V (G)D, its neighborhood N(u)⋂D is nonempty and distinct from N( …

Extremal Random Walks On Trees, Meng Wang

Mathematics, Statistics, and Computer Science Honors Projects

We study random walks on trees, where we iteratively move from one vertex to a randomly chosen adjacent vertex. We study two quantities arising in random walks: the hitting time and the mixing time. The hitting time is the expected number of steps to walk between a chosen pair of vertices. The mixing time is the expected number of steps before the distribution of the current state is proportional to its degree. For a fixed tree size, we prove that the star is the unique minimizing structure and the path is the unique maximizing structure for both quantities.

Counting On Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07

All HMC Faculty Publications and Research

Chebyshev polynomials have several elegant combinatorial interpretations. Specificially, the Chebyshev polynomials of the first kind are defined by T₀(x) = 1, T₁(x) = x, and T_n(x) = 2x T_n-1(x) - T_n-2(x). Chebyshev polynomials of the second kind U_n(x) are defined the same way, except U₁(x) = 2x. T_n and U_n are shown to count tilings of length n strips with squares and dominoes, where the tiles are given weights and sometimes color. Using these interpretations, many identities satisfied by Chebyshev polynomials can be given …

The Maximum Rectilinear Crossing Number Of The N Dimensional Cube Graph, Matthew Alpert, Elie Feder, Heiko Harborth, Sheldon Klein

Publications and Research

We find a.nd prove the maximum rectilinear crossing n1.1mber of the three-dimensional cube graph (Q₃). We demonstrate a method of drawing then-cube graph, Q_n., with many crossings, and thus find a lower bound for the maximum rectilinear crossing number of Q_n. We conjecture that this bound is sharp. We also prove an upper bound for the maximum rectilinear crossing number of Q_n.

Integral Orthogonal Bases Of Small Height For Real Polynomial Spaces, Lenny Fukshansky

CMC Faculty Publications and Research

Let P_N(R) be the space of all real polynomials in N variables with the usual inner product < , > on it, given by integrating over the unit sphere. We start by deriving an explicit combinatorial formula for the bilinear form representing this inner product on the space of coefficient vectors of all polynomials in P_N(R) of degree ≤ M. We exhibit two applications of this formula. First, given a finite dimensional subspace V of P_N(R) defined over Q, we prove the existence of an orthogonal basis for (V, < , >), consisting of polynomials of small height …

The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz

Faculty Publications & Research

Erdős and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West

Faculty Publications & Research

A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γ_R(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γ_R(G) + …

Discrete Mathematics With Proof Second Edition, Eric Gossett

Faculty Books

Discrete mathematics has become increasingly popular in recent years due to its growing applications in the field of computer science. Discrete Mathematics with Proof, Second Edition continues to facilitate an up-to-date understanding of this important topic, exposing readers to a wide range of modern and technological applications. The book begins with an introductory chapter that provides an accessible explanation of discrete mathematics. Subsequent chapters explore additional related topics including counting, finite probability theory, recursion, formal models in computer science, graph theory, trees, the concepts of functions, and relations.

The Maximum Of The Maximum Rectilinear Crossing Numbers Of D-Regular Graphs Of Order N, Matthew Alpert, Elie Feder, Heiko Harborth

Publications and Research

We extend known results regarding the maximum rectilinear crossing number of the cycle graph (Cn) and the complete graph (Kn ) to the class of general d-regular graphs Rn,d. We present the generalized star drawings of the d-regular graphs Sn,d of order n where n + d ≡ 1 (mod 2) and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of Sn,d for n ≡ d ≡ 0 (mod 2) is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by …

Lifting Bailey Pairs To Wp-Bailey Pairs, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

A pair of sequences (αn(a,k,q),βn(a,k,q)) such that α0(a,k,q)=1 and βn(a,k,q)=∑nj=0(k/a;q)n−j(k;q)n+j(q;q)n−j(aq;q)n+jαj(a,k,q) is termed aWP-Bailey Pair . Upon setting k=0 in such a pair we obtain a Bailey pair. In the present paper we consider the problem of “lifting” a Bailey pair to a WP-Bailey pair, and use some of the new WP-Bailey pairs found in this way to derive some new identities between basic hypergeometric series and new single-sum and double-sum identities of the Rogers–Ramanujan–Slater type.

Some More Identities Of Rogers-Ramanujan Type, Douglas Bowman, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

In this we paper we prove several new identities of the Rogers-Ramanujan-Slater type. These identities were found as the result of computer searches. The proofs involve a variety of techniques, including series-series identities, Bailey pairs, a theorem of Watson on basic hypergeometric series, generating functions and miscellaneous methods.

Combinatorics Of Ramanujan-Slater Type Identities, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

We provide the missing member of a family of four q-series identities related to the modulus 36, the other members having been found by Ramanujan and Slater. We examine combinatorial implications of the identities in this family, and of some of the identities we considered inIdentities of the Ramanujan-Slater type related to the moduli 18 and 24.

Rogers-Ramanujan Computer Searches, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

We describe three computer searches (in PARI/GP, Maple, and Mathematica, respectively) which led to the discovery of a number of identities of Rogers–Ramanujan type and identities of false theta functions.

Transformée En Échelle De Signaux Stationnaires, Daniel Alpay, Mamadou Mboup

Mathematics, Physics, and Computer Science Faculty Articles and Research

Using the scale transform of a discrete time signal we define a new family of linear systems. We focus on a particular case related to function theory in the bidisk.

The Schur Transformation For Nevanlinna Functions: Operator Representations, Resolvent Matrices, And Orthogonal Polynomials, Daniel Alpay, A. Dijksma, H. Langer

Mathematics, Physics, and Computer Science Faculty Articles and Research

A Nevanlinna function is a function which is analytic in the open upper half plane and has a non-negative imaginary part there. In this paper we study a fractional linear transformation for a Nevanlinna function n with a suitable asymptotic expansion at ∞, that is an analogue of the Schur transformation for contractive analytic functions in the unit disc. Applying the transformation p times we find a Nevanlinna function np which is a fractional linear transformation of the given function n. The main results concern the effect of this transformation to the realizations of n and np, by which we …

On The Number Of K-Gons In Finite Projective Planes, Felix Lazebnik, Keith Mellinger, Oscar Vega

Mathematics Articles

Let π = πq denote a finite projective plane of order q, and let G = Levi(π) be the bipartite point-line incidence graph of π. For k ≥ 3, let c2k(π) denote the number of cycles of length 2k in G. Are the numbers c2k(π) the same for all πq? We prove that this is the case for k = 3, 4, 5, 6 by computing these numbers.

Superbimatrices And Their Generalizations, Florentin Smarandache, W.B Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

The systematic study of supermatrices and super linear algebra has been carried out in 2008. These new algebraic structures find their applications in fuzzy models, Leontief economic models and data-storage in computers. In this book the authors introduce the new notion of superbimatrices and generalize it to super trimatrices and super n-matrices. Study of these structures is not only interesting and innovative but is also best suited for the computerized world. The main difference between simple bimatrices and super bimatrices is that in case of simple bimatrices we have only one type of product defined on them, whereas in case …

The Orchard Crossing Number Of An Abstract Graph, Elie Feder, David Garber

Publications and Research

.We introduce the Orchard crossing number, which is defined in a similar way to the well-known rectilinear crossing number. We compute the Orchard crossing number for some simple families of graphs. We also prove some properties of this crossing number.

Moreover, we define a variant of this crossing number which is tightly connected to the rectilinear crossing number, and compute it for some simple families of graphs.

Generalized Q-Functions And Dirichlet-To-Neumann Maps For Elliptic Differential Operators, Daniel Alpay, Jussi Behrndt

Mathematics, Physics, and Computer Science Faculty Articles and Research

The classical concept of Q-functions associated to symmetric and selfadjoint operators due to M.G. Krein and H. Langer is extended in such a way that the Dirichlet-to-Neumann map in the theory of elliptic differential equations can be interpreted as a generalized Q-function. For couplings of uniformly elliptic second order differential expression on bounded and unbounded domains explicit Krein type formulas for the difference of the resolvents and trace formulas in an H2-framework are obtained.

Krein Systems, Daniel Alpay, I. Gohberg, M. A. Kaashoek, L. Lerer, A. Sakhnovich

Mathematics, Physics, and Computer Science Faculty Articles and Research

In the present paper we extend results of M.G. Krein associated to the spectral problem for Krein systems to systems with matrix valued accelerants with a possible jump discontinuity at the origin. Explicit formulas for the accelerant are given in terms of the matrizant of the system in question. Recent developments in the theory of continuous analogs of the resultant operator play an essential role.

Restrained And Other Domination Parameters In Complementary Prisms., Wyatt Jules Desormeaux

Electronic Theses and Dissertations

In this thesis, we will study several domination parameters of a family of graphs known as complementary prisms. We will first present the basic terminology and definitions necessary to understand the topic. Then, we will examine the known results addressing the domination number and the total domination number of complementary prisms. After this, we will present our main results, namely, results on the restrained domination number of complementary prisms. Subsequently results on the distance - k domination number, 2-step domination number and stratification of complementary prisms will be presented. Then, we will characterize when a complementary prism is Eulerian or …

Queen's Domination Using Border Squares And (A,B)-Restricted Domination, Anne Sinko, Peter J. Slater

Mathematics Faculty Publications

In this paper we introduce a variant on the long studied, highly entertaining, and very difficult problem of determining the domination number of the queen's chessboard graph, that is, determining how few queens are needed to protect all of the squares of a k by k chessboard. Motivated by the problem of minimum redundance domination, we consider the problem of determining how few queens restricted to squares on the border can be used to protect the entire chessboard. We give exact values of "border-queens" required for the k by k chessboard when 1≤k≤13. For the general case, we …

Tiling Proofs Of Recent Sum Identities Involving Pell Numbers, Arthur T. Benjamin, Sean S. Plott '08, James A. Sellers

All HMC Faculty Publications and Research

In a recent note, Santana and Diaz-Barrero proved a number of sum identities involving the well-known Pell numbers. Their proofs relied heavily on the Binet formula for the Pell numbers. Our goal in this note is to reconsider these identities from a purely combinatorial viewpoint. We provide bijective proofs for each of the results by interpreting the Pell numbers as enumerators of certain types of tilings. In turn, our proofs provide helpful insight for straightforward generalizations of a number of the identities.

Double Domination Of Complementary Prisms., Lamont D. Vaughan

Electronic Theses and Dissertations

The complementary prism of a graph G is obtained from a copy of G and its complement G̅ by adding a perfect matching between the corresponding vertices of G and G̅. For any graph G, a set D ⊆ V (G) is a double dominating set (DDS) if that set dominates every vertex of G twice. The double domination number, denoted γ_×2(G), is the cardinality of a minimum double dominating set of G. We have proven results on graphs of small order, specific families and lower bounds on γ_{×2 …}

Finding Edge And Vertex Induced Cycles Within Circulants., Trina Marcella Wooten

Electronic Theses and Dissertations

Let H be a graph. G is a subgraph of H if V (G) ⊆ V (H) and E(G) ⊆ E(H). The subgraphs of H can be used to determine whether H is planar, a line graph, and to give information about the chromatic number. In a recent work by Beeler and Jamison [3], it was shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As …

A Sharp Bound For The Reconstruction Of Partitions, Vincent Vatter

Dartmouth Scholarship

Answer in g a question of Cameron, Pretzel and Siemons proved that every integer partition of n >= 2(k + 3) (k + 1) can be reconstructed from its set of k-deletions. We describe a new reconstruction algorithm that lowers this bound to n >= k(2) + 2k and present examples showing that this bound is best possible.