Discrete Mathematics and Combinatorics Commons^™

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

Theory & 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 & 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 & 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 & 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 & 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 & 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) …

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

Theory & 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 …

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

Theory & 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 …

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

Theory & 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 & 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 & 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 …

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

Theory & 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 if the diametrical graph of (X, d _ε) with d _ε (x, y) = min{d(x, y), ε} is complete multipartite for every ε ∈ (0, d* …

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

Theory & 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 …

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

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).

3-Uniform 4-Path Decompositions Of Complete 3-Uniform Hypergraphs, Rachel Mccann

Mathematical Sciences Undergraduate Honors Theses

The complete 3-uniform hypergraph of order v is denoted as K_v and consists of vertex set V with size v and edge set E, containing all 3-element subsets of V. We consider a 3-uniform hypergraph P₇, a path with vertex set {v₁, v₂, v₃, v₄, v₅, v₆, v₇} and edge set {{v₁, v₂, v₃}, {v₂, v₃, v₄}, {v₄, v₅, v₆}, {v₅, v_{6 …}

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 …