MS, Kent State University, 2014, College of Arts and Sciences / Department of Computer Science

Graph database has attracted increasing attention from both of the database and data mining/machine learning communities. Enormous kinds of data with complex and dynamic relationships can be efficiently expressed by graph structure. Certain techniques such as scoring, shortest path and clustering can provide information and services by leveraging those data. They are widely used in areas like Web graph mining (Google), social network analysis (Facebook), User/Product recommendation (Netflix/Amazon), chemical and biological analysis, etc. Graph databases provide a fast and efficient way to store, access and analysis those kinds of data than any other database system. This thesis will go over the graph data and its representations, then categorize some of the most commonly used graph databases by their storage behavior. Then we will introduce some of the state-of-the-art techniques that enpower the graph database internally. After the introduction, we will have the study on how to access the graph database through query languages or APIs, and compare them through different aspects. Another contribution of this work is to compare the performance to process different kinds of data between the persistent graph databases. Not only the performance of batch loading process has been compared, we also have the stress test on single transactional insertion, query, and the in-memory graph algorithm comparison. At last we have some recommendations of using the databases based on the experiment result.

Committee: Ruoming Jin (Advisor) Subjects: Computer Engineering; Computer Science

Doctor of Philosophy, The Ohio State University, 2009, Mathematics

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. Up until now, the only examples of 2-arc transitive polygonal graphs with arbitrarily large valency had girth no larger than seven, and the 2-arc transitive polygonal graph with largest girth had valency five and girth twenty-three (in fact, even with no restrictions on the automorphism group, there were no examples of polygonal graphs with odd girth greater than twenty-three). This thesis provides a construction of an infinite family of polygonal graphs of arbitrary girth m with 2-arc transitive automorphism groups, showing that there are 2-arc transitive polygonal graphs of arbitrarily large valency for each girth m. Furthermore, this thesis also provides a construction that, given a polygonal graph of valency r and girth m, produces a polygonal graph of valency r and girth 3m, and that the graphs constructed via this method will be 2-arc transitive if the original graph was 2-arc transitive. Finally, this thesis provides a construction of a new infinite family of near-polygonal graphs of valency 10 and a method for determining which graphs can have a given girth, which yields a few new examples of polygonal graphs.

Committee: Akos Seress PhD (Advisor); Boris Pittel PhD (Committee Member); Neil Robertson PhD (Committee Member) Subjects: Mathematics

PHD, Kent State University, 2024, College of Arts and Sciences / Department of Mathematical Sciences

The commuting graph of a group is a graph whose vertices are the noncentral elements of the group, and two vertices are connected in the commuting graph if the elements commute. We first investigate the commuting graph of finite, solvable A-groups, groups whose Sylow subgroups are abelian. We determine when the commuting graph of a solvable A-group will be connected and prove that, when connected, the diameter of the commuting graph will be at most 6. Next, we briefly turn our attention to commuting graphs of p-groups, where p is a prime. We build off work that established there was no universal upper bound on the diameter of the commuting graph by constructing a family of p-groups whose commuting graphs have increasing diameters. Lastly, we define the cyclic graph of a group to be the graph whose vertices are the nontrivial elements of a group, and two vertices are connected in the cyclic graph if the elements generate a cyclic subgroup. We investigate the cyclic graph of a finite, solvable A-group and establish an upper bound for the diameter. More specifically, if Z(Gi), where Gi is the i-th term in the derived series, we establish that when the deleted enhanced power graph is connected, it will have diameter at most 6+4i. For A-groups of derived length 2, we prove an even stronger bound of 8 for the diameter.

Committee: Mark Lewis (Advisor); Stephen Gagola Jr. (Committee Member); Hamza Balci (Committee Member); Joanne Caniglia (Committee Member); Donald White (Committee Member) Subjects: Mathematics

MS, University of Cincinnati, 2023, Engineering and Applied Science: Computer Engineering

Due to the limitations of currently available benchmarks, evaluating applications in the field of hardware security poses significant difficulties. The small size, lack of scalability, and rigidity of these benchmarks hinder comprehensive assessments. This thesis seeks to resolve these limitations by demonstrating the effective adaptation of attributed graph transformation systems for the automated generation of synthetic benchmark circuits. These circuits are designed to satisfy a number of structural constraint specifications. Using existing benchmarks, this study also emphasizes the adaptability and scalability of the proposed methodology. By extracting and utilizing frequently occurring subcircuit patterns from these benchmarks, the generated circuits can encapsulate the essence of actual designs. This thesis provides a comprehensive description of its methodology. The methodology is applied to exisiting benchmarks and real-life designs to extract subcircuit patterns and generate synthetic benchmarks. To demonstrate the usefulness of the generated circuits, the thesis concentrates on their application in hardware security, particularly trojan insertion and detection. The experimental evaluation demonstrates the effectiveness of the generated circuits in detecting and mitigating trojans. This thesis contributes to the field of hardware security by overcoming the limitations of current benchmarks and providing a systematic approach for generating synthetic benchmark circuits. The adaptability and scalability of the proposed methodology opens up new areas for comprehensive evaluations and enables researchers to investigate novel solutions in this vital domain.

Committee: Ranganadha Vemuri Ph.D. (Committee Chair); Wen-Ben Jone Ph.D. (Committee Member); John Emmert Ph.D. (Committee Member) Subjects: Computer Engineering

Master of Arts (MA), Bowling Green State University, 2020, Mathematics/Mathematics (Pure)

Graph theory is a branch of mathematics that uses graphs as a mathematical structure to model relations between objects. Graphs can be categorized in a wide variety of graph families. One important instrument to classify graphs is the chromatic polynomial. This was introduced by Birkhoff in 1912 and allowed to further study and develop several graph related problems. In this thesis, we study some problems that can be approached using the chromatic polynomial. In the first chapter, we introduce general definitions and examples of graphs. In the second chapter, we talk about graph colorings, the greedy algorithm, and give a short description for the four color problem. In the third chapter, we introduce the chromatic polynomial, study its property, and give some examples of computations. All of these are classical results. In chapter 4, we introduce colorings of graphs with split vertices, and give an application to the scheduling problem. Also, we show how the chromatic polynomial can be used in that setting. This is our ``semi-original" contribution. Finally, in the last chapter, we talk about distance two colorings for graphs, and give examples on how this applies to coloring maps.

Committee: Mihai Staic Dr. (Advisor); Juan Bes Dr. (Committee Member); Kimberly Rogers Dr. (Committee Member) Subjects: Mathematics

Doctor of Philosophy, The Ohio State University, 2019, Computer Science and Engineering

Taxonomy graphs that capture hyponymy or meronymy relationships through directed edges are expected to be acyclic. However, in practice, they may have thousands of cycles, as they are often created in a crowd-sourced way. Since these cycles represent logical fallacies, they need to be removed for many web applications. In this thesis, we first address the problem of breaking cycles while preserving the logical structure (hierarchy) of a directed graph as much as possible. Existing approaches for this problem either need manual intervention or use heuristics that can critically alter the taxonomy structure. In contrast, our approach infers graph hierarchy using a range of features, including a Bayesian skill rating system and a social agony metric. We also devise several strategies to leverage the inferred hierarchy for removing a small subset of edges to make the graph acyclic. We then apply our breaking cycles technique to address the problem of Question Difficulty and Expertise Estimation (QDEE) in Community Question Answer (CQA) sites such as Yahoo! Answers and Stack Overflow. Our framework QDEE tackles a fundamental challenge in crowdsourcing: how to appropriately route and assign questions to users with suitable expertise. This problem domain has been the subject of much research and includes both language-agnostic as well as language conscious solutions. We bring to bear a key language-agnostic insight: that users gain expertise and therefore tend to ask as well as answer more difficult questions over time. We use this insight within the popular competition (directed) graph model to estimate question difficulty and user expertise by identifying key hierarchical structure within the said model. Difficulty levels of newly posted questions (the cold-start problem) are estimated by using our QDEE framework and additional textual features. We also propose a model to route newly posted questions to appropriate users based on the difficulty level of the question (open full item for complete abstract)

Committee: Srinivasan Parthasarathy (Advisor); Huan Sun (Committee Member); Eric Fosler-Lussier (Committee Member); Darren Drewry (Committee Member) Subjects: Computer Engineering; Computer Science

BA, Oberlin College, 2017, Mathematics

We study a novel model of random graph which exhibits the structural characteristics of the Watts- Strogatz small-world network. The small-world network is characterized by a high level of local clustering while also having a relatively small graph diameter. The same behavior that makes the Watts-Strogatz model behave like this also makes it difficult to analyze. Our model addresses this issue, closely mimicking the same structure experimentally while following a constructive process that makes it easier to analyze mathematically. We present a bound on the average shortest path length in our new model, which we approach by looking at the two key geometric components.

Committee: Elizabeth L. Wilmer (Advisor) Subjects: Mathematics

PhD, University of Cincinnati, 2017, Engineering and Applied Science: Computer Science and Engineering

Graph vertex and edge deletion algorithms are normally studied separately. We develop a framework to link them by transferring any existing vertex deletion algorithms to a set of new edge deletion algorithms. It is done by creating new measure for each edge in the view its endpoints, vertices. Each vertex measures its incident edges in its neighborhood graph by using a chosen vertex deletion algorithm. If a vertex is deleted in the neighborhood graph, the edge between the vertex and the host vertex is marked removable. At the end, each edge is marked twice for its removability by its two endpoints. An edge measure function combines those two removability marks and creates a new measure for each edge. A new edge deletion algorithm is created by deleting edges from the original graph basing on the newly generated edge measures. We extend above concept and operations recursively into neighborhood graphs. It makes the framework a recursive process. We further study a series of stopping criteria for the recursion process. Eventually, the framework is expressed as a recursive algorithm with parameters of edge measure function and stopping criteria. By changing those parameters, the framework can transfer a vertex deletion algorithm to multiple edge deletion algorithms. This creates the flexibility for different research purposes. As examples, we apply the framework to a few vertex deletion algorithms and generate a few sets of edge deletion algorithms. Some resulting edge deletion algorithms prove to be very efficient community discovery algorithms, especially, with the vertex deletion algorithm that is proposed by this research. We call the algorithm Follow the Crowd. We thoroughly study the performance of its generated edge deletion algorithms as community discovery algorithms.

Committee: Yizong Cheng Ph.D. (Committee Chair); Fred Annexstein Ph.D. (Committee Member); Chia Han Ph.D. (Committee Member); Wen-Ben Jone Ph.D. (Committee Member); Anca Ralescu Ph.D. (Committee Member) Subjects: Computer Science

Master of Science, Miami University, 2015, Mathematics

There have been many generalizations of Dirac's Theorem to more complex structures within graphs. I will present a proof that any standard 2-colored multigraph with minimum semi degree at least (1/2+ε)n is Hamiltonian Connected through paths of any color pattern. I will also present how this proof can be generalized to a much stronger condition that will relate to many previous results in this area. The proof will involve the idea of structures called Sorters and Pipelines and will follow closely the ideas within a proof by Haggkvist and Thomassen for arbitrarily oriented cycles in oriented graphs.

Committee: Louis DiBiasio (Advisor); Daniel Pritkin (Committee Member); Tao Jiang (Committee Member) Subjects: Mathematics

Master of Science in Electrical Engineering, University of Toledo, 2013, College of Engineering

Processing large graph datasets represents an increasingly important area in computing research and applications. The size of many graph datasets has increased well beyond the processing capacity of a single computing node, thereby necessitating distributed approaches. As these datasets are processed over a distributed system of nodes, this leads to an inter-node communication cost problem (also known as inter-partition communication), negatively affecting the system performance. This research proposes new graph partitioning algorithms to minimize the inter-node communication by achieving a sufficiently balanced partition. Initially, an intuitive graph partitioning algorithm using Random Selection method coupled with Breadth First Search is developed for reducing inter-node communication by achieving a sufficiently balanced partition. Second, another graph partitioning algorithm is developed using Particle Swarm Optimization with Breadth First Search to reduce inter-node communication further. Simulation results demonstrate that the inter-node communication using PSO with BFS gives better results (reduction of approximately 6% to 10% more) compared to the RS method with BFS. However, both the algorithms minimize the inter-node communication efficiently in order to improve the performance of a distributed system.

Committee: Robert Green (Committee Chair); Vijay Devabhaktuni (Committee Co-Chair); William Acosta (Committee Member); Mansoor Alam (Committee Member) Subjects: Computer Engineering; Computer Science

Master of Science, The Ohio State University, 2009, Computer Science and Engineering

Graphs of various kinds are important in modern culture. Humans can understand and draw inferences from large amounts of data represented in a graphical format more easily than the same data represented in textual form. Even though graphs seem to be very effective, a badly designed graph may affect the accuracy or speed in comprehending information represented in a graph. Graph designers, instead of just depending on just their intuitions about what makes a good graph, need guidance based on a set of scientific principles. The relevant science involves understanding the various cognitive processes involved in graph comprehension. This has led many scientists to study graph comprehension as a cognitive task. However, most of the models proposed by the various scientists are qualitative descriptions of aspects of the graph comprehension process. Though these models are consistent with a computational approach, they were neither expressed as computer programs, nor were they sufficiently detailed to support implementation as a computer program. Computational models are more useful than descriptive models, since they can be run on a computer to predict behavioral details such as time taken to perform tasks under varying assumptions. Our goal in this work is to build a computational cognitive model for graph comprehension that unifies the multiplicity of models proposed by the various researchers in our survey. Instead of multiple models, we will have one model that exhibits the multiplicity of identified phenomena under appropriate conditions. We should be able to explain how background knowledge, the attention mechanism, visual activities such as scanning and anchoring, and mental imagery – all features of a general architecture – are deployed opportunistically in the specific graph comprehension task in response to the specifics of the task and agent's situation. The thesis describes a set of models for a range of graph comprehension tasks that together provide the (open full item for complete abstract)

Committee: Balakrishnan Chandrasekaran (Advisor); John Josephson (Committee Member) Subjects: Artificial Intelligence

Doctor of Philosophy, Case Western Reserve University, 2011, EECS - Computer and Information Sciences

In recent years, graph pattern matching, approximate graph matching and dynamic subgraph indexing have become important graph analysis tools due to the emergence of many new applications such as computational biology and social networks analysis. In this work we investigate these three related problems. For the first problem, in previous existing models, each edge in the query pattern represents the same relationship, e.g., the two endpoint vertices have to be connected or the distance between them should be within a certain uniform threshold. However, real world applications may require edges representing different relationships or distances. Therefore, we introduce the flexible pattern matching model where a range [mine; maxe] is associated with an edge e in the query pattern, which means that the minimum distance between the matched endpoints of e is in the range of [mine; maxe]. A novel pattern matching algorithm is devised, which consists of several innovations including preprocessing the query pattern, two types of indices, and a top-k matches generation scheme. For the second problem, we study the problem of finding approximate matches of a query graph in a large database graph with (possible) missing edges. The SAPPER method is proposed, utilizing the hybrid neighborhood unit structures in the index. SAPPER also takes advantage of pre-generated random spanning trees and a carefully designed graph enumeration order. For the third problem, to the best of our knowledge, most subgraph indexing focuses on the static database graphs. However, in real applications, database graphs may change over time. Thus, we propose an indexing structure, BR-index, for large dynamic graphs. The large database graph is partitioned into a set of overlapping index regions. Features (small subgraphs) are extracted from these regions and used to index them. The updates to G can be localized to a small number of these regions. To further improve the efficiency in updates and query pro (open full item for complete abstract)

Committee: Jiong Yang (Advisor); Gultekin Ozsoyoglu (Committee Member); Wojbor Woyczynski (Committee Member); Soumya Ray (Committee Member) Subjects: Computer Science

Doctor of Philosophy (PhD), Wright State University, 2024, Computer Science and Engineering PhD

The digital landscape is ever-evolving. In recent years the amount of bot traffic, traffic generated by autonomous applications over the internet has increased significantly. Many bots perform useful and needed functions, however, malicious bots are known sources of both common and emerging security threats. Denial-of-Services (DoS), information theft, and credential stuffing have all been conducted by malicious software running on unknowingly infected machines. The dichotomy of useful bots operating in the same networks as malicious bots combined with novel bot attacks and an ever-increasing number of personal devices connecting to the Internet drives the need for continued advancement of malicious bot detection techniques. Graph Neural Networks, a class of neural networks that are enriched with structural and relationship information, have emerged as a possible advancement on existing bot detection methods. Unfortunately, GNNs have known limitations pertaining to extreme data imbalances and heterophily, two common attributes of bot datasets. Moreover, a lack of accurate and completely labeled bot data for training purposes further limits GNN performance. This dissertation outlines multiple novel approaches for addressing data imbalances, heterophily, and scarce data enabling the application of GNNs to malicious bot detection. First, I introduce the HOVER (Homophilic Oversampling Via Edge Removal) technique, an oversampling approach capable of mitigating heterophily in graphs and learning improved data representations. Next, I explore the utility of out-of-distribution detection (ODD) on imbalanced graphs. Two different ODD approaches are developed demonstrating the effectiveness of energy-based and isotropic ODD for bot detection. I supplement shortcomings not addressed in earlier ODD research by enhancing learning-free belief propagation schemes to boost detection performance. Finally, I present a selective graph rewiring methodology derived from the topol (open full item for complete abstract)

Committee: Lingwei Chen Ph.D. (Advisor); Michael L. Raymer Ph.D. (Committee Member); Tanvi Banerjee Ph.D. (Committee Member); Josh Ash Ph.D. (Committee Member) Subjects: Artificial Intelligence; Computer Science

Master of Science (MS), Wright State University, 2024, Computer Science

Graph Neural Networks (GNNs) have increasingly gained popularity as tools for analyzing graph data in areas like biology, knowledge-graphs, social networks, biology, and recommendation systems. However, their vulnerability to adversarial attacks - small, targeted manipulations of graph structures or node features - raises serious concerns about their reliability in real-world applications. Existing defense strategies, such as adversarial training, edge filtering, low-rank approximations, and randomization-based methods, often suffer from high computational costs, scalability issues, or reduced clean-data performance. Unlike these methods, the proposed approach integrates multi-hop relationships, applies adaptive regularization, and maintains a balance between feature-based and structural embeddings, ensuring improved performance under both clean and adversarial conditions. The learned embeddings from multi-hop relationships also result in performance improvements. Extensive experiments on benchmark datasets (Cora, Citeseer, PubMed, Texas, Wisconsin) under various attack scenario - DICE, MetaAttack, and random perturbations - are performed on the proposed method as well as baseline models (GCN, GAT, WRGCN, LinkX). The proposed model consistently outperformed baseline models on both clean data and perturbed data. By addressing key challenges in adversarial machine learning, such as dataset consistency, hyperparameter tuning, and computational efficiency, this research provides a scalable, adaptable solution for deploying GNNs in sensitive applications like fraud detection, cybersecurity, and recommendation systems.

Committee: Lingwei Chen Ph.D. (Advisor); Cogan Shimizu Ph.D. (Committee Member); Michael Raymer Ph.D. (Committee Member) Subjects: Computer Science

Master of Computing and Information Systems, Youngstown State University, 2024, Department of Computer Science and Information Systems

As graphs used as input for real-world applications become larger, training and inference workloads for Graph Neural Networks (GNNs) can quickly become infeasible under any reasonable latency requirements. Unlike traditional Deep Neural Networks (DNNs), GNNs confront various computational problems due to their large dimensions, unstructured nature, and sparsity in the input graphs. Several pruning mechanisms have been used in the past, including both irregular and structured methods, to reduce the size of GNN models while maintaining performance. The challenge is that some pruning algorithms, particularly those that are irregular or unstructured, do not help improve the computing performance on parallel architectures because the sparse and irregular connections impose limitations on the amount of parallelism in the dense matrix multiplication kernels. The structured pruning methods reduce the size of GNN models however, their adoption has been somewhat limited due to the inability of current structured model pruning techniques to leverage GPU resources to their fullest, especially with vectorized hardware. This work shows that the newly introduced structured pruning method enhances the scalability of GNNs on modern parallel architectures. The method prunes redundant connections in a structured way, optimizing GNNs for modern GPUs and improving parallelism for efficient GPU utilization. The results show that the structured pruning method achieves high sparsity and reduced computing time without sacrificing accuracy. In real-time applications where latency is critical, such as social networks and autonomous driving, these results allow for the effective deployment of GNNs.

Committee: Alina Lazar PhD (Advisor); Feng Yu PhD (Committee Member); Robert Gilliland PhD (Committee Member) Subjects: Computer Science; Information Systems

Doctor of Philosophy, The Ohio State University, 2024, Computer Science and Engineering

Graphs are widely used to model data in many applications such as chemistry, transportation, etc. Visualizing and analyzing graph data pose inherent challenges due to its non-Euclidean nature. In this dissertation, inspired by the emergence of Graph Neural Networks (GNNs), we address the challenges of graph visualization and analysis through innovative approaches. In the past decades, many graph drawing techniques have been proposed for generating aesthetically pleasing graph layouts. Several research studies have shown that a method that considers multiple aesthetic metrics simultaneously and makes sensible compromises is more likely to generate a visually pleasing graph layout [43]. However, most existing works only focus on optimizing a single aesthetic criterion. To bridge this research gap, we first propose a GNN-based deep learning framework, DeepGD, which can generate layouts by optimizing multiple aesthetics simultaneously. In order to balance the tradeoff, we propose two adaptive training strategies, which adjust the weight factor of each aesthetic dynamically during training. Nonetheless, DeepGD cannot be directly applied to optimizing nondifferentiable criteria without special accommodation, which thus constrains its flexibility in optimizing arbitrary aesthetic criteria. To solve this limitation, we propose a novel Generative Adversarial Network (GAN)-based deep learning framework for graph drawing, called SmartGD, which can optimize different quantitative aesthetic goals, regardless of their differentiability. To optimize graph layouts toward an optimization goal without the need to mathematically define aesthetic metrics, we allow SmartGD to learn from high-quality layouts generated by itself and keep challenging the self-generated layouts during training via the self-challenging mechanism. Compared to existing works focusing on optimizing different criteria, this work addresses the unique challenge of optimizing nondifferenti (open full item for complete abstract)

Committee: Han-Wei Shen (Advisor); Rephael Wenger (Committee Member); Hanqi Guo (Committee Member); Wei-Lun Chao (Committee Member) Subjects: Artificial Intelligence; Computer Science

MS, University of Cincinnati, 2024, Engineering and Applied Science: Computer Science

This thesis addresses the critical challenges of Large Language Models (LLMs) in biomedical research, focusing on reducing hallucinations and ensuring the secure use of private data. Incorrect or fabricated responses generated by LLMs can directly impact patient care and clinical outcomes. This study aims to reduce these concerns by integrating LLMs with a structured knowledge graph that combines public data from the Unified Medical Language System (UMLS) and private data from the Pediatric Cardiac Genomics Consortium (PCGC). This integration allows LLMs to answer queries using both public and sensitive private datasets without exposing individual records. Advanced techniques for graph traversal and vector embeddings fetch the most relevant context, significantly reducing the risk of hallucination and ensuring context verifiability. Our architecture leverages Neo4j for graph database management and LangChain for orchestrating LLM workflows. Neo4j's capabilities in vector indexing and full-text search enable efficient semantic searches, while LangChain facilitates the integration and management of LLMs and knowledge bases. Advanced ranking techniques such as Reciprocal Rank Fusion (RRF) and FlashRank enhance the relevance and accuracy of retrieved information. Additionally, the system uses the Ragas library to evaluate the quality of generated content and LangSmith for debugging, testing, and monitoring. Benchmarking results demonstrate that this approach significantly reduces hallucination rates compared to general-purpose LLMs like OpenAI's GPT-4 models, providing more reliable and contextually accurate outputs. Furthermore, the system addresses data privacy concerns by securely leveraging sensitive datasets, ensuring that private data is used appropriately without being exposed or used directly to train models. In summary, integrating LLMs with a fused knowledge base of public and private data through Retrieval-Augmented Generation (RAG) models rep (open full item for complete abstract)

Committee: Jaroslaw Meller Ph.D. (Committee Chair); Michal Kouril Ph.D. (Committee Member); Michael Wagner Ph.D. (Committee Member); Raj Bhatnagar Ph.D. (Committee Member) Subjects: Computer Science

Master of Science in Mathematics, Youngstown State University, 2023, Department of Mathematics and Statistics

A graph G is said to arrow a graph H if every red-blue edge coloring of G presents a monochromatic H, and is written G→H. The down-arrow Ramsey set reports all subgraphs H of a graph G for which G→H. Formally, the down-arrow Ramsey set is a graph G is ↓G:= {H⊆G: G→H }. Calculating this set by way of scientific computing is computationally prohibitive with the resources commonly available to graph theorists and other academics. Using existing research into complete graphs, the down-arrow Ramsey sets for small complete graphs (Kn for 2 ≤ n ≤ 7) can be generated quickly. For larger complete graphs (Kn for 8 ≤ n ≤ 11) specific pre-processing steps are leveraged to speed up calculations in addition to existing data sets. Presented is work on the development of a Python script to generate the down-arrow Ramsey set of a graph through efficient memory management and parallel computing methodologies. The down-arrow generator is used to report new results on complete graphs as well as complete bipartite graphs, and assorted other graphs.

Committee: Alexis Byers PhD (Advisor); Alina Lazar PhD (Committee Member); Anita O'Mellan PhD (Committee Member) Subjects: Computer Science; Mathematics

Master of Sciences, Case Western Reserve University, 2022, EECS - Computer and Information Sciences

We expand on the framework of graph matrices first introduced by Ahn et al. [1], which are a class of random matrices whose entries' dependence can be described by a small graph. While Ahn et al. assume that a univariate distribution underlies this dependence, we relax this assumption and introduce graph matrices whose input structure is derived from a multivariate probability distribution. We then show spectral norm bounds on these graph matrices as being consistent with those under the univariate setting using the trace power method. Our result expands Ahn et al's work by allowing for random matrices with more complicated dependencies between elements. We present potential applications that have such dependencies under the multivariate setting in fields such as graph theory.

Committee: Harold Connamacher (Advisor); Vincenzo Liberatore (Committee Member); Mark Meckes (Committee Member) Subjects: Computer Science; Mathematics

Master of Science (M.S.), University of Dayton, 2021, Aerospace Engineering

With more efficient computational capabilities, the use of topology optimization (TO) is becoming more common for many different types of structural design problems. Rapid prototyping and testing is often used to further validate optimized designs, but depending on a design's complexity, the structural behavior of physical models can vary significantly compared to that of their computational counterparts. For graph-based topologies such differences are caused, in part, by a need to realize finite-thickness structures from the infinitely thin geometries described by graph theory. Other differences are caused by limitations on manufacturing processes such as the need to fabricate large models from smaller components. While additive manufacturing (AM) can be more conducive for fabrication of complex topologies, its limitations are generally less understood than those for traditional subtractive manufacturing processes. Understanding and incorporating limitations on AM into a TO process in the form of added constraints would allow the algorithm to produce not only optimal designs, but also those that are feasible for AM. In this work, two specific AM constraints are characterized for Lindenmayer system (L-system) graph-based topologies of a multi-material, diamond-shaped, morphing airfoil in supersonic flow. One constraint is related to the feasible generation of thick structural members from the infinitely thin beams of graph-based topologies. To characterize the effects of geometric overlap, structural behavior of finite element models made of lower-fidelity beam elements is compared to that of finite element models made of higher-fidelity volume elements. Results indicate that at intersections where 10% or more of a member's length is overlapped, there will be significant variations in stress and effective torsional stiffness when thin members are converted to thick members. The second AM constraint characterized in this work is related to partitioning of large mo (open full item for complete abstract)

Committee: Markus Rumpfkeil (Committee Chair); Richard Beblo (Committee Member); Alexander Pankonien (Committee Member); Raymond Kolonay (Committee Member) Subjects: Aerospace Engineering; Engineering; Mechanical Engineering