Discrete Mathematics and Combinatorics Commons^™

Global Supply Sets In Graphs, Christian G. Moore

Electronic Theses and Dissertations

For a graph G=(V,E), a set S⊆V is a global supply set if every vertex v∈V\S has at least one neighbor, say u, in S such that u has at least as many neighbors in S as v has in V \S. The global supply number is the minimum cardinality of a global supply set, denoted γgs (G). We introduce global supply sets and determine the global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.

Completing Partial Latin Squares With One Nonempty Row, Column, And Symbol, Jaromy Kuhl, Michael W. Schroeder

Mathematics Faculty Research

Let r,c,s ∈{1,2,…,n} and let PP be a partial latin square of order n in which each nonempty cell lies in row r, column c, or contains symbol s. We show that if n ∉ {3, 4, 5} and row r, column c, and symbol s can be completed in P, then a completion of P exists. As a consequence, this proves a conjecture made by Casselgren and Häggkvist. Furthermore, we show exactly when row r, column c, and symbol s can be completed.

The Chromatic Number Of The Square Of Subcubic Planar Graphs, Stephen Hartke, Sogol Jahanbekam, Brent Thomas

Faculty Publications

Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most 3 is 7-colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.

Two Generalizations Of The Filippov Operation, Menevse Eryuzlu

Masters Theses & Specialist Projects

The purpose of this thesis is to generalize Filippov's operation, and to get more useful results. It includes two main parts: The C-Filippov operation for the finite and countable cases and the Filippov operation with different measures. In the first chapter, we give brief information about the importance of Filippov's operation, our goal and the ideas behind our generalizations. In the second chapter, we give some sufficient background notes. In the third chapter, we introduce the Filippov operation, explain how to calculate the Filippov of a function and give some sufficient properties of it. In the fourth chapter, we introduce …

Generalized Splines On Arbitrary Graphs, Simcha Gilbert, Julianna Tymoczko, Shira Viel

Mathematics Sciences: Faculty Publications

Let G be a graph whose edges are labeled by ideals of a commutative ring. We introduce a generalized spline, which is a vertex labeling of G by elements of the ring so that the difference between the labels of any two adjacent vertices lies in the corresponding edge ideal. Generalized splines arise naturally in combinatorics (algebraic splines of Billera and others) and in algebraic topology (certain equivariant cohomology rings, described by Goresky, Kottwitz, and MacPherson, among others). The central question of this paper asks when an arbitrary edge-labeled graph has nontrivial generalized splines. The answer is “always”, and we …

Combinatorial Descriptions Of The Crystal Structure On Certain Pbw Bases (Extended Abstract), Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

Lusztig's theory of PBW bases gives a way to realize the infinity crystal for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our …

Impartial Avoidance Games For Generating Finite Groups, Bret J. Benesh, Dana C. Ernst, Nándor Sieben

Mathematics Faculty Publications

We study an impartial avoidance game introduced by Anderson and Harary. The game is played by two players who alternately select previously unselected elements of a finite group. The first player who cannot select an element without making the set of jointly-selected elements into a generating set for the group loses the game. We develop criteria on the maximal subgroups that determine the nim-numbers of these games and use our criteria to study our game for several families of groups, including nilpotent, sporadic, and symmetric groups.

Single Valued Neutrosophic Graphs, Florentin Smarandache, Said Broumi, Assia Bakali, Mohamed Talea

Branch Mathematics and Statistics Faculty and Staff Publications

The notion of single valued neutrosophic sets is a generalization of fuzzy sets, intuitionistic fuzzy sets. We apply the concept of single valued neutrosophic sets, an instance of neutrosophic sets, to graphs. We introduce certain types of single valued neutrosophic graphs (SVNG) and investigate some of their properties with proofs and examples.

A Beautiful Proof By Induction, Lars-Daniel Öhman

Journal of Humanistic Mathematics

The purpose of this note is to present an example of a proof by induction that in the opinion of the present author has great aesthetic value. The proof in question is Thomassen's proof that planar graphs are 5-choosable. I give a self-contained presentation of this result and its proof, and a personal account of why I think this proof is beautiful.

A secondary purpose is to more widely publicize this gem, and hopefully make it part of a standard set of examples for examining characteristics of proofs by induction.

Generalized Eulerian Numbers And Multiplex Juggling Sequences, Esther M. Banaian

All College Thesis Program, 2016-2019

We consider generalizations of both juggling sequences and non-attacking rook placements. We demonstrate the important connection between these objects, and also propose a generalization of the Eulerian numbers. These generalizations give rise to several interesting counting problems, which we explore.

An Exploration Of “The Enumeration Of Heterofullerenes”, Kayla Penkava

Conspectus Borealis

No abstract provided.

Graph Cohomology, Matthew Lin

HMC Senior Theses

What is the cohomology of a graph? Cohomology is a topological invariant and encodes such information as genus and euler characteristic. Graphs are combinatorial objects which may not a priori admit a natural and isomorphism invariant cohomology ring. In this project, given any finite graph G, we constructively define a cohomology ring H*(G) of G. Our method uses graph associahedra and toric varieties. Given a graph, there is a canonically associated convex polytope, called the graph associahedron, constructed from G. In turn, a convex polytope uniquely determines a toric variety. We synthesize these results, and describe the …

Line-Of-Sight Pursuit And Evasion Games On Polytopes In R^N, John Phillpot

HMC Senior Theses

We study single-pursuer, line-of-sight Pursuit and Evasion games in polytopes in $\mathbb{R}^n$. We develop winning Pursuer strategies for simple classes of polytopes (monotone prisms) in Rⁿ, using proven algorithms for polygons as inspiration and as subroutines. More generally, we show that any Pursuer-win polytope can be extended to a new Pursuer-win polytope in more dimensions. We also show that some more general classes of polytopes (monotone products) do not admit a deterministic winning Pursuer strategy. Though we provide bounds on which polytopes are Pursuer-win, these bounds are not tight. Closing the gap between those polytopes known to be …

Fibonomial Tilings And Other Up-Down Tilings, Robert Bennett

HMC Senior Theses

The Fibonomial coefficients are a generalization of the binomial coefficients with a rather nice combinatorial interpretation. While the ordinary binomial coefficients count lattice paths in a grid, the Fibonomial coefficients count the number of ways to draw a lattice path in a grid and then Fibonacci-tile the regions above and below the path in a particular way. We may forgo a literal tiling interpretation and, instead of the Fibonacci numbers, use an arbitrary function to count the number of ways to "tile" the regions of the grid delineated by the lattice path. When the function is a combinatorial sequence such …

Adinkras And Arithmetical Graphs, Madeleine Weinstein

HMC Senior Theses

Adinkras and arithmetical graphs have divergent origins. In the spirit of Feynman diagrams, adinkras encode representations of supersymmetry algebras as graphs with additional structures. Arithmetical graphs, on the other hand, arise in algebraic geometry, and give an arithmetical structure to a graph. In this thesis, we will interpret adinkras as arithmetical graphs and see what can be learned.

Our work consists of three main strands. First, we investigate arithmetical structures on the underlying graph of an adinkra in the specific case where the underlying graph is a hypercube. We classify all such arithmetical structures and compute some of the corresponding …

The Maximum Multiplicity Of An Eigenvalue Of Symmetric Matrices With A Given Graph, Keivan Hassani Monfared, Sudipta Mallik

Mathematics Faculty Research

For a graph G, M(G) denotes the maximum multiplicity occurring of an eigenvalue of a symmetric matrix whose zero-nonzero pattern is given by edges of G. We introduce two combinatorial graph parameters T^-(G) and T^+(G) that give a lower and an upper bound for M(G) respectively, and we show that these bounds are sharp.

A Bound On The Number Of Spanning Trees In Bipartite Graphs, Cheng Wai Koo

HMC Senior Theses

Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees.

Our other results are combinatorial proofs that the conjecture holds for …

On Edge-Minimization Of Vertex Minimal Graphs With Dicyclic Automorphism Group, Peter E. Huston

Undergraduate Honors Thesis Projects

We find the smallest degree of a graph with automorphism group isomorphic to the dicyclic group with 4n elements, denoted α(Dic_n). We also find the fewest edges a minimum-order graph with dicyclic automorphism group and a minimal number of vertices can have. For n not a power of 2, the value of α(Dic_n) is significantly less than the best previously known upper bound, 8n. Such an edge-minimized vertex-minimal graph is constructed and shown to have automorphism group Dic_n . That the exhibited graph is minimal is verified using a combination of techniques similar to those developed previously for Abelian groups …

Automated Conjecturing Approach For Benzenoids, David Muncy

Theses and Dissertations

Benzenoids are graphs representing the carbon structure of molecules, defined by a closed path in the hexagonal lattice. These compounds are of interest to chemists studying existing and potential carbon structures. The goal of this study is to conjecture and prove relations between graph theoretic properties among benzenoids. First, we generate conjectures on upper bounds for the domination number in benzenoids using invariant-defined functions. This work is an extension of the ideas to be presented in a forthcoming paper. Next, we generate conjectures using property-defined functions. As the title indicates, the conjectures we prove are not thought of on our …

The Automorphism Group Of The Halved Cube, Benjamin B. Mackinnon

Theses and Dissertations

An n-dimensional halved cube is a graph whose vertices are the binary strings of length n, where two vertices are adjacent if and only if they differ in exactly two positions. It can be regarded as the graph whose vertex set is one partite set of the n-dimensional hypercube, with an edge joining vertices at hamming distance two. In this thesis we compute the automorphism groups of the halved cubes by embedding them in R n and realizing the automorphism group as a subgroup of GLn(R). As an application we show that a halved cube is a circulant graph if …

Combinatorial Optimization Of Subsequence Patterns In Words, Matthew R. Just

College of Graduate Studies: Theses & Dissertations

Packing patterns in words concerns finding a word with the maximum number of a prescribed pattern. The majority of the work done thus far is on packing patterns into permutations. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently, the packing density for all but two (up to equivalence) permutation patterns up to length 4 can be obtained. In this thesis we consider the analogous question for colored patterns and permutations. By introducing the concept of colored blocks …

Polytopes Of Large Rank For Psl(4,Q), Peter A. Brooksbank, Dimitri Leemans

Faculty Journal Articles

This paper examines abstract regular polytopes whose automorphism group is the projective special linear group PSL(4,q). For q odd we show that polytopes of rank 4 exist by explicitly constructing PSL(4,q) as a string C-group of that rank. On the other hand, we show that no abstract regular polytope exists whose group of automorphisms is PSL(4,2^k).

Zeon Roots, Lisa M. Dollar, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

Zeon algebras can be thought of as commutative analogues of fermion algebras, and they can be constructed as subalgebras within Clifford algebras of appropriate signature. Their inherent combinatorial properties make them useful for applications in graph enumeration problems and evaluating functions defined on partitions. In this paper, kth roots of invertible zeon elements are considered. More specifically, conditions for existence of roots are established, numbers of existing roots are determined, and computational methods for constructing roots are developed. Recursive and closed formulas are presented, and specific low-dimensional examples are computed with Mathematica. Interestingly, Stirling numbers of the first kind appear …

Zeons, Orthozeons, And Graph Colorings, G. Stacey Staples, Tiffany Stellhorn

SIUE Faculty Research, Scholarship, and Creative Activity

No abstract provided.

The Encyclopedia Of Neutrosophic Researchers - Vol. 1, Florentin Smarandache

Branch Mathematics and Statistics Faculty and Staff Publications

This is the first volume of the Encyclopedia of Neutrosophic Researchers, edited from materials offered by the authors who responded to the editor’s invitation. The authors are listed alphabetically. The introduction contains a short history of neutrosophics, together with links to the main papers and books. Neutrosophic set, neutrosophic logic, neutrosophic probability, neutrosophic statistics, neutrosophic measure, neutrosophic precalculus, neutrosophic calculus and so on are gaining significant attention in solving many real life problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistent, and indeterminacy. In the past years the fields of neutrosophics have been extended and applied in various fields, such as: …

Strong Neutrosophic Graphs And Subgraph Topological Subspaces, Florentin Smarandache, W.B. Vasantha Kandasamy, Ilantheral K

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of strong neutrosophic graphs. They are very different from the usual graphs and neutrosophic graphs. Using these new structures special subgraph topological spaces are defined. Further special lattice graph of subgraphs of these graphs are defined and described. Several interesting properties using subgraphs of a strong neutrosophic graph are obtained. Several open conjectures are proposed. These new class of strong neutrosophic graphs will certainly find applications in NCMs, NRMs and NREs with appropriate modifications.

Semigroups On Mod Natural Neutrosophic Elements, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book the notion of semigroups under + is constructed using the Mod natural neutrosophic integers or MOD natural neutrosophic-neutrosophic numbers or mod natural neutrosophic finite complex modulo integer or MOD natural neutrosophic dual number integers or MOD natural neutrosophic special dual like number or MOD natural neutrosophic special quasi dual numbers are analysed in a systematic way. All these semigroups under + have an idempotent subsemigroup under +. This is the first time we are able to give a class of idempotent subsemigroups under + by taking only those MOD natural neutrosophic elements

Mod Relational Maps Models And Mod Natural Neutrosophic Relational Maps Models, Florentin Smarandache, K. Ilanthenral, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

Zadeh introduced the degree of membership/truth (t) in 1965 and defined the fuzzy set. Atanassov introduced the degree of non membership/falsehood (f) in 1986 and defined the intuitionistic fuzzy set. Smarandache introduced the degree of indeterminacy/neutrality (i) as independent component in 1995 (published in 1998) and defined the neutrosophic set on three components (t,i,f) = (truth, indeterminacy, falsehood). The words “neutrosophy” and “neutrosophic” were coined/invented by F. Smarandache in his 1998 book. Etymologically, “neutro-sophy” (noun) [French neutre 1), or complete information (sum of components = 1).

Mod Natural Neutrosophic Subset Semigroups, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of MOD subsets using Zn ... On these MOD subsets the operation ‘+’ is defined, S(Zn) denotes the MOD subset and {S(Zn), +} happens to be only a Smarandache semigroup.

These S-semigroups enjoy several interesting properties. The notion of MOD universal subset and MOD absorbing subsets are defined and developed. {S(Zn), x } is also a semigroup and several properties associated with them are derived. MOD natural neutrosophic subsets forms only a semigroup under ‘+’. In fact the main feature enjoyed by this structure is they have subset idempotents …

Mod Cognitive Maps Models And Mod Natural Neutrosophic Cognitive Maps Models, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

Zadeh introduced the degree of membership/truth (t) in 1965 and defined the fuzzy set. Atanassov introduced the degree of non membership/falsehood (f) in 1986 and defined the intuitionistic fuzzy set. Smarandache introduced the degree of indeterminacy/neutrality (i) as independent component in 1995 (published in 1998) and defined the neutrosophic set on three components (t,i,f) = (truth, indeterminacy, falsehood). The words “neutrosophy” and “neutrosophic” were coined/invented by F. Smarandache in his 1998 book. Etymologically, “neutro-sophy” (noun) [French neutre 1), or complete information (sum of components = 1).