Discrete Mathematics and Combinatorics Commons^™

Counting Hamiltonian Cycles In Quartic Circulant Graphs, Allison Hilliard

Seaver College Research And Scholarly Achievement Symposium

We consider the problem of counting Hamiltonian cycles in circulant graphs $C^K_n$ where $n$ is the number of vertices and $K$ is a set containing elements that correspond to the allowed edges in the circulant graphs. After sorting the cycles by a topological invariant called the winding number, we use a modified transfer matrix method to convert local data into global structures. The result is a generating function that counts the number of Hamiltonian cycles in a circulant graph with $n$ vertices. The results for $K=\{1,2\}$ and $K=\{1,3\}$ have been found by previous authors. We focus on the case where …

Counting Hamiltonian Cycles In Quartic Circulant Graphs, Allison Hilliard

Seaver College Research And Scholarly Achievement Symposium

We consider the problem of counting Hamiltonian cycles in circulant graphs $C_n^{1,k}$. Our method is to partition the set of Hamiltonian cycles according to their winding numbers. Then, we construct a weighted digraph that allows us to produce a generating function that counts the number of Hamiltonian cycles for each winding number. Summing these generating functions derives a formula for the total number of Hamiltonian cycles in a circulant graph with $n$ vertices.

Some Generalizations Of Corona Product Of Two Graphs, Aparajita Borah, Gajendra Pratap Singh

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we are seeking to conceptualize the notion of corona product of two graphs to contrive some special types of graphs. That is, here our attempt is to regenerate a familiar graph as a product graph. We are considering seven familiar graphs here to reconstruct them with the help of corona product of two graphs. Such types of families of the graphs and operations can be used to study biological pathways as well as to find the optimal order and size for the special types of graphs.

Quasisymmetric Functions Distinguishing Trees, Jean-Christophe Aval, Karimatou Djenabou, Peter R. W. Mcnamara

Faculty Journal Articles

A famous conjecture of Stanley states that his chromatic symmetric function distinguishes trees. As a quasisymmetric analogue, we conjecture that the chromatic quasisymmetric function of Shareshian and Wachs and of Ellzey distinguishes directed trees. This latter conjecture would be implied by an affirmative answer to a question of Hasebe and Tsujie about the P-partition enumerator distinguishing posets whose Hasse diagrams are trees. They proved the case of rooted trees and our results include a generalization of their result.

The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen

Theory & Applications of Graphs

The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]-complete for DAGs. Finally, we give a fixed-parameter …

Choose Your Own Adventure: An Analysis Of Interactive Gamebooks Using Graph Theory, D'Andre Adams, Daniela Beckelhymer, Alison Marr

Journal of Humanistic Mathematics

"BEWARE and WARNING! This book is different from other books. You and YOU ALONE are in charge of what happens in this story." This is the captivating introduction to every book in the interactive novel series, Choose Your Own Adventure (CYOA). Our project uses the mathematical field of graph theory to analyze forty books from the CYOA book series for ages 9-12. We first began by drawing the digraphs of each book. Then we analyzed these digraphs by collecting structural data such as longest path length (i.e. longest story length) and number of vertices with outdegree zero (i.e. number …

Polytopes Associated To Graph Laplacians, Marie Meyer

Theses and Dissertations--Mathematics

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, P_G, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, P_D.

Basic properties of both families of simplices, P_G and P …

Private Out-Domination Number Of Generalized De Bruijn Digraphs, G. Marimuthu, B. Johnson

Applications and Applied Mathematics: An International Journal (AAM)

Dominating sets are widely applied in the design and efficient use of computer networks. They can be used to decide the placement of limited resources, so that every node has access to the resource through neighbouring node. The most efficient solution is one that avoids duplication of access to the resources. This more restricted version of minimum dominating set is called an private dominating set. A vertex v in a digraph D is called a private out-neighbor of the vertex u in S (subset of V(D)) if u is the only element in the intersection of in-neighborhood set of v …

Decompositions, Packings, And Coverings Of Complete Directed Gaphs With A 3-Circuit And A Pendent Arc., Chrys Gwellem

Electronic Theses and Dissertations

In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K₃ ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings, and coverings of the complete digraph with the two 3-circuit with a pendant arc orientations.

Generating Sequences Of Clique-Symmetric Graphs Via Eulerian Digraphs, John P. Mcsorley, Thomas D. Porter

Articles and Preprints

Let {G_p1,G_p2, . . .} be an infinite sequence of graphs with G_pn having pn vertices. This sequence is called K_p-removable if G_p1 ≅ K_p, and G_pn − S ≅ G_p(n−1) for every n ≥ 2 and every vertex subset S of G_pn that induces a K_p. Each graph in such a sequence has a high degree of symmetry: every way of removing the vertices of any fixed number of disjoint K_p’s yields the same …