Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Keyword
-
- Graph theory (2)
- $L(3 (1)
- $\alpha$-labeling (1)
- 1)$-labeling (1)
- 2 (1)
-
- 2-Domination number (1)
- Alternate m-triangular snake graph (1)
- Amalgamation (1)
- Art gallery problem (1)
- Art gallery theorem (1)
- B-nomial numbers (1)
- Betweenness-uniform graph (1)
- Binomial (1)
- Cartesian product (1)
- Cartesian product of paths (1)
- Circular distance (1)
- Combinatorial Nullstellensatz (1)
- Compact ultrametric space (1)
- Complete graph (1)
- Complete multipartite graph (1)
- Computational geometry (1)
- Connectedness (1)
- Convex geometry (1)
- Cosets (1)
- Cube connected path (1)
- Cut-vertex (1)
- Cycles (1)
- Cyclic snake (1)
- Deficient rectangles (1)
- Determinant (1)
Articles 1 - 30 of 32
Full-Text Articles in Discrete Mathematics and Combinatorics
Meertens Number And Its Variations, Chai Wah Wu
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.
(R1979) Permanent Of Toeplitz-Hessenberg Matrices With Generalized Fibonacci And Lucas Entries, Hacène Belbachir, Amine Belkhir, Ihab-Eddine Djellas
(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.
Path-Stick Solitaire On Graphs, Jan-Hendrik De Wiljes, Martin Kreh
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.
Alpha Labeling Of Amalgamated Cycles, Christian Barrientos
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
(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.
(Si10-054) Nonsplit Edge Geodetic Domination Number Of A Graph, P. Arul Paul Sudhahar, J. Jeba Lisa
(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
(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.
Radio Number Of Hamming Graphs Of Diameter 3, Jason Devito, Amanda Niedzialomski, Jennifer Warren
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
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
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 rr(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
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 Cp(D) of D is the graph satisfying the following: V(Cp(D))=V(D), for x,y ∈ V(Cp(D)), xy ∈ E(Cp(D)) if and only if there exist distinct p vertices v1, v2, ..., vp ∈ V(D) such that x → vi, y → vi ∈ A(D) for each i=1,2, ..., p.
We show the H1 ∪ H2 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
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. …
Geodesic Bipancyclicity Of The Cartesian Product Of Graphs, Amruta V. Shinde, Y.M. Borse
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 …
On The Total Set Chromatic Number Of Graphs, Mark Anthony C. Tolentino, Gerone Russel J. Eugenio, Mari-Jo P. Ruiz
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) …
Total Colouring Of New Classes Of Subcubic Graphs, Sethuraman G, Velankanni Anthonymuthu
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 …
One-Factorizations Of The Complete Graph $K_{P+1}$ Arising From Parabolas, György Kiss, Nicola Pace, Angelo Sonnino
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
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 …
Rainbow Perfect And Near-Perfect Matchings In Complete Graphs With Edges Colored By Circular Distance, Shuhei Saitoh, Naoki Matsumoto, Wei Wu
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 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
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 if the diametrical graph of (X, d ε) with d ε (x, y) = min{d(x, y), ε} is complete multipartite for every ε ∈ (0, d* …
An Even 2-Factor In The Line Graph Of A Cubic Graph, Seungjae Eom, Kenta Ozeki
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 …
On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik
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
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).
How To Guard An Art Gallery: A Simple Mathematical Problem, Natalie Petruzelli
How To Guard An Art Gallery: A Simple Mathematical Problem, Natalie Petruzelli
The Review: A Journal of Undergraduate Student Research
The art gallery problem is a geometry question that seeks to find the minimum number of guards necessary to guard an art gallery based on the qualities of the museum’s shape, specifically the number of walls. Solved by Václav Chvátal in 1975, the resulting Art Gallery Theorem dictates that ⌊n/3⌋ guards are always sufficient and sometimes necessary to guard an art gallery with n walls. This theorem, along with the argument that proves it, are accessible and interesting results even to one with little to no mathematical knowledge, introducing readers to common concepts in both geometry and graph …
A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar
A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar
Rose-Hulman Undergraduate Mathematics Journal
The Hadamard product (denoted by∗) of two power series A(x) =a0+a1x+a2x2+···and B(x) =b0+b1x+b2x2+··· is the power series A(x)∗B(x) =a0b0+a1b1x+a2b2x2+···. Although it is well known that the Hadamard product of two rational functions is also rational, a closed form expression of the Hadamard product of rational functions has not been found. Since any rational power series can be expanded by partial fractions as a polynomial plus a sum of power series …
Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang
Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang
Communications on Number Theory and Combinatorial Theory
Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be …
Prime Labelings On Planar Grid Graphs, Stephen James Curran
Prime Labelings On Planar Grid Graphs, Stephen James Curran
Theory and Applications of Graphs
It is known that for any prime p and any integer n such that 1≤n≤p there exists a prime labeling on the pxn planar grid graph PpxPn. We show that PpxPn has a prime labeling for any odd prime p and any integer n such that that p<n≤p2.
Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan
Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan
Theory and Applications of Graphs
The betweenness centrality of an edge e is, summed over all u,v ∈ V(G), the ratio of the number of shortest u,v-paths in G containing e to the number of shortest u,v-paths in G. Graphs whose vertices all have the same edge betweenness centrality are called edge betweeness-uniform. It was recently shown by Madaras, Hurajová, Newman, Miranda, Fl´orez , and Narayan that of the over 11.7 million graphs with ten vertices or fewer, only four graphs are edge betweenness-uniform but not edge-transitive. In this paper we present new results involving properties of betweenness-uniform graphs.
Chromatic Polynomials Of Signed Book Graphs, Deepak Sehrawat, Bikash Bhattacharjya
Chromatic Polynomials Of Signed Book Graphs, Deepak Sehrawat, Bikash Bhattacharjya
Theory and Applications of Graphs
For m ≥ 3 and n ≥ 1, the m-cycle book graph B(m,n) consists of n copies of the cycle Cm with one common edge. In this paper, we prove that (a) the number of switching non-isomorphic signed B(m,n) is n+1, and (b) the chromatic number of a signed B(m,n) is either 2 or 3. We also obtain explicit formulas for the chromatic polynomials and the zero-free chromatic polynomials of switching non-isomorphic signed book graphs.
Connectedness Of Unit Distance Subgraphs Induced By Closed Convex Sets, Remie Janssen, Leonie Van Steijn
Connectedness Of Unit Distance Subgraphs Induced By Closed Convex Sets, Remie Janssen, Leonie Van Steijn
Theory and Applications of Graphs
The unit distance graph G1Rd is the infinite graph whose nodes are points in Rd, with an edge between two points if the Euclidean distance between these points is 1. The 2-dimensional version G1R2 of this graph is typically studied for its chromatic number, as in the Hadwiger-Nelson problem. However, other properties of unit distance graphs are rarely studied. Here, we consider the restriction of G1Rd to closed convex subsets X of Rd. We show that the graph G1Rd[X] is connected precisely when the radius of …
Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings, Richard M. Low, Dan Roberts
Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings, Richard M. Low, Dan Roberts
Theory and Applications of Graphs
Let A be a nontrivial abelian group and A* = A \ {0}. A graph is A-magic if there exists an edge labeling f using elements of A* which induces a constant vertex labeling of the graph. Such a labeling f is called an A-magic labeling and the constant value of the induced vertex labeling is called an A-magic value. In this paper, we use the Combinatorial Nullstellensatz to show the existence of Ζp-magic labelings (prime p ≥ 3 ) for various graphs, without having to construct the Ζp-magic labelings. Through many …