Discrete Mathematics and Combinatorics Commons^™

Interval Valued Neutrosophic Shortest Path Problem By A* Algorithm, Florentin Smarandache, S. Khrisna Prabha, Said Broumi

Branch Mathematics and Statistics Faculty and Staff Publications

Many researchers have been proposing various algorithms to unravel different types of fuzzy shortest path problems. There are many algorithms like Dijkstra’s, Bellman-Ford,Floyd-Warshall and kruskal’s etc are existing for solving the shortest path problems. In this work a shortest path problem with interval valued neutrosophic numbers is investigated using the proposed algorithm. A* algorithm is extensively applied in pathfinding and graph traversal.Unlike the other algorithms mentioned above, A* algorithm entails heuristic function to uncover the cost of path that traverses through the particular state. In the structured work A* algorithm is applied to unravel the length of the shortest path …

On Eigenvalue Bounds For The Finite-State Birth-Death Process Intensity Matrix, R.R.P Tan, K Ikeda, Len Patrick Dominic M. Garces

Mathematics Faculty Publications

The paper sets forth a novel eigenvalue interlacing property across the finite-state birth-death process intensity matrix and two clearly identified submatrices as an extension of Cauchy’s interlace theorem for Hermitian matrix eigenvalues. A supplemental proof involving an examination of probabilities acquired from specific movements across states and a derivation of a form for the eigenpolynomial of the matrix through convolution and Laplace transform is then presented towards uncovering a similar characteristic for the general Markov chain transition rate matrix. Consequently, the proposition generates bounds for each eigenvalue of the original matrix, easing numerical computation. To conclude, the applicability of the …

On The Ranks Of String C-Group Representations For Symplectic And Orthogonal Groups, Peter A. Brooksbank

Faculty Journal Articles

We determine the ranks of string C-group representations of 4-dimensional projective symplectic groups over a finite field, and comment on those of higher-dimensional symplectic and orthogonal groups.

Orthogonal Groups In Characteristic 2 Acting On Polytopes Of High Rank, Peter A. Brooksbank, Dimitri Leemans, John T. Ferrara

Faculty Journal Articles

No abstract provided.

Maximality And Applications Of Subword-Closed Languages, Rhys Davis Jones

UNF Graduate Theses and Dissertations

Characterizing languages D that are maximal with the property that D^* ⊆ S^⊗ is an important problem in formal language theory with applications to coding theory and DNA codewords. Given a finite set of words of a fixed length S, the constraint, we consider its subword closure, S^⊗, the set of words whose subwords of that fixed length are all in the constraint. We investigate these maximal languages and present characterizations for them. These characterizations use strongly connected components of deterministic finite automata and lead to polynomial time algorithms for generating such languages. We prove that …

A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler

Senior Independent Study Theses

Santorini is a two player combinatorial board game. Santorini bears resemblance to the graph theory game of Geography, a game of moving and deleting vertices on a graph. We explore Santorini with game theory, complexity theory, and artificial intelligence. We present David Lichtenstein’s proof that Geography is PSPACE-hard and adapt the proof for generalized forms of Santorini. Last, we discuss the development of an AI built for a software implementation of Santorini and present a number of improvements to that AI.

Cycle Double Covers And Integer Flows, Zhang Zhang

Graduate Theses, Dissertations, and Problem Reports (ETD)

My research focuses on two famous problems in graph theory, namely the cycle double cover conjecture and the integer flows conjectures. This kind of problem is undoubtedly one of the major catalysts in the tremendous development of graph theory. It was observed by Tutte that the Four color problem can be formulated in terms of integer flows, as well as cycle covers. Since then, the topics of integer flows and cycle covers have always been in the main line of graph theory research. This dissertation provides several partial results on these two classes of problems.

Weighted Modulo Orientations Of Graphs, Jianbing Liu

Graduate Theses, Dissertations, and Problem Reports (ETD)

This dissertation focuses on the subject of nowhere-zero flow problems on graphs. Tutte's 5-Flow Conjecture (1954) states that every bridgeless graph admits a nowhere-zero 5-flow, and Tutte's 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4k-edge-connected graph admits a modulo (2k+1)-orientation, that is, an orientation such that the indegree is congruent to outdegree modulo (2k+1) at every vertex. Note that the k=1 case of Circular Flow Conjecture coincides with the 3-Flow Conjecture, and the case of k=2 implies the 5-Flow Conjecture. This work is devoted …

Circuits And Cycles In Graphs And Matroids, Yang Wu

Graduate Theses, Dissertations, and Problem Reports (ETD)

This dissertation mainly focuses on characterizing cycles and circuits in graphs, line graphs and matroids. We obtain the following advances.

1. Results in graphs and line graphs. For a connected graph G not isomorphic to a path, a cycle or a K1,3, let pc(G) denote the smallest integer n such that the nth iterated line graph Ln(G) is panconnected. A path P is a divalent path of G if the internal vertices of P are of degree 2 in G. If every edge of P is a cut edge of G, then P is a bridge divalent path of G; …