Discrete Mathematics and Combinatorics Commons^™

Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory & Applications of Graphs

Radio labelling problem of graphs have their roots in communication problem known as Channel Assignment Problem. For a simple connected graph G=(V(G), E(G)), a radio labeling is a mapping f : V(G) →{0,1,2,…} such that |f(u)-f(v)|≥ diam(G)+1-d(u,v) for each pair of distinct vertices u,v ∈ V(G), where diam(G) is the diameter of G and d(u,v) is the distance between u and v. A radio labeling f of a graph G is a radio graceful labeling of G if f(V(G)) = {0,1,… |V(G)|-1}. A graph for which a radio graceful labeling exists is called radio graceful. …

Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga

Theory & Applications of Graphs

An annulus triangulation G is a 2-connected plane graph with two disjoint faces f₁ and f₂ such that every face other than f₁ and f₂ are triangular, and that every vertex of G is contained in the boundary cycle of f₁ or f₂. In this paper, we prove that every annulus triangulation G with t vertices of degree 2 has a dominating set with cardinality at most ⌊ \frac{|V(G)|+t+1}{4} ⌋ if G is not isomorphic to the octahedron. In particular, this bound is best possible.

An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff

Theory & Applications of Graphs

Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs. In this note we improve the recent bound of Breŝar by applying a technique of Zerbib to show that for any graphs G and H, γ(G x H)≥ γ (G) 2/3(γ(H)-ρ(H)+1), where γ is the domination number, ρ is the 2-packing number, and x is the Cartesian product.

On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila

Theory & Applications of Graphs

Given a simple graph G, a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S. Denote the domination number, which is the size of any minimum dominating set of G, by γ(G). For any integer k ≥ 1, a function f : V (G) → {0, 1, . . ., k} is called a {k}-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a {k}-dominating function is the sum of its values over all …

Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami

Theory & Applications of Graphs

In this paper, we regard each edge of a connected graph G as a line segment having a unit length, and focus on not only the "vertices" but also any "point" lying along such a line segment. So we can define the distance between two points on G as the length of a shortest curve joining them along G. The beans function B_G(x) of a connected graph G is defined as the maximum number of points on G such that any pair of points have distance at least x>0. We shall show a recursive formula for …

Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini

Theory & Applications of Graphs

For n ≥ 15, we prove that the minimum number of triangles in an n-vertex K₄-saturated graph with minimum degree 4 is exactly 2n-4, and that there is a unique extremal graph. This is a triangle version of a result of Alon, Erdos, Holzman, and Krivelevich from 1996. Additionally, we show that for any s > r ≥ 3 and t ≥ 2 (s-2)+1, there is a K_s-saturated n-vertex graph with minimum degree t that has \binom{ s-2}{r-1}2^{r-1} n + c_{s,r,t} copies of K_r. This shows that …

Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani

Theory & Applications of Graphs

For connected graphs G and H, Graham conjectured that π(G □ H) ≤ π(G) π(H) where π(G), π (H), and π(G □ H) are the pebbling numbers of G, H, and the Cartesian product G □ H, respectively. In this paper, we show that the inequality holds when H is a complete graph of sufficiently large order in terms of graph parameters of G.

Rearrangement Operations On Unrooted Phylogenetic Networks, Remie Janssen, Jonathan Klawitter

Theory & Applications of Graphs

Rearrangement operations transform a phylogenetic tree into another one and hence induce a metric on the space of phylogenetic trees. Popular operations for unrooted phylogenetic trees are NNI (nearest neighbour interchange), SPR (subtree prune and regraft), and TBR (tree bisection and reconnection). Recently, these operations have been extended to unrooted phylogenetic networks, which are generalisations of phylogenetic trees that can model reticulated evolutionary relationships. Here, we study global and local properties of spaces of phylogenetic networks under these three operations. In particular, we prove connectedness and asymptotic bounds on the diameters of spaces of different classes of phylogenetic networks, including …

Conditional Strong Matching Preclusion Of The Alternating Group Graph, Mohamad Abdallah, Eddie Cheng

Theory & Applications of Graphs

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. Park and Ihm introduced the problem of strong matching preclusion under the condition that no isolated vertex is created as a result of faults. In this paper, we find the conditional strong matching preclusion number for the n-dimensional alternating group graph AG_n.

Forcibly-Biconnected Graphical Degree Sequences: Decision Algorithms And Enumerative Results, Kai Wang

Theory & Applications of Graphs

We present an algorithm to test whether a given graphical degree sequence is forcibly biconnected. The worst case time complexity of the algorithm is shown to be exponential but it is still much better than the previous basic algorithm for this problem. We show through experimental evaluations that the algorithm is efficient on average. We also adapt the classic algorithm of Ruskey et al. and that of Barnes and Savage to obtain some enumerative results about forcibly biconnected graphical degree sequences of given length n and forcibly biconnected graphical partitions of given even integer n. Based on these enumerative …

Laplacian Spectral Characterization Of Signed Sun Graphs, Fatemeh Motialah, Mohammad Hassan Shirdareh Haghighi

Theory & Applications of Graphs

A sun SG_n is a graph of order 2n consisting of a cycle C_n, n ≥ 3, to each vertex of it a pendant edge is attached. In this paper, we prove that unbalanced signed sun graphs are determined by their Laplacian spectra. Also we show that a balanced signed sun graph is determined by its Laplacian spectrum if and only if n is odd.

Fractional Strong Matching Preclusion For Two Variants Of Hypercubes, Huifen Ge, Tianlong Ma, Miaolin Wu, Yuzhi Xiao

Theory & Applications of Graphs

Let F be a subset of edges and vertices of a graph G. If G-F has no fractional perfect matching, then F is a fractional strong matching preclusion set of G. The fractional strong matching preclusion number is the cardinality of a minimum fractional strong matching preclusion set. In this paper, we mainly study the fractional strong matching preclusion problem for two variants of hypercubes, the multiply twisted cube and the locally twisted cube, which are two of the most popular interconnection networks. In addition, we classify all the optimal fractional strong matching preclusion set of each.

Colored Complete Hypergraphs Containing No Rainbow Berge Triangles, Colton Magnant

Theory & Applications of Graphs

The study of graph Ramsey numbers within restricted colorings, in particular forbidding a rainbow triangle, has recently been blossoming under the name Gallai-Ramsey numbers. In this work, we extend the main structural tool from rainbow triangle free colorings of complete graphs to rainbow Berge triangle free colorings of hypergraphs. In doing so, some other concepts and results are also translated from graphs to hypergraphs.

Maximum Oriented Forcing Number For Complete Graphs, Yair Caro, Ryan Pepper

Theory & Applications of Graphs

The maximum oriented k-forcing number of a simple graph G, written MOF_k(G), is the maximum directed k-forcing number among all orientations of G. This invariant was recently introduced by Caro, Davila and Pepper in [6], and in the current paper we study the special case where G is the complete graph with order n, denoted K_n . While MOF_k(G) is an invariant for the underlying simple graph G, MOF_k(K_n) can also be interpreted as an interesting property for tournaments. Our main results …

Matching Preclusion Of The Generalized Petersen Graph, Ajay Arora, Eddie Cheng, Christopher Melekian

Theory & Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph with no perfect matchings. In this paper we determine the matching preclusion number for the generalized Petersen graph P(n,k) and classify the optimal sets.

Series-Parallel Operations With Alpha-Graphs, Christian Barrientos, Sarah Minion

Theory & Applications of Graphs

Among difference vertex labelings of graphs, α-labelings are the most restrictive one. A graph is an α-graph if it admits an α-labeling. In this work, we study a new alternative to construct α-graphs using, the well-known, series-parallel operations on smaller α-graphs. As an application of the series operation, we show that all members of a subfamily of all trees with maximum degree 4, obtained using vertex amalgamation of copies of the path Ρ₁₁}, are α-graphs. We also show that the one-point union of up to four copies of Κ_n,n is an …

Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang

Theory & Applications of Graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu [18] recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of G, denoted by fmp(G), is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of G, denoted by fsmp(G), is the minimum number of vertices and edges whose deletion …

Singular Ramsey And Turán Numbers, Yair Caro, Zsolt Tuza

Theory & Applications of Graphs

We say that a subgraph F of a graph G is singular if the degrees d_G(v) are all equal or all distinct for the vertices v ∈ V (F). The singular Ramsey number Rs(F) is the smallest positive integer n such that, for every m at least n, in every edge 2-coloring of K_m, at least one of the color classes contains F as a singular subgraph. In a similar flavor, the singular Turán number Ts(n,F) is defined as the maximum number of edges in a graph of order n, …

Gallai-Ramsey Number For Classes Of Brooms, Benjamin J. Hamlin

College of Graduate Studies: Theses & Dissertations

Given a graph $G$, we consider the problem of finding the minimum number $n$ such that any $k$ edge colored complete graph on $n$ vertices contains either a rainbow colored triangle or a monochromatic copy of the graph $G$, denoted $gr_k(K_{3}:G)$. More precisely we consider $G=B_{m,\ell}$ where $B_{m,\ell}$ is a broom graph with $m$ representing the number of vertices on the handle and $\ell$ representing the number of bristle vertices. We develop a technique to reduce the difficulty of finding $gr_{k}(K_{3}:B_{m,\ell})$, and use the technique to prove a few cases with a fixed handle length, but arbitrarily many bristles. Further, …

Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier

College of Graduate Studies: Theses & Dissertations

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound …

Taking A Canon To The Adjunction Formula, Paul M. Harrelson

College of Graduate Studies: Theses & Dissertations

In this paper, we show how the canonical divisor of a graph is related to the canonical divisor of its subgraph. The use of chip firing and the adjunction formula for graphs ex- plains said relation and even completes it. We go on to show the difference between the formula for full subgraphs and that of non-full subgraphs. Examples are used to simplify these results and to see the adjunction formula in action. Finally, we show that though the adjunction formula seems simple at first glance, it is somewhat complex and rather useful.

Inverse Problems Related To The Wiener And Steiner-Wiener Indices, Matthew Gentry

College of Graduate Studies: Theses & Dissertations

In a graph, the generalized distance between multiple vertices is the minimum number of edges in a connected subgraph that contains these vertices. When we consider such distances between all subsets of $k$ vertices and take the sum, it is called the Steiner $k$-Wiener index and has important applications in Chemical Graph Theory. In this thesis we consider the inverse problems related to the Steiner Wiener index, i.e. for what positive integers is there a graph with Steiner Wiener index of that value?

Subsets Of Vertices Of The Same Size And The Same Maximum Distance, Maria Axenovich, Dominik Duerrschnabel

Theory & Applications of Graphs

For a simple connected graph G=(V,E) and a subset X of its vertices, let

d*(X) = max {dist}_G(x,y): x,y ∈ X}

and let h*(G) be the largest k such that there are disjoint vertex subsets A and B of G, each of size k such that d*(A) = d*(B). Let h*(n) = min {h*(G): |V(G)|=n}. We prove that h*(n) =⌊(n+1)/3 ⌋, for n ≥ 6. This solves the homometric set problem restricted to the largest distance exactly. In addition we compare h*(G) with a respective function h_diam(G), where …

Finite Simple Graphs And Their Associated Graph Lattices, James B. Hart, Brian Frazier

Theory & Applications of Graphs

In his 2005 dissertation, Antoine Vella explored combinatorical aspects of finite graphs utilizing a topological space whose open sets are intimately tied to the structure of the graph. In this paper, we go a step further and examine some aspects of the open set lattices induced by these topological spaces. In particular, we will characterize all lattices that constitute the opens for finite simple graphs endowed with this topology, explore the structure of these lattices, and show that these lattices contain information necessary to reconstruct the graph and its complement in several ways.

Reducing The Maximum Degree Of A Graph By Deleting Vertices: The Extremal Cases, Peter Borg, Kurt Fenech

Theory & Applications of Graphs

Let λ(G) denote the smallest number of vertices that can be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. In a recent paper, we proved that if n is the number of vertices of G,k is the maximum degree of G, and t is the number of vertices of degree k, then λ: (G) ≤ n+(k-1)t}{2k}. We also showed that λ (G) ≤ \frac{n}{k+1} if G is a tree. In this paper, we provide a new proof of the first bound and use it to determine the graphs that …

Minimal Graphs With A Specified Code Map Image, Paul Feit

Theory & Applications of Graphs

Let G be a graph and ^e1,…^en be n distinct vertices. Let ρ be the metric on G. The code map on vertices, corresponding to this list, is c(x)=(ρ (x,^e1),…ρ (x,^en)). This paper introduces a variation: begin with V ⊆ Ζ^n for some n, and consider assignments of edges E such that the identity function on V is a code map for G=(V,E). Refer to such a set E as a code-match.

An earlier paper classified subsets of V for which at least one code-match exists. We prove …

Integer-Antimagic Spectra Of Disjoint Unions Of Cycles, Wai Chee Shiu

Theory & Applications of Graphs

Let A be a non-trivial abelian group. A simple graph G = (V, E) is A-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) = \sum_{uv\in E(G)}f(uv), is injective. The integer-antimagic spectrum of a graph G is the set IAM(G) = \{k\;|\; G \textnormal{ is } \mathbb{Z}_k\textnormal{-antimagic and } k \geq 2\}. In this paper, we determine the integer-antimagic spectra of disjoint unions of cycles.

An Efficient Algorithm To Test Forcibly-Connectedness Of Graphical Degree Sequences, Kai Wang

Theory & Applications of Graphs

We present an algorithm to test whether a given graphical degree sequence is forcibly connected or not and prove its correctness. We also outline the extensions of the algorithm to test whether a given graphical degree sequence is forcibly k-connected or not for every fixed k ≥ 2. We show through experimental evaluations that the algorithm is efficient on average, though its worst case run time is probably exponential. We also adapt Ruskey et al's classic algorithm to enumerate zero-free graphical degree sequences of length n and Barnes and Savage's classic algorithm to enumerate graphical partitions of even integer …

Finite Asymptotic Clusters Of Metric Spaces, Viktoriia Bilet, Oleksiy Dovgoshey

Theory & Applications of Graphs

Let (X, d) be an unbounded metric space and let \tilde r=(r_n)_{n\in\mathbb N} be a sequence of positive real numbers tending to infinity. A pretangent space \Omega_{\infty, \tilde r}^{X} to (X, d) at infinity is a limit of the rescaling sequence \left(X, \frac{1}{r_n}d\right). The set of all pretangent spaces \Omega_{\infty, \tilde r}^{X} is called an asymptotic cluster of pretangent spaces. Such a cluster can be considered as a weighted graph (G_{X, \tilde r}, \rho_{X}) whose maximal cliques coincide with \Omega_{\infty, \tilde r}^{X} and the weight \rho_{X} is defined by metrics on \Omega_{\infty, \tilde r}^{X}. We describe the structure …

Gamma-Realizability And Other Musings On Inverse Domination, John Asplund, Joe Chaffee, James M. Hammer Iii, Matt Noble

Theory & Applications of Graphs

We introduce and study γ-realizable sequences. For a finite, simple graph G containing no isolated vertices, I ⊆ V(G) is said to be an inverse dominating set if I dominates all of G and I is contained by the complement of some minimum dominating set D. Define a sequence of positive integers (x₁,…, x_n) to be γ-realizable if there exists a graph G having exactly n distinct minimum dominating sets D₁,… D_n where for each i ∈ {1,… n}, the minimum size of an inverse dominating set in V(G) …