skip to main content


Title: Notes on Growing a Tree in a Graph
We study the height of a spanning tree $T$ of a graph $G$ obtained by starting with a single vertex of $G$ and repeatedly selecting, uniformly at random, an edge of $G$ with exactly one endpoint in $T$ and adding this edge to $T$.  more » « less
Award ID(s):
1661063
NSF-PAR ID:
10158516
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
Random structures algorithms
Volume:
55
ISSN:
1042-9832
Page Range / eLocation ID:
290-312
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graphGat least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph$$\varvec{(G,\lambda )}$$(G,λ), with$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$λ:E(G)2[τ], an edge$$\varvec{e}\varvec{\in } \varvec{E(G)}$$eE(G)is available only at the times specified by$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$λ(e)[τ], in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether$$\varvec{(G,\lambda )}$$(G,λ)has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{\texttt {NP}}$$NP-complete even if$$\varvec{\tau = 2}$$τ=2. In contrast, in the general case, solving any of these problems is$$\varvec{\texttt {NP}}$$NP-complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {XP}}$$XPalgorithms parametrized by$$\varvec{\tau }$$τfor walks, and by$$\varvec{\tau +tw(G)}$$τ+tw(G)for trails and local trails, where$$\varvec{tw(G)}$$tw(G)refers to the treewidth of$$\varvec{G}$$G.

     
    more » « less
  2. Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the sub-curve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log |V (G)|)), and s, t ∈ V (G), outputs a β-stretch path between s and t, if a (1 − ε)β-stretch path between s and t exists in the drawing. 
    more » « less
  3. null (Ed.)
    A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $T$ with $n$~edges, it is conjectured that there exists a labeling $f\colon V(T) \to \{0,1,\ldots,n\}$ such that the set of induced edge labels $\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$ is exactly $\{1,2,\ldots,n\}$. We extend this concept to allow for multigraphs with edge multiplicity at most~$2$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $G$ with $n$~edges is a one-to-one function $f\colon V(G) \to \{0,1,\ldots,n\}$ such that the multiset of induced edge labels is comprised of two copies of each element in $\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$ and, if $n$ is odd, one copy of $\bigl\{ \lceil n/2 \rceil \bigr\}$. When $n$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $n \not\equiv 1 \pmod{4}$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $2$-fold graceful. 
    more » « less
  4. We study the height of a spanning tree T of a graphGobtained by starting with a single vertex ofGand repeatedly selecting, uniformly at random, an edge ofGwith exactly one endpoint inTand adding this edge toT.

     
    more » « less
  5. Given a graph G = (V, E) and a subset T ⊆ V of terminals, a Steiner tree of G is a tree that spans T. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of G. Vertex-weighted problems have applications in network design and routing, where there are different costs for installing or maintaining facilities at different vertices. We study a natural generalization of the VST problem motivated by multi-level graph construction, the vertex-weighted grade-of-service Steiner tree problem (V-GSST), which can be stated as follows: given a graph G and terminals T, where each terminal v ∈ T requires a facility of a minimum grade of service R(v) ∈ {1, 2, . . . `}, compute a Steiner tree G0 by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in G 0 with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on `, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a (2 ln |T|)-approximation, where T is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. Finally, we show that this problem is a special case of the directed Steiner tree problem and provide an integer linear programming (ILP) formulation for the V-GSST problem. 
    more » « less