Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

On claws belonging to every tournament

A directed graph is said to ben-unavoidable if it is contained as a subgraph by every tournament onn vertices. A number of theorems have been proven showing that certain graphs aren-unavoidable, the first being Rédei's results that every tournament has a Hamiltonian path. M. Saks and V. Sós gave more examples in [6] and also a conjecture that states: Every directed claw onn vertices such that the outdegree of the root is at most [n/2] isn-unavoidable. Here a claw is a rooted tree obtained by identifying the roots of a set of directed paths. We give a counterexample to this conjecture and prove the following result:any claw of rootdegreen/4 is n-unavoidable.     

On unavoidable hypergraphs

A r-uniform hypergraph H (or a r-graph, for short) is a collection E = E(H) of r-element subsets (called edges) of a set V = V(H) (called vertices). We say a r-graph H is (n, e)-unavoidable if every r-graph with n vertices and e edges must contain H. In this paper we investigate the largest possible number of edges in an (n, e)-unavoidable 3-graph for fixed n and e. We also study the structure of such unavoidable 3-graphs.     

A contact process with a semi-infected state on the complete graph

In this paper, we are concerned with a contact process with a semi-infected state on the complete graph C_n with n vertices. Our model is a special case of a general model introduced by Schinazi in 2003. In our model, each vertex is in one of three states, namely, “healthy,” “semi-infected,” or “fully-infected.” Only fully-infected vertices can infect others. A healthy vertex becomes semi-infected when being infected while a semi-infected vertex becomes fully-infected when being further infected. Each (semi- and fully-) infected vertex becomes healthy at constant rate. Our main result shows a phase transition for the waiting time until extinction of the fully-infected vertices. Conditioned on all the vertices are fully-infected when t = 0, we show that fully-infected vertices survive for exp?{O(n)} units of time when the infection rate λ > 4 while they die out in O(log?n) units of time when λ < 4.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

Vertex pancyclic in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001     

Counting Special Families of Labelled Trees

A labelled tree rooted at its least labelled vertex is Least-Child-Being-Monk if it has the property that the least labelled child of 0 is a leaf. One of our main results is that the number of Least-Child-Being-Monk trees labelled on {0, 1, 2,... ,n + 1} is equal to nⁿ. More generally, let be the set of labelled trees on {0,1,2,..., n + 1}, such that the total number of descendants of the least labelled child of 0 is p. We prove that the cardinality of is equal to Furthermore, a labelled tree rooted at its least labelled vertex is Hereditarily-Least-Single if it has the property that every least child in this tree is a leaf. Let the number of Hereditarily-Least-Single trees with n vertices be h_n. We find a functional equation for the generating function of h(n) and derive a recurrence that will quickly compute h(n). Received November 13, 2004     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

Tight Bounds for Connecting Sites Across Barriers

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines, it is known that there is a spanning tree such that every barrier is crossed by tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost. We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular, we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are the best possible. Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027. E. Rafalin’s research conducted while at Tufts University.     

On the existence of special depth first search trees

The Depth First Search (DFS) algorithm is one of the basic techniques that is used in a very large variety of graph algorithms. Most applications of the DFS involve the construction of a depth-first spanning tree (DFS tree). In this paper, we give a complete characterization of all the graphs in which every spanning tree is a DFS tree. These graphs are called Total-DFS-Graphs. We prove that Total-DFS-Graphs are closed under minors. It follows by the work of Robertson and Seymour on graph minors that there is a finite set of forbidden minors of these graphs and that there is a polynomial algorithm for their recognition. We also provide explicit characterizations of these graphs in terms of forbidden minors and forbidden topological minors. The complete characterization implies explicit linear algorithm for their recognition. In some problems the degree of some vertices in the DFS tree obtained in a certain run are crucial and therefore we also consider the following problem: Let G = (V,E) be a connected undirected graph where |V| = n and let d ? Nⁿ be a degree sequence upper bound vector. Is there any DFS tree T with degree sequence d _T that violates d (i.e., d _T ≤ d , which means: E j such that d _T(j) > d (j))? We show that this problem is NP-complete even for the case where we restrict the degree of only on specific vertex to be less than or equal to k for a fixed k ≥ 2 (i.e., d = (n - 1, ?, n - 1, k, n - 1, ?, n - 1)). 0 1995 John Wiley & Sons, Inc.     

Bipartite labeling of trees with maximum degree three

Let T = (V, E) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, |V|} for which there exists a k such that whenever φ(u) ≤ k < φ(v), then u and v have different colors. The α‐size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) − φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α‐size of trees with maximum degree three. Let α₃(n) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α₃(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5n/6. Using a computer search, we also establish that α₃(n) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Convex labelings of trees

A convex labeling of a tree T of order n is a one-to-one function f from the vertex set of T into the nonnegative integers, so that f(y) ? (f(x) + f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f(v) ? n ? 1 for every vertex v of T, then f is a perfect convex labeling and T is called a perfectly convex tree. Jamison introduced this concept and conjectured that every tree is perfectly convex. We show that there exists an infinite class of trees, none of which is perfectly convex, and in fact prove that for every n there exists a tree of order n which requires a convex labeling with maximum value at least 6n/5 – 22. We also prove that every tree of order n admits a convex labeling with maximum label no more than n²/8 + 2. In addition, we present some constructive methods for obtaining perfect convex labelings of large classes of trees.     

Self‐destructive percolation as a limit of forest‐fire models on regular rooted trees

Let T be a regular rooted tree. For every natural number n, let T_n be the finite subtree of vertices with graph distance at most n from the root. Consider the following forest‐fire model on T_n: Each vertex can be “vacant” or “occupied”. At time 0 all vertices are vacant. Then the process is governed by two opposing mechanisms: Vertices become occupied at rate 1, independently for all vertices. Independently thereof and independently for all vertices, “lightning” hits vertices at rate λ(n) > 0. When a vertex is hit by lightning, its occupied cluster becomes vacant instantaneously. Now suppose that λ(n) decays exponentially in n but much more slowly than 1/|T_n|, where |T_n| denotes the number of vertices of T_n. We show that then there exist such that between time 0 and time the forest‐fire model on T_n tends to the following process on T as n goes to infinity: At time 0 all vertices are vacant. Between time 0 and time τ vertices become occupied at rate 1, independently for all vertices. Immediately before time τ there are infinitely many infinite occupied clusters. At time τ all these clusters become vacant. Between time τ and time vertices again become occupied at rate 1, independently for all vertices. At time all occupied clusters are finite. This process is a dynamic version of self‐destructive percolation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 86–113, 2017     

Linear verification for spanning trees

Given a rooted tree with values associated with then vertices and a setA of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only $$5n + n\log \frac{{\left| A \right| + n}}{n}$$ comparisons. This leads to a spanning tree verification algorithm usingO(n+e) comparisons in a graph withn vertices ande edges. No implementation is offered.     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.