Discrete Mathematics and Combinatorics Commons^™

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

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

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory and Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to …

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory and Applications of Graphs

We say that a blinking node system modulo n is an ordered pair (G,L) where G is a graph and L is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of G such that the position of each vertex modulo n is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other graphs.

On The Planarity Of Generalized Line Graphs, Khawlah H. Alhulwah, Mohra Zayed, Ping Zhang

Theory and Applications of Graphs

One of the most familiar derived graphs is the line graph. The line graph L(G) of a graph G is that graph whose vertices are the edges of G where two vertices of L(G) are adjacent if the corresponding edges are adjacent in G. Two nontrivial paths P and Q in a graph G are said to be adjacent paths in G if P and Q have exactly one vertex in common and this vertex is an end-vertex of both P and Q. For an integer ℓ ≥ 2, the ℓ -line graph Lℓ (G) of a …

A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu

Theory and Applications of Graphs

The concept of monochromatic connection of graphs was introduced by Caro and Yuster in 2011. Recently, a lot of results have been published about it.
In this survey, we attempt to bring together all the results that dealt with it.
We begin with an introduction, and then classify the results into the following categories: monochromatic connection coloring of edge-version, monochromatic connection coloring of vertex-version, monochromatic index, monochromatic connection coloring of total-version.

Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

Theory and 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 that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of …

A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

Theory and Applications of Graphs

Given a graph H and a positive integer k, the k-color Gallai-Ramsey number gr_k(K3 : H) is defined to be the minimum number of vertices n for which any k-coloring of the complete graph K_n contains either a rainbow triangle or a monochromatic copy of H. The behavior of these numbers is rather well understood when H is bipartite but when H is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs H to a value that we conjecture to …