Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

1,115 Full-Text Articles 1,295 Authors 292,068 Downloads 114 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

1,115 full-text articles. Page 2 of 44.

Characteristic Sets Of Matroids, Dony Varghese 2022 University of Tennessee, Knoxville

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 …


Radio Number Of Hamming Graphs Of Diameter 3, Jason DeVito, Amanda Niedzialomski, Jennifer Warren 2022 University of Tennessee Martin

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)\to \Z_+$ is called a \emph{radio labeling of $G$} if it satisfies $|f(u)-f(v)|\geq\diam(G)+1-d(u,v)$ for all distinct vertices $u,v\in V(G)$. The \emph{radio number of $G$} is the minimal span over all radio labelings of $G$. If a bijective radio labeling onto $\{1,2,\dots,|V(G)|\}$ exists, $G$ is called a \emph{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 2022 The Chinese University of Hong Kong

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$-\textbf{antimagic} if there exists an edge labeling $f: E(G) \to A \setminus \{0\}$ such that the induced vertex labeling $f^+: V(G) \to A$, defined by $f^+(v) = \Sigma$ $\{f(u,v): (u, v) \in 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 2022 Azarbaijan Shahid Madani University

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\setminus S$ has a neighbor in $S$ and a neighbor in $V\setminus S$. The minimum cardinality of a restrained dominating set is the restrained domination number $\gamma_{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\subseteq E(\overline{G})$ for which $\gamma _{r}(G+F)


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

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 \in V(C_{p}(D))$, $xy \in E(C_{p}(D))$ if and only if there exist distinct $p$ vertices $v_{1},$ $v_{2},$ $...,$ $v_{p}$ $\in$ $V(D)$ such that $x \rightarrow v_{i}$, $y \rightarrow v_{i}$ $\in$ $A(D)$ for each $i=1,2,$ $...,$ $p$.

We show the $H_1 \cup H_2$ is a $p$-competition graph of a loopless digraph without symmetric arcs for $p \geq 2$, where $H_1$ and $H_2$ are $p$-competition graphs of loopless digraphs without symmetric arcs and $V(H_1) \cap V(H_2)$ $=$ $\{ \alpha \}$. For $p$-competition graphs of …


Harmonious Labelings Via Cosets And Subcosets, Jared L. Painter, Holleigh C. Landers, Walker M. Mattox 2022 University of North Alabama

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. We will …


Total Colouring Of New Classes Of Subcubic Graphs, Sethuraman G, Velankanni Anthonymuthu 2022 Anna University, Chennai

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 $\chi^{\prime\prime}(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$, $\chi^{\prime\prime}(G) \leq \Delta(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 triangles are exactly …


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

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, …


Geodesic Bipancyclicity Of The Cartesian Product Of Graphs, Amruta V. Shinde, Y.M. Borse 2022 Savitribai Phule Pune University

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\leq l \leq |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 \geq 2$ every $n$-dimensional torus is a …


One-Factorizations Of The Complete Graph $K_{P+1}$ Arising From Parabolas, György Kiss, Nicola Pace, Angelo Sonnino 2022 Eötvös Loránd University

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.


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

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

Theory and Applications of Graphs

A {\em $k$-domination number} of a graph $G$ is minimum cardinality of a $k$-dominating set of $G$, where a subset $S \subseteq V(G)$ is a {\em $k$-dominating set} if each vertex $v\in V(G)\setminus S$ is adjacent to at least $k$ vertices in $S$. It is known that for any graph $G$ with $\Delta(G) \geq k \geq 2$, $\gamma_k(G) \geq \gamma(G) + k - 2$, and then $\gamma_k(G) > \gamma(G)$ for any $k\geq 3$, where $\gamma(G) = \gamma_1(G)$ is the usual domination number. Thus, it is the most interesting problem to characterize graphs $G$ with $\gamma_2(G) = \gamma(G)$. In this paper, we …


Using Magic To Teach Computer Programming, Dale F. Reed, Ronald I. Greenberg 2022 University of Illinois at Chicago

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 …


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

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 Kn on n vertices, a perfect (respectively, near-perfect) matching M in Kn 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 Kn by circular distance, and we denote the resulting complete graph by Kn. We show that when Kn 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 …


Ultrametrics And Complete Multipartite Graphs, Viktoriia Viktorivna Bilet, Oleksiy Dovgoshey, Yuriy Nikitovich Kononov 2022 Institute of Applied Mathematic and Mechanics of NAS of Ukraine

Ultrametrics And Complete Multipartite Graphs, Viktoriia Viktorivna Bilet, Oleksiy Dovgoshey, Yuriy Nikitovich Kononov

Theory and Applications of Graphs

Let \((X, d)\) be a semimetric space and let \(G\) be a graph. We say that \(G\) is the diametrical graph of \((X, d)\) if \(X\) is the vertex set of \(G\) and the adjacency of vertices \(x\) and \(y\) is equivalent to the equality \(\diam X = d(x, y)\). It is shown that a semimetric space \((X, d)\) with diameter \(d^*\) is ultrametric iff the diametrical graph of \((X, d_{\varepsilon})\) with \(d_{\varepsilon}(x, y) = \min\{d(x, y), \varepsilon\}\) is complete multipartite for every \(\varepsilon \in (0, d^*)\). A refinement of the last result is given for totally bounded ultrametric spaces. …


Unomaha Problem Of The Week (2021-2022 Edition), Brad Horner, Jordan M. Sahs 2022 University of Nebraska at Omaha

Unomaha Problem Of The Week (2021-2022 Edition), Brad Horner, Jordan M. Sahs

UNO Student Research and Creative Activity Fair

The University of Omaha math department's Problem of the Week was taken over in Fall 2019 from faculty by the authors. The structure: each semester (Fall and Spring), three problems are given per week for twelve weeks, with each problem worth ten points - mimicking the structure of arguably the most well-regarded university math competition around, the Putnam Competition, with prizes awarded to top-scorers at semester's end. The weekly competition was halted midway through Spring 2020 due to COVID-19, but relaunched again in Fall 2021, with massive changes.

Now there are three difficulty tiers to POW problems, roughly corresponding to …


An Even 2-Factor In The Line Graph Of A Cubic Graph, SeungJae Eom, Kenta Ozeki 2022 Yokohama National University

An Even 2-Factor In The Line Graph Of A Cubic Graph, Seungjae Eom, Kenta Ozeki

Theory and Applications of Graphs

An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence, we are interested in whether those graphs have an even 2-factor. Bonisoli and Bonvicini proved that the line graph of a connected cubic graph G with an even number of edges has an even 2-factor, if G has a perfect matching [Even cycles and even …


On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik 2022 Lehigh University

On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik

Communications on Number Theory and Combinatorial Theory

Graph pebbling can be extended to a two-player game on a graph G, called Two-Player Graph Pebbling, with players Mover and Defender. The players each use pebbling moves, the act of removing two pebbles from one vertex and placing one of the pebbles on an adjacent vertex, to win. Mover wins if they can place a pebble on a specified vertex. Defender wins if the specified vertex is pebble-free and there are no more pebbling moves on the vertices of G. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement …


Tiling Rectangles And 2-Deficient Rectangles With L-Pentominoes, Monica Kane 2022 California Lutheran University

Tiling Rectangles And 2-Deficient Rectangles With L-Pentominoes, Monica Kane

Rose-Hulman Undergraduate Mathematics Journal

We investigate tiling rectangles and 2-deficient rectangles with L-pentominoes. First, we determine exactly when a rectangle can be tiled with L-pentominoes. We then determine locations for pairs of unit squares that can always be removed from an m × n rectangle to produce a tileable 2-deficient rectangle when m ≡ 1 (mod 5), n ≡ 2 (mod 5) and when m ≡ 3 (mod 5), n ≡ 4 (mod 5).


Extremal Problems In Graph Saturation And Covering, Adam Volk 2022 University of Nebraska-Lincoln

Extremal Problems In Graph Saturation And Covering, Adam Volk

Dissertations, Theses, and Student Research Papers in Mathematics

This dissertation considers several problems in extremal graph theory with the aim of finding the maximum or minimum number of certain subgraph counts given local conditions. The local conditions of interest to us are saturation and covering. Given graphs F and H, a graph G is said to be F-saturated if it does not contain any copy of F, but the addition of any missing edge in G creates at least one copy of F. We say that G is H-covered if every vertex of G is contained in at least one copy of H. In the former setting, we …


Structure Of Number Theoretic Graphs, Lee Trent 2022 Rose-Hulman Institute of Technology

Structure Of Number Theoretic Graphs, Lee Trent

Mathematical Sciences Technical Reports (MSTR)

The tools of graph theory can be used to investigate the structure
imposed on the integers by various relations. Here we investigate two
kinds of graphs. The first, a square product graph, takes for its vertices
the integers 1 through n, and draws edges between numbers whose product
is a square. The second, a square product graph, has the same vertex set,
and draws edges between numbers whose sum is a square.
We investigate the structure of these graphs. For square product
graphs, we provide a rather complete characterization of their structure as
a union of disjoint complete graphs. For …


Digital Commons powered by bepress