Discrete Mathematics and Combinatorics Commons^™

Meertens Number And Its Variations, Chai Wah Wu

Communications on Number Theory and Combinatorial Theory

In 1998, Bird introduced Meertens numbers as numbers that are invariant under a map similar to the Gödel encoding. In base 10, the only known Meertens number is 81312000. We look at some properties of Meertens numbers and consider variations of this concept. In particular, we consider variations of Meertens numbers where there is a finite time algorithm to decide whether such numbers exist, exhibit infinite families of these variations and provide bounds on parameters needed for their existence.

Irreducible Representations From Group Actions On Trees, Charlie Liou

Master's Theses

We study the representations of the symmetric group $S_n$ found by acting on

labeled graphs and trees with $n$ vertices. Our main results provide

combinatorial interpretations that give the number of times the irreducible

representations associated with the integer partitions $(n)$ and $(1^n)$ appear

in the representations. We describe a new sign

reversing involution with fixed points that provide a combinatorial

interpretation for the number of times the irreducible associated with the

integer partition $(n-1, 1)$ appears in the representations.

(R1979) Permanent Of Toeplitz-Hessenberg Matrices With Generalized Fibonacci And Lucas Entries, Hacène Belbachir, Amine Belkhir, Ihab-Eddine Djellas

Applications and Applied Mathematics: An International Journal (AAM)

In the present paper, we evaluate the permanent and determinant of some Toeplitz-Hessenberg matrices with generalized Fibonacci and generalized Lucas numbers as entries.We develop identities involving sums of products of generalized Fibonacci numbers and generalized Lucas numbers with multinomial coefficients using the matrix structure, and then we present an application of the determinant of such matrices.

Extension Of Fundamental Transversals And Euler’S Polyhedron Theorem, Joy Marie D'Andrea

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Modularity And Boolean Network Decomposition, Matthew Wheeler

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Path-Stick Solitaire On Graphs, Jan-Hendrik De Wiljes, Martin Kreh

Theory and Applications of Graphs

In 2011, Beeler and Hoilman generalised the game of peg solitaire to arbitrary connected graphs. Since then, peg solitaire and related games have been considered on many graph classes. In this paper, we introduce a variant of the game peg solitaire, called path-stick solitaire, which is played with sticks in edges instead of pegs in vertices. We prove several analogues to peg solitaire results for that game, mainly regarding different graph classes. Furthermore, we characterise, with very few exceptions, path-stick-solvable joins of graphs and provide some possible future research questions.

Combinatorial Algorithms For Graph Discovery And Experimental Design, Raghavendra K. Addanki

Doctoral Dissertations

In this thesis, we study the design and analysis of algorithms for discovering the structure and properties of an unknown graph, with applications in two different domains: causal inference and sublinear graph algorithms. In both these domains, graph discovery is possible using restricted forms of experiments, and our objective is to design low-cost experiments. First, we describe efficient experimental approaches to the causal discovery problem, which in its simplest form, asks us to identify the causal relations (edges of the unknown graph) between variables (vertices of the unknown graph) of a given system. For causal discovery, we study algorithms …

Alpha Labeling Of Amalgamated Cycles, Christian Barrientos

Theory and Applications of Graphs

A graceful labeling of a bipartite graph is an α-labeling if it has the property that the labels assigned to the vertices of one stable set of the graph are smaller than the labels assigned to the vertices of the other stable set. A concatenation of cycles is a connected graph formed by a collection of cycles, where each cycle shares at most either two vertices or two edges with other cycles in the collection. In this work we investigate the existence of α-labelings for this kind of graphs, exploring the concepts of vertex amalgamation to produce a …

(Si10-089) Integer Cordial Labeling Of Alternate Snake Graph And Irregular Snake Graph, Pratik Shah, Dharamvirsinh Parmar

Applications and Applied Mathematics: An International Journal (AAM)

If a graph G admits integer cordial labeling, it is called an integer cordial graph. In this paper we prove that Alternate m-triangular Snake graph, Quadrilateral Snake graph, Alternate m- quadrilateral Snake graph, Pentagonal Snake graph, Alternate m-pentagonal Snake graph, Irregular triangular Snake graph, Irregular quadrilateral Snake graph, and Irregular pentagonal Snake graphs are integer cordial graphs.

Conflict Dynamics In Scale-Free Networks With Degree Correlations And Hierarchical Structure, Eduardo Jacobo-Villegas, Bibiana Obregón-Quintana, Lev Guzmán-Vargas, Larry S. Liebovitch

Publications and Research

We present a study of the dynamic interactions between actors located on complex networks with scale-free and hierarchical scale-free topologies with assortative mixing, that is, correlations between the degree distributions of the actors. The actor’s state evolves according to a model that considers its previous state, the inertia to change, and the influence of its neighborhood. We show that the time evolution of the system depends on the percentage of cooperative or competitive
interactions. For scale-free networks, we find that the dispersion between actors is higher when all interactions are either cooperative or competitive, while a balanced presence of interactions …

(Si10-054) Nonsplit Edge Geodetic Domination Number Of A Graph, P. Arul Paul Sudhahar, J. Jeba Lisa

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, we have defined an inventive parameter called the nonsplit edge geodetic domination number of a graph, and some of its general properties are studied. The nonsplit edge geodetic domination number of some standard graph is obtained. In this work, we also determine the realization results of the nonsplit edge geodetic domination number and the edge geodetic number of a graph.

(Si10-130) On Regular Inverse Eccentric Fuzzy Graphs, N. Meenal, J. Jeromi Jovita

Applications and Applied Mathematics: An International Journal (AAM)

Two new concepts of regular inverse eccentric fuzzy graphs and totally regular inverse eccentric fuzzy graphs are established in this article. By illustrations, these two graphs are compared and the results are derived. Equivalent condition for the existence of these two graphs are found. The exact values of Order and Size for some standard inverse eccentric graphs are also derived.

Asymptotic Classes, Pseudofinite Cardinality And Dimension, Alexander Van Abel

Dissertations, Theses, and Capstone Projects

We explore the consequences of various model-theoretic tameness conditions upon the behavior of pseudofinite cardinality and dimension. We show that for pseudofinite theories which are either Morley Rank 1 or uncountably categorical, pseudofinite cardinality in ultraproducts satisfying such theories is highly well-behaved. On the other hand, it has been shown that pseudofinite dimension is not necessarily well-behaved in all ultraproducts of theories which are simple or supersimple; we extend such an observation by constructing simple and supersimple theories in which pseudofinite dimension is necessarily ill-behaved in all such ultraproducts. Additionally, we have novel results connecting various forms of asymptotic classes …

The On-Line Width Of Various Classes Of Posets., Israel R. Curbelo

Electronic Theses and Dissertations

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemer\'edi proved that any on-line algorithm could be forced to use $\binom{w+1}{2}$ chains to partition a poset of width $w$. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In the survey paper by Bosek et al., variants of the problem were studied where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size $d$. We prove …

Minimal Differential Graded Algebra Resolutions Related To Certain Stanley-Reisner Rings, Todd Anthony Morra

All Dissertations

We investigate algebra structures on resolutions of a special class of Cohen-Macaulay simplicial complexes. Given a simplicial complex, we define a pure simplicial complex called the purification. These complexes arise as a generalization of certain independence complexes and the resultant Stanley-Reisner rings have numerous desirable properties, e.g., they are Cohen-Macaulay. By realizing the purification in the context of work of D'alì, et al., we obtain a multi-graded, minimal free resolution of the Alexander dual ideal of the Stanley-Reisner ideal. We augment this in a standard way to obtain a resolution of the quotient ring, which is likewise minimal and multi-graded. …

Characteristic Sets Of Matroids, Dony Varghese

Doctoral Dissertations

Matroids are combinatorial structures that generalize the properties of linear independence. But not all matroids have linear representations. Furthermore, the existence of linear representations depends on the characteristic of the fields, and the linear characteristic set is the set of characteristics of fields over which a matroid has a linear representation. The algebraic independence in a field extension also defines a matroid, and also depends on the characteristic of the fields. The algebraic characteristic set is defined in the similar way as the linear characteristic set.

The linear representations and characteristic sets are well studied. But the algebraic representations and …

Verifying Sudoku Puzzles, Chelsea Schweer

Electronic Theses, Projects, and Dissertations

Sudoku puzzles, created by Meki Kaji around 1983, consist of a square 9 by 9 grid made up of 9 rows, 9 columns, and nine 3 by 3 square sub-grids called blocks. The goal of the puzzle is to be able to place the numbers 1 through 9 in every row, column, and block where no number is repeated in each row, column, and block. Imagine being given a completed Sudoku puzzle and having to check that it was solved correctly. You could just check all the rows columns and blocks (27 items), but is there a smaller number of …

Radio Number Of Hamming Graphs Of Diameter 3, Jason Devito, Amanda Niedzialomski, Jennifer Warren

Theory and Applications of Graphs

For G a simple, connected graph, a vertex labeling f:V(G) → Z+ is called a radio labeling of G if it satisfies |f(u)-f(v)|≥ diam(G)+1-d(u,v) for all distinct vertices u,v ∈ V(G). The radio number of G is the minimal span over all radio labelings of G. If a bijective radio labeling onto {1,2,…|V(G)|} exists, G is called a radio graceful graph. We determine the radio number of all diameter 3 Hamming graphs and show that an infinite subset of them is radio graceful.

On The Integer-Antimagic Spectra Of Non-Hamiltonian Graphs, Wai Chee Shiu, Richard M. Low

Theory and Applications of Graphs

Let A be a nontrivial abelian group. A connected simple graph G = (V, E) is A-antimagic if there exists an edge labeling f: E(G) → A \ {0} such that the induced vertex labeling f+: V(G) → A, defined by f+(v) = Σ {f(u,v): (u, v) ∈ E(G)}, is a one-to-one map. In this paper, we analyze the group-antimagic property for Cartesian products, hexagonal nets and theta graphs.

Restrained Reinforcement Number In Graphs, Kazhal Haghparast, Jafar Amjadi, Mustapha Chellali, Seyed Mahmoud Sheikholeslami

Theory and Applications of Graphs

A set S of vertices is a restrained dominating set of a graph G=(V,E) if every vertex in V\ S has a neighbor in S and a neighbor in V\S. The minimum cardinality of a restrained dominating set is the restrained domination number γ_r(G). In this paper we initiate the study of the restrained reinforcement number r_r(G) of a graph G defined as the cardinality of a smallest set of edges F ⊆ E( ‾G) for which γ_r(G + F) < γ_r(G), where ‾G denotes the complement graph of G. …

On P-Competition Graphs Of Loopless Hamiltonian Digraphs Without Symmetric Arcs And Graph Operations, Kuniharu Yokomura, Morimasa Tsuchiya

Theory and Applications of Graphs

For a digraph D, the p-competition graph C_p(D) of D is the graph satisfying the following: V(C_p(D))=V(D), for x,y ∈ V(C_p(D)), xy ∈ E(C_p(D)) if and only if there exist distinct p vertices v₁, v₂, ..., v_p ∈ V(D) such that x → v_i, y → v_i ∈ A(D) for each i=1,2, ..., p.

We show the H₁ ∪ H₂ is a p-competition graph of a loopless digraph without symmetric arcs for p ≥ 2 , where …

Harmonious Labelings Via Cosets And Subcosets, Jared L. Painter, Holleigh C. Landers, Walker M. Mattox

Theory and Applications of Graphs

In [Abueida, A. and Roblee, K., More harmonious labelings of families of disjoint unions of an odd cycle and certain trees, J. Combin. Math. Combin. Comput., 115 (2020), 61-68] it is shown that the disjoint union of an odd cycle and certain paths is harmonious, and that certain starlike trees are harmonious using properties of cosets for a particular subgroup of the integers modulo m, where m is the number of edges of the graph. We expand upon these results by first exploring the numerical properties when adding values from cosets and subcosets in the integers modulo m. …

On The Total Set Chromatic Number Of Graphs, Mark Anthony C. Tolentino, Gerone Russel J. Eugenio, Mari-Jo P. Ruiz

Theory and Applications of Graphs

Given a vertex coloring c of a graph, the neighborhood color set of a vertex is defined to be the set of all of its neighbors’ colors. The coloring c is called a set coloring if any two adjacent vertices have different neighborhood color sets. The set chromatic number χ_s(G) of a graph G is the minimum number of colors required in a set coloring of G. In this work, we investigate a total analog of set colorings; that is, we study set colorings of the total graph of graphs. Given a graph G = (V, E) …

Geodesic Bipancyclicity Of The Cartesian Product Of Graphs, Amruta V. Shinde, Y.M. Borse

Theory and Applications of Graphs

A cycle containing a shortest path between two vertices u and v in a graph G is called a (u,v)-geodesic cycle. A connected graph G is geodesic 2-bipancyclic, if every pair of vertices u,v of it is contained in a (u,v)-geodesic cycle of length l for each even integer l satisfying 2d + 2 ≤ l ≤ |V(G)|, where d is the distance between u and v. In this paper, we prove that the Cartesian product of two geodesic hamiltonian graphs is a geodesic 2-bipancyclic graph. As a consequence, we show that for n …

Total Colouring Of New Classes Of Subcubic Graphs, Sethuraman G, Velankanni Anthonymuthu

Theory and Applications of Graphs

The total chromatic number of a graph G, denoted χ”(G), is the least number of colours needed to colour the vertices and the edges of G such that no incident or adjacent elements (vertices or edges) receive the same colour. The popular Total Colouring Conjecture (TCC) posed by Behzad states that, for every simple graph G, χ”(G) ≤ Δ(G)+2. In this paper, we prove that the total chromatic number for a family of subcubic graphs called cube connected paths and also for a class of subcubic graphs having the property that the vertices are covered by independent …

Characterization Of Outerplanar Graphs With Equal 2-Domination And Domination Numbers, Naoki Matsumoto

Theory and Applications of Graphs

A k-domination number of a graph G is minimum cardinality of a k-dominating set of G, where a subset S ⊆ V(G) is a k-dominating set if each vertex v ∈ V(G) \ S is adjacent to at least k vertices in S. It is known that for any graph G with Δ(G) ≥ k ≥ 2, γ_k(G) ≥ γ(G) + k – 2, and then γk(G) > γ(G) for any k ≥ 3, where γ(G) = γ1(G) is the usual domination number. Thus, it is the most interesting problem to characterize graphs G with …

One-Factorizations Of The Complete Graph $K_{P+1}$ Arising From Parabolas, György Kiss, Nicola Pace, Angelo Sonnino

Theory and Applications of Graphs

There are three types of affine regular polygons in AG(2, q): ellipse, hyperbola and parabola. The first two cases have been investigated in previous papers. In this note, a particular class of geometric one-factorizations of the complete graph Kn arising from parabolas is constructed and described in full detail. With the support of computer aided investigation, it is also conjectured that up to isomorphisms this is the only one-factorization where each one-factor is either represented by a line or a parabola.

Using Magic To Teach Computer Programming, Dale F. Reed, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Magic can be used in project-based instruction to motivate students and provide a meaningful context for learning computer programming. This work describes several magic programs of the “Choose a Number” and “Pick a Card” varieties, making connections to underlying computing concepts.

Magic tricks presented as demonstrations and programming assignments elicit wonder and captivate students’ attention, so that students want to understand and replicate the work to show it to friends and family members. Capturing student interest and curiosity motivates them to learn the underlying programming concepts.

Two “Choose a Number” programs are shown where the computer is able to identify …

Relaxed Wythoff Has All Beatty Solutions, Jon Kay, Geremías Polanco

Mathematics Sciences: Faculty Publications

We find conditions under which the P-positions of three subtraction games arise as pairs of complementary Beatty sequences. The first game is due to Fraenkel and the second is an extension of the first game to non-monotone settings. We show that the P-positions of the second game can be inferred from the recurrence of Fraenkel's paper if a certain inequality is satisfied. This inequality is shown to be necessary if the P-positions are known to be pairs of complementary Beatty sequences, and the family of irrationals for which this inequality holds is explicitly given. We highlight several games in the …

Rainbow Perfect And Near-Perfect Matchings In Complete Graphs With Edges Colored By Circular Distance, Shuhei Saitoh, Naoki Matsumoto, Wei Wu

Theory and Applications of Graphs

Given an edge-colored complete graph K_n on n vertices, a perfect (respectively, near-perfect) matching M in K_n with an even (respectively, odd) number of vertices is rainbow if all edges have distinct colors. In this paper, we consider an edge coloring of K_n by circular distance, and we denote the resulting complete graph by K^●_n. We show that when K^●_n has an even number of vertices, it contains a rainbow perfect matching if and only if n=8k or n=8k+2, where k is a nonnegative integer. In the case of an odd …