Mathematics Commons^™

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.

On The Attainability Of Upper Bounds For The Circular Chromatic Number Of K4-Minor-Free Graphs., Tracy Lance Holt

Electronic Theses and Dissertations

Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χ_c(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and …

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

All HMC Faculty Publications and Research

No abstract provided in this article.

Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu

Computer Science: Faculty Publications

A multi-graph G on n vertices is (k,ℓ)-sparse if every subset of n^′⩽n vertices spans at most kn^′-ℓ edges. G is tight if, in addition, it has exactly kn-ℓ edges. For integer valuesk and ℓ∈[0,2k), we characterize the (k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)-pebble games. [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.

The 99th Fibonacci Identity, Arthur T. Benjamin, Alex K. Eustis '06, Sean S. Plott '08

All HMC Faculty Publications and Research

We provide elementary combinatorial proofs of several Fibonacci and Lucas number identities left open in the book Proofs That Really Count [1], and generalize these to Gibonacci sequences G_n that satisfy the Fibonacci recurrence, but with arbitrary real initial conditions. We offer several new identities as well.

[1] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions, 27, Mathematical Association of America, Washington, DC, 2003

Paint It Black -- A Combinatorial Yawp, Arthur T. Benjamin, Jennifer J. Quinn, James A. Sellers, Mark A. Shattuck

All HMC Faculty Publications and Research

No abstract provided in this paper.

A Combinatorial Approach To Fibonomial Coefficients, Arthur T. Benjamin, Sean S. Plott '08

All HMC Faculty Publications and Research

A combinatorial argument is used to explain the integrality of Fibonomial coefficients and their generalizations. The numerator of the Fibonomial coeffcient counts tilings of staggered lengths, which can be decomposed into a sum of integers, such that each integer is a multiple of the denominator of the Fibonomial coeffcient. By colorizing this argument, we can extend this result from Fibonacci numbers to arbitrary Lucas sequences.

On KS,T-Minors In Graphs With Given Average Degree, A. V. Kostochka, N. Prince

Faculty Publications & Research

Let D(H) be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on D(H) for almost all graphs H and proved that for 'balanced' H random graphs provide extremal examples and determine the extremal function. Examples of 'unbalanced graphs' are complete bipartite graphs K_s,t for a fixed s and large t. Myers proved upper bounds on D(K_s,t ) and made a conjecture on the order of magnitude of D(K_s,t ) for a fixed s and …

Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince

Faculty Publications & Research

Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that …

Ramanujan-Slater Type Identities Related To The Moduli 18 And 24, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

We present several new families of Rogers–Ramanujan type identities related to the moduli 18 and 24. A few of the identities were found by either Ramanujan, Slater, or Dyson, but most are believed to be new. For one of these families, we discuss possible connections with Lie algebras. We also present two families of related false theta function identities.

G-Perfect Nonlinear Functions, James A. Davis, Laurent Poinsot

Department of Math & Statistics Faculty Publications

Perfect nonlinear functions are used to construct DES-like cryptosystems that are resistant to differential attacks. We present generalized DES-like cryptosystems where the XOR operation is replaced by a general group action. The new cryptosystems, when combined with G-perfect nonlinear functions (similar to classical perfect nonlinear functions with one XOR replaced by a general group action), allow us to construct systems resistant to modified differential attacks. The more general setting enables robust cryptosystems with parameters that would not be possible in the classical setting. We construct several examples of G-perfect nonlinear functions, both Z₂ -valued and Z^{a …}

Rogers-Ramanujan-Slater Type Identities, James Mclaughlin, Andrew V. Sills, Peter Zimmer

Mathematics Faculty Publications

In this survey article, we present an expanded version of Lucy Slater’s famous list of identities of the Rogers-Ramanujan type, including identities of similar type, which were discovered after the publication of Slater’s papers, and older identities (such as those in Ramanujan’s lost notebook) which were not included in Slater’s papers. We attempt to supply the earliest known reference for each identity. Also included are identities of false theta functions, along with their relationship to Rogers Ramanujan type identities. We also describe several ways in which pairs/larger sets of identities may be related, as well as dependence relationships between identities.

On The Reproducing Kernel Hilbert Spaces Associated With The Fractional And Bi-Fractional Brownian Motions, Daniel Alpay, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

We present decompositions of various positive kernels as integrals or sums of positive kernels. Within this framework we study the reproducing kernel Hilbert spaces associated with the fractional and bi-fractional Brownian motions. As a tool, we define a new function of two complex variables, which is a natural generalization of the classical Gamma function for the setting we consider.

Distribution Of The Number Of Encryptions In Revocation Schemes For Stateless Receivers, Christopher Eagle, Zhicheng Gao, Mohamed Omar, Daniel Panario, Bruce Richmond

All HMC Faculty Publications and Research

We study the number of encryptions necessary to revoke a set of users in the complete subtree scheme (CST) and the subset-difference scheme (SD). These are well-known tree based broadcast encryption schemes. Park and Blake in: Journal of Discrete Algorithms, vol. 4, 2006, pp. 215--238, give the mean number of encryptions for these schemes. We continue their analysis and show that the limiting distribution of the number of encryptions for these schemes is normal. This implies that the mean numbers of Park and Blake are good estimates for the number of necessary encryptions used by these schemes.

Rational Functions Associated To The White Noise Space And Related Topics, Daniel Alpay, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

Motivated by the hyper-holomorphic case we introduce and study rational functions in the setting of Hida’s white noise space. The Fueter polynomials are replaced by a basis computed in terms of the Hermite functions, and the Cauchy-Kovalevskaya product is replaced by the Wick product.

A Characterization Of Schur Multipliers Between Character-Automorphic Hardy Spaces, Daniel Alpay, M. Mboup

Mathematics, Physics, and Computer Science Faculty Articles and Research

We give a new characterization of character-automorphic Hardy spaces of order 2 and of their contractive multipliers in terms of de Branges Rovnyak spaces. Keys tools in our arguments are analytic extension and a factorization result for matrix-valued analytic functions due to Leech.

N- Linear Algebra Of Type I And Its Applications, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

With the advent of computers one needs algebraic structures that can simultaneously work with bulk data. One such algebraic structure namely n-linear algebras of type I are introduced in this book and its applications to n-Markov chains and n-Leontief models are given. These structures can be thought of as the generalization of bilinear algebras and bivector spaces. Several interesting n-linear algebra properties are proved. This book has four chapters. The first chapter just introduces n-group which is essential for the definition of nvector spaces and n-linear algebras of type I. Chapter two gives the notion of n-vector spaces and several …

Weight Systems For Milnor Invariants, Blake Mellor

Mathematics Faculty Works

We use Polyak's skein relation to give a new proof that Milnor's string link homotopy invariants are finite type invariants, and to develop a recursive relation for their associated weight systems. We show that the obstruction to the triviality of these weight systems is the presence of a certain kind of spanning tree in the intersection graph of a chord diagram.

Intrinsic Linking And Knotting Are Arbitrarily Complex, Erica Flapan, Blake Mellor, Ramin Naimi

Mathematics Faculty Works

We show that, given any n and α, every embedding of any sufficiently large complete graph in R³ contains an oriented link with components Q₁, ..., Q_n such that for every i≠j, $|\lk(Q_i,Q_j)|\geq\alpha$ and |a₂(Qi)|≥α, where a₂(Q_i) denotes the second coefficient of the Conway polynomial of Q_i.

Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince

Noah Prince

Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that …

On KS,T-Minors In Graphs With Given Average Degree, A. V. Kostochka, N. Prince

Noah Prince

Let D(H) be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on D(H) for almost all graphs H and proved that for 'balanced' H random graphs provide extremal examples and determine the extremal function. Examples of 'unbalanced graphs' are complete bipartite graphs K_s,t for a fixed s and large t. Myers proved upper bounds on D(K_s,t ) and made a conjecture on the order of magnitude of D(K_s,t ) for a fixed s and …