Discrete Mathematics and Combinatorics Commons^™

Efficient Domination In Knights Graphs, Anne Sinko, Peter J. Slater

Mathematics Faculty Publications

The influence of a vertex set S ⊆V(G) is I(S) = Σ_v∈S(1 + deg(v)) = Σ_v∈S |N[v]|, which is the total amount of domination done by the vertices in S. The efficient domination number F(G) of a graph G is equal to the maximum influence of a packing, that is, F(G) is the maximum number of vertices one can dominate under the restriction that no vertex gets dominated more than once.

In …

Self-Avoiding Walks And Fibonacci Numbers, Arthur T. Benjamin

All HMC Faculty Publications and Research

By combinatorial arguments, we prove that the number of self-avoiding walks on the strip {0, 1} × Z is 8F_n − 4 when n is odd and is 8F_n − n when n is even. Also, when backwards moves are prohibited, we derive simple expressions for the number of length n self-avoiding walks on {0, 1} × Z, Z × Z, the triangular lattice, and the cubic lattice.

Summing Cubes By Counting Rectangles, Arthur T. Benjamin, Jennifer J. Quinn, Calyssa Wurtz

All HMC Faculty Publications and Research

No abstract provided in this article.

The Zeta Function Of A Hypergraph, Christopher K. Storm

Dartmouth Scholarship

We generalize the Ihara-Selberg zeta function to hypergraphs in a natural way. Hashimoto's factorization results for biregular bipartite graphs apply, leading to exact factorizations. For $(d,r)$-regular hypergraphs, we show that a modified Riemann hypothesis is true if and only if the hypergraph is Ramanujan in the sense of Winnie Li and Patrick Solé. Finally, we give an example to show how the generalized zeta function can be applied to graphs to distinguish non-isomorphic graphs with the same Ihara-Selberg zeta function.

Double Domination Edge Critical Graphs., Derrick Wayne Thacker

Electronic Theses and Dissertations

In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and …

On The Chromatic Number Of The Ao(2, K , K-1) Graphs., Navya Arora

Electronic Theses and Dissertations

The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs.

We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k …

Trees With Unique Minimum Locating-Dominating Sets., Stephen M. Lane

Electronic Theses and Dissertations

A set S of vertices in a graph G = (V, E) is a locating-dominating set if S is a dominating set of G, and every pair of distinct vertices {u, v} in V - S is located with respect to S, that is, if the set of neighbors of u that are in S is not equal to the set of neighbors of v that are in S. We give a construction of trees that have unique minimum locating-dominating sets.

The Linear Complexity Of A Graph, David L. Neel, Michael E. Orrison Jr.

All HMC Faculty Publications and Research

The linear complexity of a matrix is a measure of the number of additions, subtractions, and scalar multiplications required to multiply that matrix and an arbitrary vector. In this paper, we define the linear complexity of a graph to be the linear complexity of any one of its associated adjacency matrices. We then compute or give upper bounds for the linear complexity of several classes of graphs.

Combinatorial Interpretations Of Spanning Tree Identities, Arthur T. Benjamin, Carl R. Yerger

All HMC Faculty Publications and Research

We present a combinatorial proof that the wheel graph Wn has L2n − 2 spanning trees, where Ln is the nth Lucas number, and that the number of spanning trees of a related graph is a Fibonacci number. Our proofs avoid the use of induction, determinants, or the matrix tree theorem.

Freeness Of Hopf Algebras, Christopher David Walker

Theses Digitization Project

The Nichols-Zoeller freeness theorem states that a finite dimensional Hopf algebra is free as a module over any subHopfalgebra. We will prove this theorem, as well as the first significant generalization of this theorem, which was proven three years later. This generalization says that if the Hopf algebra is infinite dimensional, then the Hopf algebra is still free if the subHopfalgebra is finite dimensional and semisimple . We will also look at several other significant generalizations that have since been proven.

The Linking Probability Of Deep Spider-Web Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

We consider crossbar switching networks with base b (that is, constructed from b x b crossbar switches), scale k (that is, with b^k inputs, b^k outputs, and b^k links between each consecutive pair of stages), and depth l (that is, with l stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least k stages. We assume that each vertex is independently idle with probability q, the vacancy probability. We assume that b ≥ 2 and the vacancy probability q are fixed, and that k …

Fuzzy Interval Matrices, Neutrosophic Interval Matrices And Their Applications, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

The new concept of fuzzy interval matrices has been introduced in this book for the first time. The authors have not only introduced the notion of fuzzy interval matrices, interval neutrosophic matrices and fuzzy neutrosophic interval matrices but have also demonstrated some of its applications when the data under study is an unsupervised one and when several experts analyze the problem. Further, the authors have introduced in this book multiexpert models using these three new types of interval matrices. The new multi expert models dealt in this book are FCIMs, FRIMs, FCInMs, FRInMs, IBAMs, IBBAMs, nIBAMs, FAIMs, FAnIMS, etc. Illustrative …

Matrix-J-Unitary Non-Commutative Rational Formal Power Series, Daniel Alpay, D. S. Kalyuzhnyi-Verbovetzkii

Mathematics, Physics, and Computer Science Faculty Articles and Research

Formal power series in N non-commuting indeterminates can be considered as a counterpart of functions of one variable holomorphic at 0, and some of their properties are described in terms of coefficients. However, really fruitful analysis begins when one considers for them evaluations on N-tuples of n × n matrices (with n = 1, 2, . . .) or operators on an infinite-dimensional separable Hilbert space. Moreover, such evaluations appear in control, optimization and stabilization problems of modern system engineering.

In this paper, a theory of realization and minimal factorization of rational matrix-valued functions which are J-unitary on the imaginary …

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

Mathematics and Statistics Faculty Publications and Presentations

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 …

Chord Diagrams And Gauss Codes For Graphs, Thomas Fleming, Blake Mellor

Mathematics, Statistics and Data Science Faculty Works

Chord diagrams on circles and their intersection graphs (also known as circle graphs) have been intensively studied, and have many applications to the study of knots and knot invariants, among others. However, chord diagrams on more general graphs have not been studied, and are potentially equally valuable in the study of spatial graphs. We will define chord diagrams for planar embeddings of planar graphs and their intersection graphs, and prove some basic results. Then, as an application, we will introduce Gauss codes for immersions of graphs in the plane and give algorithms to determine whether a particular crossing sequence is …

Tree Diagrams For String Links, Blake Mellor

Mathematics, Statistics and Data Science Faculty Works

In previous work, the author defined the intersection graph of a chord diagram associated with string links (as in the theory of finite type invariants). In this paper, we classify the trees which can be obtained as intersection graphs of string link diagrams.