Self-Assembly Of Dna Graphs And Postman Tours, 2018 University of North Florida

#### Self-Assembly Of Dna Graphs And Postman Tours, Katie Bakewell

*UNF Graduate Theses and Dissertations*

DNA graph structures can self-assemble from branched junction molecules to yield solutions to computational problems. Self-assembly of graphs have previously been shown to give polynomial time solutions to hard computational problems such as 3-SAT and k-colorability problems. Jonoska et al. have proposed studying self-assembly of graphs topologically, considering the boundary components of their thickened graphs, which allows for reading the solutions to computational problems through reporter strands. We discuss weighting algorithms and consider applications of self-assembly of graphs and the boundary components of their thickened graphs to problems involving minimal weight Eulerian walks such as the Chinese Postman Problem and ...

Zero Forcing And Maximum Nullity For Hypergraphs, 2018 Iowa State University and American Institute of Mathematics

#### Zero Forcing And Maximum Nullity For Hypergraphs, Leslie Hogben

*Mathematics Publications*

The concept of zero forcing is extended from graphs to uniform hypergraphs in analogy with the way zero forcing was defined as an upper bound for the maximum nullity of the family of symmetric matrices whose nonzero pattern of entries is described by a given graph: A family of symmetric hypermatrices is associated with a uniform hypergraph and zeros are forced in a null vector. The value of the hypergraph zero forcing number and maximum nullity are determined for various families of uniform hypergraphs and the effects of several graph operations on the hypergraph zero forcing number are determined. The ...

Graphs That Are Cospectral For The Distance Laplacian, 2018 Rice University

#### Graphs That Are Cospectral For The Distance Laplacian, Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, Mark Yarrow

*Mathematics Publications*

The distance matrix D(G) of a graph G is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is D^{L}(G)=T(G)−D(G), where T(G) is the diagonal matrix of row sums of D(G). We establish several general methods for producing DL-cospectral graphs that can be used to construct infinite families. We provide examples showing that various properties are not preserved by D^{L}-cospectrality, including examples of D^{L}-cospectral strongly regular and circulant graphs. We establish that the absolute values of coefficients of the distance Laplacian characteristic polynomial ...

Rigid Linkages And Partial Zero Forcing, 2018 Texas State University - San Marcos

#### Rigid Linkages And Partial Zero Forcing, Daniela Ferrero, Mary Flagg, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Seth A. Meyer, Shahla Nasserasr, Bryan Shader

*Mathematics Publications*

Connections between vital linkages and zero forcing are established. Specifically, the notion of a rigid linkage is introduced as a special kind of unique linkage and it is shown that spanning forcing paths of a zero forcing process form a spanning rigid linkage and thus a vital linkage. A related generalization of zero forcing that produces a rigid linkage via a coloring process is developed. One of the motivations for introducing zero forcing is to provide an upper bound on the maximum multiplicity of an eigenvalue among the real symmetric matrices described by a graph. Rigid linkages and a related ...

Spn Graphs And Rank-1 Cp-Completable Graphs, 2018 Iowa State University

#### Spn Graphs And Rank-1 Cp-Completable Graphs, Leslie Hogben, Naomi Shaked-Monderer

*Mathematics Publications*

A simple graph G is an SPN graph if every copositive matrix having graph G is the sum of a positive semidefinite and nonnegative matrix. SPN graphs were introduced in [Shaked-Monderer, SPN graphs: When copositive = SPN, *Linear Algebra Appl.*, 509(15):82-113, 2016], where it was conjectured that the complete subdivision graph of K4 is an SPN graph. We disprove this conjecture, which in conjunction with results in the Shaked-Monderer paper show that a subdivision of K4 is a SPN graph if and only if at most one edge is subdivided. We conjecture that a graph is an SPN graph ...

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.

On The Strong Chromatic Index Of Sparse Graphs, 2018 Westfield State University

#### On The Strong Chromatic Index Of Sparse Graphs, Philip Deorsey, Michael Ferrara, Nathan Graber, Stephen G. Hartke, Luke L. Nelsen, Eric Sullivan, Sogol Jahanbekam, Bernard Lidicky, Derrick Stolee, Jennifer White

*Mathematics Publications*

The strong chromatic index of a graph G, denoted χ′s(G), is the least number of colors needed to edge-color G so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted χ′s,ℓ(G), is the least integer k such that if arbitrary lists of size k are assigned to each edge then G can be edge-colored from those lists where edges at distance at most two receive distinct colors.

We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if G is a subcubic planar graph with ...

3-Maps And Their Generalizations, 2018 Virginia Commonwealth University

#### 3-Maps And Their Generalizations, Kevin J. Mccall

*Theses and Dissertations*

A 3-map is a 3-region colorable map. They have been studied by Craft and White in their paper 3-maps. This thesis introduces topological graph theory and then investigates 3-maps in detail, including examples, special types of 3-maps, the use of 3-maps to find the genus of special graphs, and a generalization known as n-maps.

On Saturation Numbers Of Ramsey-Minimal Graphs, 2018 University of Central Florida

#### On Saturation Numbers Of Ramsey-Minimal Graphs, Hunter M. Davenport

*Honors Undergraduate Theses*

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs *H1,...,Hk* and a graph *G*, we write *G* "arrows" *(H _{1},...,H_{k})* if every

*k*-edge-coloring of

*G*contains a monochromatic copy of

*H*in color

_{i}*i*for some

*i=1,2,...,k.*If

*c*is a

*(red, blue)*-edge-coloring of

*G*, we say

*c*is a bad coloring if

*G*contains no red

*K*or ...

_{3}Sparse Trees With A Given Degree Sequence, 2018 Georgia Southern University

#### Sparse Trees With A Given Degree Sequence, Ao Shen

*Electronic Theses and Dissertations*

In this thesis, we consider the properties of sparse trees and summarized a certain class of trees under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph theory. Steiner k Wiener index can be regarded as the generalization of Wiener index, when k = 2, Steiner Wiener index is the same as Wiener index. Steiner k Wiener index of a tree T is the ...

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 ...

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 ...

Upper Bounds On Q-Spectral Radius Of Book-Free And/Or $K_{S,T}$-Free Graphs, 2017 Northwestern Polytechnical University

#### Upper Bounds On Q-Spectral Radius Of Book-Free And/Or $K_{S,T}$-Free Graphs, Qi Kong, Ligong Wang

*Electronic Journal of Linear Algebra*

In this paper, we prove two results about the signless Laplacian spectral radius $q(G)$ of a graph $G$ of order $n$ with maximum degree $\Delta$. Let $B_{n}=K_{2}+\overline{K_{n}}$ denote a book, i.e., the graph $B_{n}$ consists of $n$ triangles sharing an edge. The results are the following: (1) Let $1< k\leq l< \Delta < n$ and $G$ be a connected \{$B_{k+1},K_{2,l+1}$\}-free graph of order $n$ with maximum degree $\Delta$. Then $$\displaystyle q(G)\leq \frac{1}{4}[3\Delta+k-2l+1+\sqrt{(3\Delta+k-2l+1)^{2}+16l(\Delta+n-1)}$$ with equality if and only if $G$ is a strongly regular graph with parameters ($\Delta$, $k$, $l$). (2) Let $s\geq t\geq 3$, and let $G$ be a connected $K_{s,t}$-free graph of order $n$ $(n\geq s+t)$. Then $$q(G)\leq n+(s-t+1)^{1/t}n^{1-1/t}+(t-1)(n-1)^{1-3/t}+t-3.$$

On The Distance Signless Laplacian Spectral Radius Of Graphs And Digraphs, 2017 Xinjiang University,Urumqi

#### On The Distance Signless Laplacian Spectral Radius Of Graphs And Digraphs, Dan Li, Guoping Wang, Jixiang Meng

*Electronic Journal of Linear Algebra*

Let \eta(G) denote the distance signless Laplacian spectral radius of a connected graph G. In this paper,bounds for the distance signless Laplacian spectral radius of connected graphs are given, and the extremal graph with the minimal distance signless Laplacian spectral radius among the graphs with given vertex connectivity and minimum degree is determined. Furthermore, the digraph that minimizes the distance signless Laplacian spectral radius with given vertex connectivity is characterized.

Characterizations Of Some Classes Of Graphs That Are Nearly Series-Parallel, 2017 Louisiana State University and Agricultural and Mechanical College

#### Characterizations Of Some Classes Of Graphs That Are Nearly Series-Parallel, Victoria Fontaine

*LSU Doctoral Dissertations*

A series-parallel graph can be built from a single-edge graph by a sequence of series and parallel extensions. The class of such graphs coincides with the class of graphs that do not have the complete graph K_{4} as a minor. This dissertation considers a class M_{1} of graphs that are close to being series-parallel. In particular, every member of the class has the property that one can obtain a series-parallel graph by adding a new edge and contracting it out, or by splitting a vertex into two vertices whose neighbor sets partition the neighbor set of the original ...

An Exploration Of The Chromatic Polynomial, 2017 Boise State University

#### An Exploration Of The Chromatic Polynomial, Amanda Aydelotte

*Mathematics Undergraduate Theses*

In 1912, George Birkhoff was studying the Four Color Problem, and in doing so introduced the concept of the chromatic polynomial. While this did not end up directly contributing to proving that every map could be colored with four colors such that no region shares a border with another region of the same color, the chromatic polynomial has been found to have some very interesting properties. In this paper, it will be our goal to examine some of these properties and use them to determine information about their corresponding graphs.

Optimal Layout For A Component Grid, 2017 California Polytechnic State University, San Luis Obispo

#### Optimal Layout For A Component Grid, Michael W. Ebert

*Computer Science and Software Engineering*

Several puzzle games include a specific type of optimization problem: given components that produce and consume different resources and a grid of squares, find the optimal way to place the components to maximize output. I developed a method to evaluate potential solutions quickly and automated the solving of the problem using a genetic algorithm.

Classification Of Minimal Separating Sets In Low Genus Surfaces, 2017 Portland State University

#### Classification Of Minimal Separating Sets In Low Genus Surfaces, J. J. P. Veerman, William Maxwell, Victor Rielly, Austin K. Williams

*Mathematics and Statistics Faculty Publications and Presentations*

Consider a surface *S* and let *M* ⊂ *S*. If *S* \ *M* is not connected, then we say *M* separates *S*, and we refer to *M* as a separating set of *S*. If *M* separates *S*, and no proper subset of *M* separates *S*, then we say *M* is a minimal separating set of *S*. In this paper we use computational methods of combinatorial topology to classify the minimal separating sets of the orientable surfaces of genus *g* = 2 and *g* = 3. The classification for genus 0 and 1 was done in earlier work, using methods of algebraic topology.