Graphs and Combinatorics DOI 10.1007/s00373-015-1589-3 ORIGINAL PAPER

Uniquely Tree-saturated Graphs Leah Wrenn Berman1 · Glenn G. Chappell2 · Jill R. Faudree1 · John Gimbel1 · Chris Hartman2

Received: 27 June 2014 / Revised: 26 March 2015 © Springer Japan 2015

Abstract Let H be a graph. A graph G is uniquely H -saturated if G contains no subgraph isomorphic to H , but for every edge e in the complement of G (i.e., for each “nonedge” of G), G + e contains exactly one subgraph isomorphic to H . The double star Ds,t is the graph formed by beginning with K 2 and adding s + t new vertices, making s of these adjacent to one endpoint of the K 2 and the other t adjacent to the other endpoint; Ds,s is a balanced double star. Our main result is that the trees T for which there exist an infinite number of uniquely T -saturated graphs are precisely the balanced double stars. In addition we completely characterize uniquely tree-saturated graphs in the case where the tree is a star K 1,t = D0,t−1 . We show that if T is a double star, then there exists a nontrivial uniquely T -saturated graph. We conjecture that the converse holds; we verify this conjecture for all trees of order at most 6. We conclude by giving some open problems. Keywords

Graphs · Trees · Graph saturation · Uniquely saturated graphs

1 Introduction and Basic Definitions Graphs are finite and simple. Graphs are undirected, except where explicitly stated otherwise. Notation and terminology generally follows West [8].

B

Leah Wrenn Berman [email protected]

1

Department of Mathematics and Statistics, University of Alaska Fairbanks, Fairbanks, AK 99775-6660, USA

2

Department of Computer Science, University of Alaska Fairbanks, Fairbanks, AK 99775-6660, USA

123

Graphs and Combinatorics

(a)

Complete bipartite graphs are -saturated but not uniquely saturated.

(b)

Stars are uniquely

-saturated.

Fig. 1 A saturated graph versus a uniquely saturated graph; dashed edges indicate nonedges whose addition creates the copy of H (shown thick). a Complete bipartite graphs are -saturated but not uniquely saturated. b Stars are uniquely -saturated

A nonedge of a graph G is an unordered pair x y of distinct vertices of G such that x y is not an edge of G. Equivalently, a nonedge of G is an edge of G, the complement of G. Definition 1 Let H be a graph. A graph G is H -saturated if G has no subgraph isomorphic to H , and, for each nonedge e of G, the graph G + e has a subgraph isomorphic to H (Fig. 1a). If G is a complete graph whose order is less than that of H , then G is H -saturated. Such a G is said to be trivially H-saturated; other H -saturated graphs are nontrivial. We study the following sharpening of the notion of H -saturation (Figs. 1, 2). Definition 2 Let H be a graph. A graph G is uniquely H-saturated if G is H -saturated, and, in addition, for each nonedge e of G, the graph G + e has a unique subgraph isomorphic to H . If G is uniquely H -saturated, then we say that H uniquely saturates G. Once again, every complete graph with order less than that of H is uniquely H saturated. Such a graph is trivial; other graphs are nontrivial. A number of papers have been published concerning mimimum H -saturated graphs. A graph G on n vertices is minimum H -saturated if G is H -saturated and has the minimum number of edges among all H -saturated graphs of order n. For example, an early paper by Erd˝os et al. [2] found the minimum number of edges in a K r -saturated graph on n vertices and characterized all minimum K r -saturated graphs. There are a number of results concerning minimum T -saturated graphs where T is a tree. It is worth noting that there exist uniquely T -saturated graphs that are not minimum T -saturated graphs and vice versa. For example, the only uniquely K 1,5 saturated graph on 9 vertices is the disjoint union of K 5 and K 4 . However there exist K 1,5 -saturated graphs on 9 vertices with fewer edges; the disjoint union of a 4-regular graph on 6 vertices and K 3 would be such a graph. Figure 3 illustrates this situation. (See Faudree et al. [4] for a survey of minimum H -saturated graphs). Uniquely H -saturated graphs were introduced by Cooper et al. [1]. They showed that there are only a finite number of uniquely C4 -saturated graphs, and they identify all of them. Wenger [7, Thm. 6.4.3] proved similar results for uniquely C5 -saturated

123

Graphs and Combinatorics

(a) A uniquely C4 -saturated graph, adapted from Cooper, Lenz, LeSaulnier, Wenger, & West [CLLWW12].

(c) A uniquely P4 -saturated graph.

(b)

A uniquely D3,4 -saturated graph, where D3,4 is a double star with three rays on one side and four on the other.

(d) A uniquely saturated graph.

D0,4

=

K1,5 -

Fig. 2 Examples of uniquely H -saturated graphs. If the dashed edge is added, then a single copy of H can be found as a subgraph. a A uniquely C4 -saturated graph, adapted from Cooper et al. [1]. b A uniquely D3,4 -saturated graph, where D3,4 is a double star with three rays on one side and four on the other. c A uniquely P4 -saturated graph. d A uniquely D0,4 = K 1,5 -saturated graph

(a) A graph that is uniquely K1,5 saturated but not minimum K1,5 saturated.

A graph that is minimum K1,5 saturated but not uniquely K1,5 saturated, since joining the two magenta vertices completes two copies of K1,5 .

(b)

Fig. 3 Unique saturation and minimum saturation are distinct concepts. a A graph that is uniquely K 1,5 saturated but not minimum K 1,5 -saturated. b A graph that is minimum K 1,5 -saturated but not uniquely K 1,5 saturated, since joining the two magenta vertices completes two copies of K 1,5 (color figure online)

graphs. He also showed that there are no nontrivial uniquely H -saturated graphs for H equal to C6 , C7 , or any path on 5 or more vertices. Hartke and Stolee [5] studied uniquely K r -saturated graphs and found several new examples including two infinite families. We investigate uniquely T -saturated graphs G when T is a tree; such a graph G is a uniquely tree-saturated graph. We focus on the following questions.

123

Graphs and Combinatorics

(a) The double star D3,7 . This is not

(b)

The balanced double star D4,4 .

a balanced double star.

Fig. 4 Double stars. a The double star D3,7 . This is not a balanced double star. b The balanced double star D4,4

Question 1 For which trees T do there exist nontrivial uniquely T -saturated graphs? Question 2 For which trees T do there exist an infinite number of (pairwise nonisomorphic) uniquely T -saturated graphs? We believe we know the answers to both questions, and we have a proof for our answer to Question 2. Both answers involve trees we call “double stars”. Definition 3 Let s, t be nonnegative integers. The double star Ds,t is the graph formed by beginning with K 2 and adding s + t new vertices to the vertex set, making s of these adjacent to one endpoint of the K 2 and the other t adjacent to the other endpoint (see Fig. 4). We are particularly interested in the case when s = t. A double star of the form Ds,s is a balanced double star. See Fig. 4 for illustrations of double stars. Note that the double star D0,t is identical to the star K 1,t+1 . We denote a path on k vertices by Pk ; graph Pk thus has k − 1 edges. We conjecture that the trees T for which nontrivial uniquely T -saturated graphs exist (Question 1) are precisely the double stars. In Sect. 2 we investigate this, proving our conjecture for double stars. We also consider which trees T have the property that every uniquely T -saturated graph is a disjoint union of cliques, focusing on the case when T is a star. In Sect. 3 we exhibit classes of trees that do not uniquely saturate any nontrivial graph. We prove our answer to Question 1 for trees of order at most 6. In Sect. 4, we address Question 2. We show that the trees T for which an infinite number of uniquely T -saturated graphs exist are precisely the balanced double stars.

2 Trees T such that Nontrivial Uniquely T -Saturated Graphs Exist Now we look at Question 1. Here, we suspect we know the answer, but we do not have a proof. Conjecture 1 Let T be a tree. Then the following are equivalent.

123

Graphs and Combinatorics Fig. 5 A uniquely D3,4 -saturated graph

1. There exists a nontrivial uniquely T -saturated graph. 2. T is a double star. We can prove that (2) ⇒ (1) holds in the above conjecture (Proposition 1). We also address the question of which uniquely tree-saturated graphs are disjoint unions of cliques. We show (Theorem 2) that a large uniquely Ds,s -saturated graph must be a disjoint union of cliques. We also show (Proposition 2) that if a uniquely T -saturated graph G is a disjoint union of cliques, for some tree T , then T must be a double star (Fig. 5). We characterize the uniquely T -saturated graphs when T is a star (Proposition 3). Some of these graphs are not disjoint unions of cliques; we conjecture that this can only happen when T is a star with at least 5 leaves. Next we prove that (2) ⇒ (1) holds in Conjecture 1. Proposition 1 Let s, t be nonnegative integers. Then there exists a nontrivial uniquely Ds,t -saturated graph. Proof Let s, t be nonnegative integers. Let G be the disjoint union of K s+1 and K t+1 . Note that G is not a complete graph. We show that G is uniquely Ds,t -saturated. Without loss of generality, assume s ≤ t. Graph G contains no subgraph isomorphic to Ds,t , since Ds,t is a connected graph of order s + t + 2, while G has no component with more than t + 1 vertices. If we add any new edge to G, then this new edge has one endpoint in the K s+1 clique and one endpoint in the K t+1 clique. We can see that this results in a unique   subgraph isomorphic to Ds,t . The graphs in Proposition 1 are not the only graphs that are uniquely saturated by double stars. For example, as illustrated in Fig. 6, the balanced double star Ds,s uniquely saturates arbitrarily large graphs.

Fig. 6 A uniquely D3,3 -saturated graph can be formed by the disjoint union of an arbitrary number of copies of K 4

123

Graphs and Combinatorics

A uniquely K1,5 saturated graph that is a disjoint union of cliques.

(a)

A uniquely K1,5 -saturated graph that is not a disjoint union of cliques.

(b)

Fig. 7 Two uniquely K 1,5 -saturated graphs. a A uniquely K 1,5 -saturated graph that is a disjoint union of cliques. b A uniquely K 1,5 -saturated graph that is not a disjoint union of cliques Fig. 8 Two connected uniquely K 1,6 -saturated graphs

All of the uniquely saturated graphs mentioned so far have been disjoint unions of cliques. As we shall see in Proposition 4 (and Figs. 7b, 8), there do exist uniquely tree-saturated graphs that are not of this form. However, we can show that any uniquely Ds,s -saturated graph that is not a disjoint union of cliques must have low order. We will make use of the following result of Wenger [7] (see his Thm. 6.1.1 and the discussion preceding it), which characterizes the nontrivial uniquely Pk -saturated graphs, for all k ≥ 2. Theorem 1 (Wenger) Characterization of uniquely Pk -saturated graphs 1. The nontrivial uniquely P2 -saturated graphs are precisely the edgeless graphs of order 2 or more. 2. There is exactly one nontrivial uniquely P3 -saturated graph: the disjoint union of K 2 and K 1 . 3. The nontrivial uniquely P4 -saturated graphs are precisely the disjoint unions of 2 or more copies of K 2 . 4. If k ≥ 5, then there exists no nontrivial uniquely Pk -saturated graph. Now we can prove our result. Theorem 2 Let s ≥ 0, and let G be a uniquely Ds,s -saturated graph of order n. If n ≥ s 2 + 3s + 2, then G is a disjoint union of cliques.

123

Graphs and Combinatorics

Proof Let s, G, and n be as in the statement of the result. If s is 0 or 1, then Ds,s is P2 or P4 , respectively. These cases follow from Theorem 1. We assume therefore that s ≥ 2. Let Δ be the maximum degree of G. The remainder of our proof consists of two cases: Δ ≤ s and Δ ≥ s + 1. Case I Δ ≤ s. Assume for a contradiction that G is not a disjoint union of cliques. Then some component of G is not a clique. This component must be a uniquely Ds,s saturated graph. We may thus assume that G consists only of this component, and thus that G is a connected graph that is not complete. A new edge added to G must be the central edge in the copy of Ds,s that is created; otherwise G would already have had a vertex of degree greater than s. Therefore, for each nonedge x y of G, both x and y have degree exactly s in G. Furthermore, x and y can have no common neighbors in G; otherwise there would not be enough vertices among the neighbors of x and y to form a copy of Ds,s in G + x y. Now we can obtain a contradiction by letting x, y be nonadjacent vertices of G that lie at distance 2. These must exist, since G is connected but not complete, but such x, y have a common neighbor. Case II Δ ≥ s+1. We will show that this case is impossible, by proving a contradiction. Let x ∈ V (G) have degree Δ. We first show that Δ ≤ 2s + 1. Suppose for a contradiction that vertex x has degree at least 2s + 2. If the neighborhood of x forms a clique, then this clique contains multiple copies of Ds,s , which is impossible. Therefore x must have neighbors u, v such that uv is a nonedge of G. Adding nonedge uv to G forms a copy of Ds,s . One of the u and v (say u) must have degree at least s + 1 in this copy of Ds,s . Thus, in G + uv, vertex u has at least s neighbors other than x. Let A be a set of s such neighbors of u. We can now form multiple copies of Ds,s in G + uv, as follows. Let xu be the central edge of the tree. Let the elements of A be the other neighbors of u in the tree. Vertex x has at least s + 1 neighbors in G + uv other than u and the elements of A. We thus have multiple ways to choose the neighbors of x in the tree, contradicting G as uniquely T -saturated. Thus, Δ ≤ 2s + 1. Now let K be the set of all vertices y of G such that y is a nonneighbor of x and deg(y) ≥ s. Note that K may be empty. Observe that adding a new edge between any two vertices of degree less than s would not form a copy of Ds,s ; each such edge must already be in G. Hence the set of vertices of G that have degree less than s must form a clique, and so there can be at most s such vertices. Let r = Δ − s; so 1 ≤ r ≤ s + 1. Consider the vertices that do not lie in K . These consist of x, its Δ neighbors, and at most s other vertices of degree less than s, and we have |K | ≥ n − 1 − Δ − s = n − 1 − 2s − r.

123

Graphs and Combinatorics

For each vertex y ∈ K , vertex y must have at least r common neighbors with x; otherwise adding edge x y to G forms multiple copies of Ds,s . Thus the number of edges between N (x) and K is at least r |K |. By the Pigeonhole Principle, for some z ∈ N (x), the number of neighbors of z in K is at least r (n − 1 − 2s − r ) r |K | ≥ . |N (x)| s +r If the right-hand side above is at least s, then z has s or more neighbors in K , and so G contains a copy of T , giving the desired contradiction. Thus, it suffices to show r (n − 1 − 2s − r ) ≥ s. s +r By standard algebraic manipulation, noting that r and s are both positive, the above holds whenever s2 n≥ + 3s + r + 1. (1) r We wish to place an upper bound on the right-hand side of inequality (1) for r an integer with 1 ≤ r ≤ s + 1. Fixing s, differentiating the right-hand side with respect to r and setting the derivative to zero, we see that possible values of r that maximize the right-hand side are r = 1, s, s + 1. When r = 1, the right-hand side is s 2 + 3s + 2. When r = s, the right-hand side is 5s + 1, and when r = s + 1 the right-hand side is less than 5s + 2. The inequality s 2 + 3s + 2 ≥ 5s + 2 holds for each integer s ≥ 2. Thus, for all r , the right-hand side does not exceed s 2 + 3s + 2. Hence, by our assumption that n ≥ s 2 + 3s + 2, inequality (1) holds, and we have the desired contradiction.   Let G be a uniquely Ds,s -saturated graph of order n. By Theorem 2, if n ≥ s 2 + 3s + 2, then G is a disjoint union of cliques. Graph G is a also a disjoint union of cliques if n < 2s + 2, since then G is trivially uniquely Ds,s -saturated. Does there exist any uniquely Ds,s -saturated graph that is not a disjoint union of cliques? It seems likely that no such graph exists; however, we have not been able to find a proof. We do have a proof addressing the converse. If a tree T uniquely saturates a nontrivial disjoint union of cliques, then T must be a double star. Proposition 2 Let T be a tree, and let G be a nontrivial uniquely T -saturated graph. If G is a disjoint union of cliques, then T is a double star. If, in addition, G has two components with the same order, or has three or more components, then T is a balanced double star. Proof We first verify the following claim. Claim Let s, t be positive integers with s ≤ t. Suppose that the disjoint union of K s and K t is uniquely T -saturated, for some tree T . Then T is either Ds−1,t−1 or D0,t−1 . Proof of the Claim Suppose nonedge uv is added to the above disjoint union, with u ∈ K s and v ∈ K t . A single copy of T is created. Each permutation of the vertices

123

Graphs and Combinatorics

in K s − u is an automorphism of the graph that maps each of u, v to itself; such a permutation thus gives an automorphism of the created copy of T . Hence, in this copy of T , vertex u is either adjacent to every vertex in K s − u or to none of these vertices. Similarly, vertex v is either adjacent to every vertex in K t − v or to none of these vertices. It is immediate that T is a double star. If T is any graph other than Ds−1,t−1 or D0,t−1 , then the addition of uv creates more than one copy of T . Thus, the claim is proven. Now let T be a tree, and let G be a nontrivial uniquely T -saturated graph. Suppose that G is a disjoint union of cliques. Since G is nontrivial, it must have at least two components, the disjoint union of which is a uniquely T -saturated graph. By the claim, T is a double star. Suppose that, in addition, two components of G have the same order s. By the claim, T is either D0,s−1 or Ds−1,s−1 . If T is not Ds−1,s−1 , then the addition of a nonedge forms two copies of T . Thus T is a balanced double star. Lastly, suppose that G is a disjoint union of at least three cliques. Say that three components of G have orders r, s, t, respectively, with r ≤ s ≤ t. Applying the claim to the disjoint union of K r , K s , we see that T is either D0,s−1 or Dr −1,s−1 . Applying the claim to the disjoint union of K r , K t , we see that T is either D0,t−1 or Dr −1,t−1 , Thus s = t; that is, two components of G have the same order, and so, as shown above, T is a balanced double star.   The special case of Ds,t when t = 0 is of particular interest. Then the graph is question is a star: Ds,0 ∼ = K 1,s+1 . We can completely characterize the uniquely K 1,t saturated graphs, for t ≥ 2. Proposition 3 Let t ≥ 2, and let G be a graph. The following are equivalent. 1. Graph G is uniquely K 1,t -saturated. 2. The vertex set of G can be partitioned into (possibly empty) sets A, B, each inducing a complete subgraph of G, such that all of the following hold. – Each vertex in A has degree t − 1 in G. – Each vertex in B has degree less than t − 1 in G. – |A| ≤ t. – |B| ≤ t − 1. Proof Let t ≥ 2, and let G be a graph. (1) ⇒ (2) Suppose that G is uniquely K 1,t -saturated. If G is a complete graph, then G must have order at most t, since G contains no copy of K 1,t . If G has order exactly t, then let A be all of V (G), and let B be empty. If G has order less than t, then let A be empty, and let B be all of V (G). In both cases, the conditions of (1) are satisfied. Now assume that G is not a complete graph. Let x, y be nonadjacent vertices of G. Adding edge x y to G results in a copy of K 1,t . One of x, y (say x) is the center of this star. Thus, x has degree at least t − 1 in G. Since there is a unique copy of K 1,t in G + x y, in fact x has degree exactly t − 1 in G. Because t ≥ 2, vertex y is not the center of a K 1,t in G + x y. Thus y has degree less than t − 1 in G.

123

Graphs and Combinatorics

We see that each pair of nonadjacent vertices in G consists of one vertex of degree t − 1 and one vertex of degree at most t − 2. Thus, if there are two vertices of degree t − 1 in G, then these vertices must be adjacent. There are therefore at most t vertices of degree t − 1 in G. Similarly, if there are two vertices of degree at most t − 2 in G, then these vertices must be adjacent. There are therefore at most t − 1 vertices of degree t − 2 or less in G. Since G has no K 1,t subgraph, there can be no vertices of degree t or greater. We conclude that G consists of at most t vertices of degree t − 1 and at most t − 1 vertices of degree t − 2 or less. Let A be the set of all vertices of G with degree t − 1, and let B be the set of all vertices of G with degree less than t − 1. (2) ⇒ (1) Suppose that G, A, B are as in (2). Note that no vertex of G has degree greater than t − 1, and so G contains no copy of K 1,t . If G has order t or less and A contains at least one vertex, then A is the whole graph, and G is trivially K 1,t -saturated. On the other hand, if G has order t or less and A contains no vertices, then B is the whole graph, and, again, G is trivially K 1,t -saturated. Now suppose that G has order greater than t. Since no vertex of G has degree greater than t − 1, G is not a complete graph. Since each of A, B induces a complete subgraph, each nonedge of G must lie between a vertex of A and a vertex of B. Adding such a nonedge of G creates a single vertex of degree t (the endpoint in A) and thus a   single copy of K 1,t . Graph G is thus uniquely K 1,t -saturated. By Proposition 3, if G is a uniquely K 1,t -saturated graph, for t ≥ 2, then |V (G)| ≤ t + (t − 1) = 2t − 1. The next result follows immediately. Corollary 1 Let t ≥ 2. Then there exist only finitely many uniquely K 1,t -saturated graphs. In Sect. 4 we will extend the above result, proving that the trees T for which there exist infinitely many uniquely T -saturated graphs are precisely the balanced double stars. As noted previously, many uniquely tree-saturated graphs are disjoint unions of cliques. However, the characterization in Proposition 3 allows us to construct uniquely star-saturated graphs that are not of this form. Specifically, such examples can be constructed by choosing A = K t−1 , B = K 2 , and adding t − 1 edges between the two, one to each vertex of A. Proposition 4 Let t ≥ 5. Then there exists a uniquely K 1,t -saturated graph G such that G is not a disjoint union of cliques. We have not found any tree other than K 1,t with t ≥ 5 for which there exists a uniquely saturated graph that is not a disjoint union of cliques. We conjecture that no such such tree exists. Conjecture 2 Let T be a tree. Then the following are equivalent.

123

Graphs and Combinatorics

1. There exists a uniquely T -saturated graph that is not a disjoint union of cliques. 2. T is K 1,t for some t ≥ 5. The (2) ⇒ (1) direction of Conjecture 2 follows from Proposition 4. We have been unable to prove the other direction.

3 Trees that do not Uniquely Saturate any Nontrivial Graph In this section we address—but do not answer—the question of whether (1) ⇒ (2) holds in Conjecture 1; that is, we consider whether, for a tree T , the existence of a nontrivial uniquely T -saturated graph implies that T is a double star. We note that Wenger’s characterization of uniquely path-saturated graphs (Theorem 1) is consistent with our conjecture (Conjecture 1), as the paths that are double stars are precisely those for which Wenger found uniquely saturated graphs: P2 = D0,0 , P3 = D0,1 , and P4 = D1,1 . We can show that no nontrivial uniquely T -saturated graph exists if T is a tree of order 6 or less, and T is not a double star. Our proofs are based on the following lemmas, the first of which is a straightforward observation. Lemma 1 Let T be a tree, and let H be a graph containing two or more copies of T . Then, for each edge e of H , the graph H − e cannot be a subgraph of a uniquely T -saturated graph G. Lemma 2 Let T be a tree, and let G be a uniquely T -saturated graph. If there exist unordered pairs {x1 , x2 } and {y1 , y2 } of vertices of G, such that G +{x1 , x2 }+{y1 , y2 } contains two or more copies of T , then {x1 , x2 } and {y1 , y2 } are both nonedges of G. Proof We will proceed by contradiction. Let T, G, x1 , x2 , y1 , and y2 be as stated in the Lemma. Let e = {x1 , x2 } and f = {y1 , y2 }. Without loss of generality assume e is an edge of G. Since G contains no copies of T, f cannot be an edge of G. Now, by assumption, G + f contains at least two copies of T , contradicting G as uniquely T -saturated.   Lemma 3 Let T be a tree, and let G be a uniquely T -saturated graph. Then G does not contain two vertices of degree 1 lying at distance 2 from each other. Proof We will proceed by contradiction. Assume G has two vertices, x and y, of degree 1 with common neighbor z. Clearly T has order at least 3. Since G is T saturated, G + {x, y} contains a copy of T using edge x y and vertex z. But now G + {x, y} contains a copy of T using path zyx and another copy of T using path zx y, contradicting G as uniquely T -saturated.   The statements of Lemmas 1–3 actually hold under less restrictive conditions. Lemmas 1 and 2 continue to hold if T is not restricted to being a tree; T may be any graph. Lemma 3 holds whenever T is a triangle-free graph. However, we only apply the three lemmas when T is a tree, and so that is how we have stated them. Based on the above lemmas, we can verify Conjecture 1 for all trees of order 6 or less.

123

Graphs and Combinatorics

(a) Tree A.

(b) Tree B.

Fig. 9 The two trees of order at most 6 that are neither double stars nor paths. a Tree A. b Tree B

e

(a) P6 + e . . .

(b) . . . contains two copies of tree A.

Fig. 10 Illustration of the Proof of Proposition 5. Tree A does not uniquely saturate any nontrivial connected graph G whose maximum path has 6 or more vertices. a P6 + e …. b … contains two copies of tree A

Proposition 5 Let T be a tree of order 6 or less. Then there exists a nontrivial uniquely T -saturated graph if and only if T is a double star. Proof By Proposition 1 and Theorem 1 the desired result holds for double stars and paths, respectively. Of the 13 isomorphism classes of trees with order at least 2 and at most 6, exactly two are neither double stars nor paths; we will denote these trees by A and B, shown in Fig. 9. It suffices to show that there exist no nontrivial uniquely T -saturated graphs, for T = A, B. Suppose for a contradiction that G is a nontrivial uniquely T -saturated graph, for T ∈ {A, B}. Graph G cannot be a disjoint union of cliques, since then T would necessarily be a double star by Proposition 2. Thus, G has a component that is not a clique. This component is a nontrivial uniquely T -saturated graph, and so we may assume that the component is all of graph G, that is, that G is connected. For each of trees A, B, the proof that there is no connected graph G that is uniquely saturated by this tree will proceed by case analysis, based on the order of the maximum path in G. Tree A For tree A, we have four cases: the number of vertices in the maximum path P in G is at least 6, exactly 5, exactly 4, or exactly 3. G contains P6 —If G contains P6 , then there exists an edge e, shown in green in Fig. 10a, so that H = P6 + e contains two copies of tree A (Fig. 10b). Hence by Lemma 1, the path P6 is forbidden. The maximum path in G is P5 —If the maximum path P in G is P5 , then since tree A has 6 vertices, there must be another vertex v in G joined to a vertex of P. By the maximality of P, v cannot be adjacent to an endpoint of P, and since G cannot contain tree A itself, v cannot be adjacent to a penultimate vertex in P. Hence v must be adjacent to the middle vertex of P. Call this new graph J ; again, we can find an

123

Graphs and Combinatorics

e

(a) J + e . . .

(b) . . .

contains two copies of tree A.

Fig. 11 Illustration of the Proof of Proposition 5. Tree A does not uniquely saturate any nontrivial connected graph G whose maximum path is P5 . a J + e …. b … contains two copies of tree A

e

(a) J1 + e . . .

(b) . . .

contains two copies of tree A.

Fig. 12 Illustration of the Proof of Proposition 5. If the maximum path in G is P4 , then J1 has an edge e whose addition forms two copies of tree A. a J1 + e …. b … contains two copies of tree A

edge e (Fig. 11a) such that H = J + e contains two copies of P (Fig. 11), so by Lemma 1, J and hence P5 are forbidden. The maximum path in G is P4 —If the maximum path P in G is P4 , then since tree A has 6 vertices, there must be two other vertices in G. Let u, v be two such vertices whose distance from P is as small as possible; at least one of these (say v) is therefore adjacent to a vertex of P. By the maximality of P, neither u nor v can be adjacent to an endpoint of P. Since the maximum path in P is P4 , we cannot have u adjacent to v and v adjacent to some vertex in P, since that would create a P5 . Hence either u and v are each adjacent to different internal vertices in P (resulting in graph J1 ) or they are both adjacent to the same internal vertex of P (resulting in graph J2 . In each case, we find an edge e such that H = Ji + e contains two copies of P (Figs. 12, 13), so by Lemma 1, the Ji graphs, and hence P4 , are forbidden. The maximum path in G is P3 —If the maximum path in G is P3 , then G is either K 3 or a star. By inspection, neither of these is nontrivially uniquely saturated by tree A, and we have our contradiction when T is tree A. Tree B For tree B, we again have four cases: the number of vertices in the maximum path P in G is at least 6, exactly 5, exactly 4, or exactly 3. The arguments are similar to those for tree A, except in the case where the maximum path in G is a P5 , which requires a more involved argument.

123

Graphs and Combinatorics

e

(a) J2 + e . . .

(b) . . . contains two copies of tree A.

Fig. 13 Illustration of the Proof of Proposition 5. If the maximum path in G is P4 , then J2 has an edge e whose addition forms two copies of tree A. a J2 + e …. b … contains two copies of tree A

e

(a) P6 + e . . .

(b) . . .

contains two copies of tree B.

Fig. 14 Illustration of the Proof of Proposition 5. Tree B does not uniquely saturate any nontrivial connected graph G whose maximum path has 6 or more vertices. a P6 + e …. b … contains two copies of tree B

G contains a P6 —If G contains a P6 , then there exists an edge e, shown in green in Fig. 14a, so that H = P6 + e contains two copies of tree B (Fig. 14b). Hence by Lemma 1, the path P6 is forbidden. The maximum path in G is P5 —If the maximum path P in G is P5 , then since tree B has 6 vertices, there must be another vertex v in G joined to a vertex of P. By the maximality of P, v cannot be adjacent to an endpoint of P, and since G cannot contain tree B itself, v cannot be adjacent to the middle vertex of P. Hence v must be adjacent to a penultimate vertex of P, say x. Call this new graph J , and let w be the endpoint of P that is adjacent to x. In this case, we cannot find a single edge e for which two copies of tree B are found in J + e. However, there are two edges e and f , both shown in orange in Fig. 15b, so that J + e + f contains two copies of tree B; by Lemma 2 both edges must be excluded from G. Moreover, since the maximum order of a path in G is 5 in this case, we must exclude a number of other edges from G, shown in magenta in Fig. 15c; that is, all the magenta and orange edges must be nonedges of G. Notice in Fig. 15 that we are forced to exclude all possible neighbors of v and w, other than x, so that in G, vertices v and w are two degree-1 vertices that are distance two apart; therefore, by Lemma 3, J , and hence P5 , are forbidden subgraphs of G. The maximum path in G is P4 —As in the P4 case for tree A, the two addition vertices u and v are either each adjacent to different internal vertices in P or they are both adjacent to the same internal vertex of P, forming the same graphs J1 and

123

Graphs and Combinatorics

w x w e

v x

w

f

v

x v

J + e + f (f can also be the dashed edge).

(a)

(b) There are two copies of tree B, so edges e, f (the orange edges) are forbiddden.

w x

w x

v

(c) Any magenta edge with endpoint v or w—including to vertices outside J, shown in green—forms a prohibited P6 , so all magenta edges are prohibited.

v

(d) All edges incident with vertices v

and w are prohibited except those to x, so v and w are degree 1 vertices at distance 2 from each other; hence J is forbidden by Lemma 3.

Fig. 15 Illustration of the Proof of Proposition 5. Tree B does not uniquely saturate any nontrivial graph G whose maximum path is P5 . a J + e + f ( f can also be the dashed edge). b There are two copies of tree B, so edges e, f (the orange edges) are forbiddden. c Any magenta edge with endpoint v or w—including to vertices outside J , shown in green—forms a prohibited P6 , so all magenta edges are prohibited. d All edges incident with vertices v and w are prohibited except those to x, so v and w are degree 1 vertices at distance 2 from each other; hence J is forbidden by Lemma 3 (color figure online)

J2 . In each case, we find an edge e such that H = Ji + e contains two copies of B (Figs. 16, 17), so by Lemma 1, Ji , and hence P4 , are forbidden. The maximum path in G is P3 —Again, if the maximum path in G is P3 , then G is either K 3 or a star. By inspection, neither of these is nontrivially uniquely saturated by tree B, and we have our contradiction when T is tree B. This completes the proof.  

4 Trees that Uniquely Saturate an Infinite Number of Graphs We now consider Question 2, asking for which trees T there exist infinitely many uniquely T -saturated graphs. Here we have been able to verify our answer. This section will be largely devoted to proving the following result.

123

Graphs and Combinatorics

e

(a) J1 + e

(b) . . . contains two copies of tree B.

Fig. 16 Illustration of the Proof of Proposition 5. If the maximum path in G is P4 , then J1 has an edge e whose addition forms two copies of tree B. a J1 + e. b … contains two copies of tree B

e

(a)

J2 + e

(b) . . .

contains two copies of tree B.

Fig. 17 Illustration of the Proof of Proposition 5. If the maximum path in G is P4 , then J2 has an edge e whose addition forms two copies of tree B. a J2 + e. b … contains two copies of tree B

Theorem 3 Let T be a tree. Then the following are equivalent. 1. There exist infinitely many uniquely T -saturated graphs. 2. T is a balanced double star. We note that Theorem 3 is consistent with Corollary 1, as K 1,1 = K 2 = D0,0 is the only star that is a balanced double star. Theorem 3 is also consistent with Theorem 1, as P2 and P4 are the only paths that are balanced double stars. As with Conjecture 1, one direction of Theorem 3 is not hard to prove. Below, we show that (2) ⇒ (1) holds in Theorem 3. Proposition 6 Let s ≥ 0. Then there exist infinitely many uniquely Ds,s -saturated graphs. Proof Any disjoint union of copies of K s+1 is uniquely Ds,s -saturated.

 

For example, D3,3 uniquely saturates any graph consisting of disjoint copies of K 4 (see Fig. 6).

123

Graphs and Combinatorics

Most of the rest of this section will be devoted to proving (1) ⇒ (2) in Theorem 3. Our proof will proceed in a series of lemmas. We begin with a technical result (Lemma 4) Then we prove several structural lemmas. If adding some nonedge e to a graph G forms a copy of a tree T , then the copy of T consists of the new edge e along with two subtrees, each rooted at an endpoint of e. We will call such a rooted subtree a T -branch of G. We prove several lemmas concerning the structure of T -branches in a large uniquely T -saturated graph G. We show (Lemma 5) that if each T -branch of G is labeled, then any large G contains a large independent set such that adding any nonedge with both endpoints in the set results in a copy of T using two T -branches having the same label. We will be particularly interested in T -branches with the property that a copy of T can be formed using this T -branch, an edge, and another T -branch that is isomorphic to the first. Such a T -branch will be called a T /2-branch. Lemmas 8–12 concern the structure of T /2-branches in a large uniquely T -saturated graph. Lastly, we prove a result (Theorem 6) that directly implies that (1) ⇒ (2) holds in Theorem 3, thus completing our proof of that theorem. We prove our technical lemma next. Lemma 4 Let k, m ≥ 0, and let X 1 , . . . , X m and Y1 , . . . , Ym be sets of size at most k such that the following both hold. 1. For each i with 1 ≤ i ≤ m, we have X i ∩ Yi = ∅. 2. For each i, j with 1 ≤ i < j ≤ m, we have X i ∩ Y j = ∅. Then m ≤ 1 + k + k2 + · · · + kk . Proof The result is easily seen to hold when k = 0. If m = 0, then the conclusion holds. Therefore, suppose that k, m ≥ 1. Let sets X i and Yi be as in the statement of the result. Let Y = {Y1 , . . . , Ym }. Suppose for a contradiction that |Y| = m > 1 + k + k 2 + · · · + k k . We prove the following claim. m Yi Claim For each p = 0, . . . , k, there exist pairwise distinct y1 , . . . , y p ∈ i=0 and a subset Y p ⊆ Y with |Y p | > 1 + · · · + k k− p such that each of y1 , . . . , y p is contained in each element of Y p . Proof of the Claim We proceed by induction on p. Our base case is p = 0. No yi values need to be defined. Let Y0 = Y. Then the required statements hold for p = 0. Now suppose that 1 ≤ p ≤ k, and that y1 , . . . , y p−1 and Y p−1 are defined such that the required statements hold for p − 1. Let r be the smallest index such that Yr ∈ Y p−1 . Set X r meets Yi for each i > r ; in particular, X r meets each element of Y p−1 −{Yr }. Since |X r | ≤ k, there is y p ∈ X r that |Y

|−1

is contained in at least p−1 elements of Y p−1 − {Yr }. By the induction hypothesis k 2 there are more than 1 + k + k + · · · + k k−( p−1) elements in Y p−1 ; thus, y p must lie

123

Graphs and Combinatorics

in more than [1 + k + k 2 + · · · + k k−( p−1) ] − 1 = 1 + k + · · · + k k− p k sets (note that k − p ≥ 0, so the sum is well defined). Define Y p as follows. Y p = { Yi ∈ Y p−1 | y p ∈ Yi }. Then |Y p | > 1 + k + · · · + k k− p . Now y1 , . . . , y p−1 ∈ Yr , while y p ∈ X r , and X r ∩ Yr = ∅. Thus each of y1 , . . . , y p−1 must be distinct from y p . We see that y1 , . . . , y p and Y p satisfy the required statements for p. Thus, the claim is proven. Now apply the claim with p = k. We have pairwise distinct y1 , . . . , yk and a subset Yk ⊆ Y with |Yk | > 1, such that each of y1 , . . . , yk is contained in each element of Yk . Let Ya , Yb ∈ Yk , with a < b. We have {y1 , . . . , yk } ⊆ Ya , Yb . Since Ya , Yb both have cardinality at most k, we must have Ya = {y1 , . . . , yk } = Yb . But X a ∩ Ya = ∅, while X a ∩ Yb = ∅, a contradiction. By contradiction, our result is proven.   Now we begin working toward the Proof of Theorem 3. We will prove a series of lemmas giving properties that large uniquely T -saturated graphs must have, for T a tree. We start with some definitions related to the structure of uniquely tree-saturated graphs. Definition 4 A rooted tree is a tree H along with a distinguished vertex u of H , called the root. We say H is rooted at u. If such an H is a subgraph of a graph G, then H is a rooted subtree of G. Two rooted trees are isomorphic if they are isomorphic as graphs, and there is an isomorphism that takes the root of one to the root of the other. The class of a rooted tree is its equivalence class under isomorphism of rooted trees. If an edge uv is removed from a tree T , then what remains consists of two subtrees of T , rooted at u and v respectively. Each of these is a uv-branch of T . A branch of T is a uv-branch for some edge uv of T . Suppose that x y is a nonedge of a graph G, and adding edge x y to G results in the creation of a copy of T . This copy of T consists of the edge x y and two subtrees of G, one rooted at x and one rooted at y. Each of these rooted subtrees is a T -branch of G. Note that we only refer to a rooted subtree of G as a T -branch if it is part of a copy of T formed when adding to G a nonedge with one endpoint being the root of the subtree. Note also that if G is uniquely T -saturated, then the two corresponding T -branches are uniquely determined by the choice of nonedge x y. On the other hand, a single T branch in G may correspond to more than one nonedge of G. But each such nonedge must have the root of this T -branch in G as an endpoint.

123

Graphs and Combinatorics

u

(a) A tree T . . .

v

(b) . . . decomposes into two branches that are isomorphic as trees but not as rooted trees.

u

(c) A T -branch in a graph G. Fig. 18 Illustration of branches and T -branches. Particular nonedges whose addition creates a copy of the tree are shown dashed. a A tree T …. b …decomposes into two branches that are isomorphic as trees but not as rooted trees. c A T -branch in a graph G

See Fig. 18 for an illustration of a T -branch. Each T -branch in a graph G corresponds to at least one uv-branch in T , for some edge uv of T . This uv-branch is rooted at either u or v. Thus, the number of classes of T -branches in G is at most twice the number of edges of T , and we have the following observation. Observation 4 Let T be a tree of order k, and let G be a graph. Then there are at most 2(k − 1) classes of T -branches in G. In practice, Observation 4 will always overcount, as, for example, all 1-vertex rooted subtrees lie in the same class. Suppose that graph G is uniquely T -saturated, and suppose that each T -branch of G is labeled. We can form a labeling of the nonedges of G as follows. Given any nonedge x y of G, there exist corresponding T -branches C rooted at x and D rooted at y. Say C and D are given labels c, d, respectively; we assign the label {c, d} to nonedge x y. We similarly label each nonedge of G to obtain a branch labelling of G. Note that in a branch labelling each nonedge receives a unique label. Now we show that if a large uniquely T -saturated graph G is given a branch labeling, then there is some label q such that a large independent set in G has each nonedge labeled with {q, q}.

123

Graphs and Combinatorics

We will make use of the following result, attributed by Erd˝os and Moser [3] to Stearns; see Erd˝os and Moser [3, Sect. 1] for a proof. A tournament is an orientation of a complete graph. A tournament is transitive if it contains no directed cycles. Theorem 5 (Stearns) Let D be a tournament on n ≥ 1 vertices. Then there exists a subset W ⊆ V (D) such that W induces a transitive tournament, and |W | ≥ 1 + log2 n. We denote the set of positive integers by Z+ . We use R(· · · ) to denote a Ramsey number. For example, R(a, b, c) is the least n such that each edge 3-coloring of K n contains either an a-vertex clique in color 1, a b-vertex clique in color 2, or a c-vertex clique in color 3. Lemma 5 There exists a function f 1 : Z+ × Z+ × Z+ → Z+ such that the following holds. Let T be a tree of order k, and let G be a uniquely T -saturated graph. Suppose that the T -branches of G are labeled from some set of at most  labels, and G is accordingly branch-labeled. For each positive integer p and each set S ⊆ V (G) with |S| ≥ f 1 (k, , p), there exists a label q and an independent set P ⊆ S with |P| = p such that each nonedge with both endpoints in P is labeled {q, q}. Proof Define function f 1 as follows: ⎛

2 + 2

times

⎞

⎟ ⎜  ∗ ∗ ∗⎟ f 1 (k, , p) = R ⎜ p , p , . . . , p k, ⎠, ⎝

where 

k p ∗ = max p, 22(1+k+···+k )+1 . Now let T, k, G, , p, and S be as in the statement of the result. Note that G is branch-labeled. Suppose that |S| ≥ f 1 (k, , p). Edge-color the complete graph on V (G) as follows. Color each nonedge of G with its branch-label; note that the number of such labels (either {c, d} with c, d distinct,  2 or {c, c}) is 2 +  =  2+ . Color each edge of G with another color (“black”). By definition of f 1 , the subgraph of this complete graph induced by S contains either a k-clique of black edges or a monochromatic p ∗ -clique of edges in some branch-label color. The former possibility cannot happen, as a k-clique in G would contain a copy of T . Thus, there is P ⊆ S with |P| = p ∗ such that P is an independent set in G, and each nonedge between vertices in P is colored with the same branch-label {q, r }. It suffices to show that q = r ; then any collection of p vertices from P will form the required set. Suppose for a contradiction that q = r ; that is, for each x, y in P, the T -branch in G rooted at x and the T -branch in G rooted at y receive distinct labels.

123

Graphs and Combinatorics

Orient the complete graph on P as follows. Each edge is oriented from the root of the T -branch of G labeled q to the root of the T -branch of G labeled r ; since q, r are distinct this orientation is well-defined. This gives us a tournament. By Theorem 5, there is a set W ⊆ P inducing a transitive tournament with |W | = 1 + log2 |P| = 1 + log2 p ∗  ≥ 1 + 2(1 + k + · · · + k k ) + 1 = 2(1 + k + · · · + k k ) + 2. We may assume that |W | is even. If not, then remove one vertex from W ; since the above lower bound on |W | is even, it still holds. Label the vertices of W as w1 , w2 , . . . , w2m , so that each edge is oriented from a higher-numbered vertex to a lower-numbered vertex; such a labeling exists because the tournament is transitive. Note that m ≥ (1 + k + · · · + k k ) + 1. For i = 1, 2, . . . , m, edge w2i−1 w2i is a nonedge of G with two corresponding T -branches. Let X i be the vertex set of the T -branch of G labeled q rooted at w2i , and let Yi be the vertex set of the T -branch of G labeled r rooted at w2i−1 . We wish to apply Lemma 4. We show that k, the X i and Yi sets, and m satisfy the conditions of that lemma. First, note that since each T -branch is isomorphic to a rooted subtree of T , and T has k vertices, we have |X i | ≤ k and |Yi | ≤ k for each i. Second, for each i we have X i ∩ Yi = ∅, since sets X i , Yi together form the vertex set of a copy of T . Now let i, j be such that 1 ≤ i < j ≤ m, and consider X i and Y j . If these two sets are disjoint, then adding the edge w2i w2 j−1 to G results in a copy of T using edge w2i w2 j−1 , a T -branch labeled q rooted at w2i , and a T -branch labeled r rooted at w2 j−1 ; so edge w2i w2 j−1 would be oriented from w2i to w2 j−1 in W . But 2i < 2 j −1, and so the edge is actually oriented in the other direction. Thus X i ∩ Y j = ∅. We see that the conditions of Lemma 4 are satisfied. By that lemma, m ≤ 1 + k + k2 + · · · + kk , which contradicts our earlier lower bound on m. By contradiction, we have q = r , and the result is proven.

 

Lemma 6 Let T be a tree of order k, and let G be a uniquely T -saturated graph. For each vertex v of G, there are at most 2k k+1 T -branches of G rooted at v. Proof Let T, k, and G be as in the statement of the result. Let v be a vertex of G, and choose some class q of branches in T . Let the T -branches in class q rooted at v be numbered 1, . . . , m. Let X i be the vertex set of T -branch i, for i = 1, . . . m. Since there are at most 2(k − 1) classes (Observation 4), and

123

Graphs and Combinatorics

2(k − 1)(1 + k + k 2 + · · · + k k ) = 2k k+1 − 2 ≤ 2k k+1 , it suffices to show that m ≤ 1 + k + · · · + k k . For each i = 1, . . . , m, let wi be a nonneighbor of v in G such that adding nonedge vwi to G results in a copy of T using T -branch i rooted at v. Let Yi be the vertex set of the the T -branch rooted at wi in that copy of T . We wish to apply Lemma 4. We show that k, the sets X i and Yi , and m satisfy the conditions of that Lemma. Since each X i , Yi is the vertex set of a T -branch, we have |X i | ≤ k and |Yi | ≤ k. For each i, sets X i and Yi form the vertex set of a copy of T ; thus, X i ∩ Yi = ∅. Let i, j be such that 1 ≤ i < j ≤ m. If we add nonedge vw j to G, then a copy of T is formed, using T -branch j rooted at v. If X i and Y j are disjoint, then we also form a copy of T using T -branch i rooted at v. Since X i and X j are vertex sets of distinct T -branches, this would be a second copy of T . As that is impossible, we must have X i ∩ Y j = ∅. Thus the conditions of Lemma 4 are satisfied. By that lemma, m ≤ 1 + k + k2 + · · · + kk , which establishes our result.

 

The next few lemmas concern trees in which there exists an edge whose removal leaves two isomorphic branches. We define some relevant terminology. Definition 5 A uv-branch of tree T is a half-tree if the branches rooted at u and v are isomorphic as rooted trees; in this case we say the edge uv is central. A tree T is symmetric if it has a central edge. So T is symmetric if and only if T has an automorphism that exchanges the endpoints of some edge. We say T -branch of G is a T /2-branch if the corresponding branch of T is a halftree. (Note that, if one corresponding branch of T is a half-tree, then all corresponding branches are necessarily half-trees). Let G be a uniquely T -saturated graph. A nonedge uv of G is central if adding uv as a new edge of G results in a copy of T using two T /2-branches. See Fig. 19 for an illustration of a T /2-branch. Note that, for a fixed tree T , all T /2-branches (if any exist) lie in the same class. Note also that the double stars that are symmetric are precisely the balanced double stars. Lemma 7 There exists a function f 2 : Z+ × Z+ → Z+ such that the following holds. Let T be a tree of order k and let G be a uniquely T -saturated graph. Let p be a positive integer, and let S ⊆ V (G). If |S| ≥ f 2 (k, p), then there exists a subset P ⊆ S with |P| = p such that P is an independent set in G, and each nonedge between vertices of P is central. Proof Let f 1 be the function from Lemma 5. Define function f 2 as follows: f 2 (k, p) = f 1 (k, 2(k − 1), p) .

123

Graphs and Combinatorics

u

(a) A

v

half-tree in a symmetric tree T ; edge uv is central.

u

(b) A T /2-branch in a graph

G; the

dashed nonedge is central.

Fig. 19 Illustration of half-trees, symmetric trees, and T /2-branches. Particular nonedges whose addition creates a copy of the tree are shown dashed. a A half-tree in a symmetric tree T ; edge uv is central. b A T /2-branch in a graph G; the dashed nonedge is central

Now let T, k, G, p and S be as in the statement of the result. Label each T -branch of G according to its class. Then there are at most 2(k−1) different labels (Observation 4). Branch-label G accordingly. A direct application of Lemma 5 gives the result.   Next we prove five lemmas concerning the structure of T /2-branches in a large uniquely T -saturated graph G. These are (somewhat informally) as follows. – Lemma 8. At most a bounded number of vertices are not the root of a T /2-branch. – Lemma 9. A vertex with many nonneighbors is the root of at most one T /2-branch. – Lemma 10. At most a bounded number of vertices are not the root of exactly one T /2-branch. – Lemma 11. Each vertex is contained in at most a bounded number of T /2-branches. – Lemma 12. The set of all nonedges whose endpoints are roots of intersecting T /2-branches has a bounded vertex cover. Lemma 8 There exists a function f 3 : Z+ → Z+ such that the following holds. Let T be a tree of order k and let G be a uniquely T -saturated graph. Let S be the set of all v ∈ V (G) such that v is not the root of a T /2-branch [so if T is not symmetric, then S = V (G)]. Then |S| ≤ f 3 (k). Proof Let f 2 be the function from Lemma 7. Define function f 3 as follows: f 3 (k) = f 2 (k, 2). Now let T, k, G, and S be as in the statement of the result. Suppose for a contradiction that |S| > f 3 (G). Then |S| ≥ f 2 (k, 2). By Lemma 7 there exists an independent set P ⊆ S with |P| = 2, and each edge nonedge between vertices of P is central. Say P = {x, y}. Then x y is a central nonedge of G, and so x is the root of a T /2-branch. But x ∈ S, which contradicts the definition of S. By contradiction, the result is proven.  

123

Graphs and Combinatorics

The result below follows immediately from Lemma 8. Corollary 2 Let T be a tree of order k, and let f 3 be the function from Lemma 8. Then the following both hold. 1. Let G be a uniquely T -saturated graph. If T is not symmetric, then the order of G is at most f 3 (k). 2. If there exist infinitely many uniquely T -saturated graphs, then T is symmetric. Our eventual goal is to show that the only trees for which an infinite number of uniquely saturated graphs exist are the balanced double stars. The above corollary is a step in this direction, since every balanced double star is a symmetric tree. Lemma 9 There exists a function f 4 : Z+ → Z+ such that the following holds. Let T be a tree of order k, and let G be a uniquely T -saturated graph. The following are both true. 1. Let v be a vertex of G. If v has at least f 4 (k) nonneighbors in G, then there is at most one T /2-branch rooted at v. 2. Let P be an independent set in G. If |P| > f 4 (k), then no vertex in P is the root of more than one T /2-branch. Proof Let f 1 be the function from Lemma 5, and let f 2 be the function from Lemma 7. Define function f 4 as follows:   f 4 (k) = f 2 k, f 1 (k, 2k k+1 , 2k + 1) . Now let T, k, and G be as in the statement of the result. Proof of (1) Let v be a vertex of G, and let S be the set of nonneighbors of v in G. Suppose that |S| ≥ f 4 (k). Suppose for a contradiction that two distinct T /2-branches D and D are rooted at v. By Lemma 7 there exists an independent set P ⊆ S such that |P| = f 1 (k, 2k k+1 , 2k + 1), and each nonedge between vertices of P is central. For each vertex w ∈ P, let the T /2-branches rooted at w be numbered 1, 2, . . . . Label each T /2-branch whose root lies in P with the index of this T /2-branch in this numbering, and branch-label the nonedges of P accordingly. By Lemma 6, there are at most 2k k+1 different T -branch labels. Thus, by Lemma 5, there exists a label q and a set P ⊆ P such that |P | = 2k + 1, and each nonedge between vertices in P is labeled {q, q}. For each vertex x ∈ P , let C x be the T /2-branch with index q rooted at x. Then for each x, y ∈ P , the T -branches corresponding to nonedge x y are C x and C y . T -branches C x , C y are thus vertex-disjoint. Therefore, the 2k + 1 T -branches C x for x ∈ P are pairwise vertex-disjoint. Recall that D, D are distinct T /2-branches rooted at vertex v.

123

Graphs and Combinatorics

Since D is a T -branch, D has at most k vertices, and so at most k of the C x can contain any vertex of D. Thus at least k + 1 of the C x contain no vertex of D. Of those k + 1, at most k contain any vertex of D , as D also has at most k vertices. This leaves at least one vertex z ∈ P such that C z meets neither D nor D . Vertex z is a nonneighbor of v, since z ∈ P ⊆ P ⊆ S. Since C z , D, and D are all T /2-branches, adding edge vz to G results in two copies of T : one using edge vz and T -branches C z , D, and another using edge vz and T -branches C z , D . This contradicts the unique T -saturation of G. By contradiction, statement (1) is proven. Proof of (2) Let P be an independent set in G with |P| > f 4 (k). For each vertex x ∈ P, the other vertices in P form a set of at least f 4 (k) nonneighbors of x. By statement (1) there is at most one T /2-branch rooted at x.   The proof of the following lemma will make use of Turán’s Theorem [6]. Recall that this theorem states that, if an n-vertex graph has more than   1 n2 1− r 2 edges, then the graph must contain a clique of order r + 1. Lemma 10 There exists a function f 5 : Z+ → Z+ such that the following holds. Let T be a tree of order k and let G be a uniquely T -saturated graph. Let S be the set of all v ∈ V (G) such that the number of T /2-branches rooted at v is not exactly 1. Then |S| ≤ f 5 (k). Proof Let f 3 be the function from Lemma 8, and let f 4 be the function from Lemma 9. Define function f 5 as follows: f 5 (k) = f 3 (k) + k f 4 (k). Now let T, k, G, and S be as in the statement of the result. If k = 1, then T cannot be a symmetric tree; assume k ≥ 2. Suppose for a contradiction that |S| > f 5 (k). Let U be the set of all v ∈ V (G) such that v is not the root of a T /2-branch. Let W be the set of all v ∈ V (G) such that v is the root of more than one T /2-branch. Then S = U ∪ W . By Lemma 8, we have |U | ≤ f 3 (k), and so |W | > f 5 (k) − f 3 (k) = k f 4 (k). Thus, |W | > (k − 1) f 4 (k). Let w ∈ W . By Lemma 9, w has fewer than f 4 (k) nonneighbors in G; vertex w thus has fewer than f 4 (k) nonneighbors in W . Letting p be the number of neighbors of vertex w that lie in W , we have |W | − 1 − p < f 4 (k), and so |W | − p ≤ f 4 (k). Hence, |W | > (k − 1)(|W | − p). Solving for p, we have  p > 1−

 1 |W |, k−1

123

Graphs and Combinatorics

since k ≥ 2. Since vertex w was arbitrarily chosen, by the above lower bound the number of edges in the subgraph of G induced by W must be more than  1−

   |W | 1 1 (|W |)2 |W | · = 1− . k−1 2 k−1 2

By Turán’s Theorem [6], this subgraph contains a clique of order (k − 1) + 1 = k, and therefore G contains a clique of this order. But this is impossible, since such a clique would contain a copy of T . By contradiction, the result is proven.   Now we place an upper bound on the number of T /2-branches containing a vertex v of G. Note that v may lie in T -branches whose root is not v. Lemma 11 There exists a function f 6 : Z+ → Z+ such that the following holds. Let T be a tree of order k, and let G be a uniquely T -saturated graph. Then no vertex of G lies in more than f 6 (k) T /2-branches. Proof Let f 2 be the function from Lemma 7, and let f 4 be the function from Lemma 9. Define function f 6 as follows: f 6 (k) = 2k k+1 [1 + f 2 (k, max {2, f 4 (k) + 1})] − 1. Note that we have f 6 (k) > 0, for each positive integer k. Now let T, k, and G be as in the statement of the result. Let v be a vertex of G. Suppose for a contradiction that v lies in more than f 6 (k) T /2-branches. Let S be the set of all vertices, other than v, that are roots of T /2-branches containing v. By Lemma 6, at most 2k k+1 T -branches are rooted at v; similarly at most 2k k+1 T -branches are rooted at each of the vertices in S. By the definition of f 6 , we have |S + v| ≥ 1 + f 2 (k, max {2, f 4 (k) + 1}) . Hence, by Lemma 7 there exists an independent set P ⊆ S with |P| = max {2, f 4 (k) + 1} , such that each nonedge between vertices of P is central. Since |P| ≥ 2 there is a central nonedge x y with x, y ∈ P. Thus, there are T /2branches C rooted at x and D rooted at y such that C and D have no vertices in common. Next we will show that C and D do have a vertex in common; this will give us a contradiction. Since P is an independent set with |P| > f 4 (k), we may apply Lemma 9 to show that no vertex in P is the root of more than one T /2-branch. Thus C is the unique T /2-branch rooted at x, and D is the unique T /2-branch rooted at y.

123

Graphs and Combinatorics

Since P ⊆ S, each vertex in P is the root of a T /2-branch containing vertex v. Thus T -branches C and D have vertex v in common, and we have a contradiction. By contradiction, the result is proven.   Lemma 12 There exists a function f 7 : Z+ → Z+ such that the following holds. Let T be a tree of order k, and let G be a uniquely T -saturated graph. The following are both true. 1. Let M be a set of nonedges of G, no two of which share a vertex. If |M| > f 7 (k), then some nonedge x y in M has the property that no T /2-branch rooted at x shares a vertex with any T /2-branch rooted at y. 2. There exists a set S ⊆ V (G) with |S| ≤ 2 f 7 (k) such that, if x y is a nonedge of G and some T /2-branch rooted at x shares a vertex with some T /2-branch rooted at y, then one of x, y lies in S. Proof Let f 4 be the function from Lemma 9, and let f 6 be the function from Lemma 11. Define function f 7 as follows:   

f 7 (k) = 1 + 2k k+2 f 6 (k) max f 4 (k), k k+1 . Let T, k, and G be as in the statement of the result. Proof of (1) Let M be a set of nonedges of G, no two of which share a vertex. Suppose that |M| > f 7 (k). Suppose for a contradiction that for each nonedge in M, that there are two T /2branches, one rooted at each of the respective endpoints, and these two T /2-branches share a vertex in common. Note that a T /2-branch corresponds to a half-tree in T ; thus k must be even. Let us say that two distinct nonedges e1 , e2 ∈ M are related if there is a T /2-branch C rooted at an endpoint of e1 and a T /2-branch D rooted at an endpoint of e2 such that C, D have a vertex in common; otherwise e1 and e2 are unrelated. Let e ∈ M. Nonedge e has two endpoints. By Lemma 6 each of these two endpoints is the root of at most 2k k+1 T /2-branches. Each T /2-branch has k/2 vertices. And by Lemma 11 each of these vertices is contained in at most f 6 (k) T /2-branches, each of which has one root that is an endpoint of at most one nonedge in M. Thus, there are at most 2 · 2k k+1 ·

k · f 6 (k) = 2k k+2 f 6 (k) 2

nonedges f ∈ M − e that are related to e. Let M ⊆ M be a maximal set of pairwise unrelated elements of M. Since every element of M either lies in M or is related to some element of M , we have   |M | 1 + 2k k+2 f 6 (k) ≥ |M| > f 7 (k),

123

Graphs and Combinatorics

and so f 7 (k) 1 + 2k k+2 f 6 (k)

 = max f 4 (k), k k+1 .

|M | >

Now let a, b be distinct vertices, both of which are endpoints of elements of M . We claim that a, b are nonadjacent in G. If a, b are endpoints of the same element of M , then they are nonadjacent, since each element of M is a nonedge of G. If a, b are endpoints of distinct elements e1 , e2 , respectively, of M , then e1 and e2 are unrelated. Each of a, b is the root of a T /2-branch. By the unrelatedness of e1 , e2 , these two T -branches share no vertex in common. If a, b are adjacent, then the T /2-branches rooted at each, together with the edge between them, forms a copy of T in G, which is impossible. Thus, a, b are nonadjacent. We conclude that the vertex set of M forms an independent set in G. Since |M | > f 4 (k), by Lemma 9 each endpoint of each element of M has exactly one T /2-branch rooted at it. Label each T -branch of G according to its class, and branch-label G accordingly. Since there are at most k − 1 distinct nonedge labels, there is M

⊆ M such that each nonedge in M

has the same label, and |M | k−1 k k+1 > k−1 k k+1 − 1 > k−1 = 1 + k + · · · + kk .

|M

| ≥

Let m = |M

|, and write M

= {e1 , e2 , . . . , em }. Each ei is a nonedge of G. This nonedge cannot be central, as each endpoint of ei is the root of exactly one T /2branch, and so, by our assumption about M, these T /2-branches share a vertex in common. Thus each nonedge in M

is labeled {q, r }, where q, r are distinct classes of T -branches. The copy of T formed when some nonedge ei as added to G is made up of the edge ei , a T -branch in class q rooted at an endpoint u i of ei , and a T -branch in class r rooted at the other endpoint (say vi ) of ei . For each i, let X i be the vertex set of the T -branch in class q rooted at u i , and let Yi be the vertex set of the T -branch in class r rooted at vi . Now we have sets X 1 , . . . , X m and Y1 , . . . , Ym . We wish to apply Lemma 4. For each i = 1, . . . , m, we have X i ∩ Yi = ∅, since X i and Yi are part of the copy of T formed when nonedge ei is added to G. Now suppose 1 ≤ i < j ≤ m. Vertices u i , v j are endpoints of distinct elements of M

and thus of distinct elements of M . Thus u i v j is a nonedge of G, since

123

Graphs and Combinatorics

the vertex set of M forms an independent set. Each of u i , v j is the root of a T /2branch, and these T /2-branches have no vertex in common. Adding nonedge u i v j to G thus produces a copy of T using the new edge u i v j and these two T /2-branches; hence nonedge u i v j is central. If X i , Y j are disjoint, then there is a second copy of T formed when nonedge u i v j is added to G, using the new edge u i v j and the two T -branches of which X i , Y j are the vertex sets. Since this is impossible, we must have X i ∩ Y j = ∅. We see that the conditions of Lemma 4 are satisfied. By that lemma, |M

| = m ≤ 1 + k + k 2 + · · · + k k , which contradicts our earlier lower bound on |M

|. By contradiction, statement (1) is proven. Proof of (2) Let M be a collection of nonedges of G, no two of which share a vertex. Suppose that, for each x y ∈ M, some T /2-branch rooted at x shares a vertex with some T /2-branch rooted at y. Futhermore, suppose that M is maximal with respect to this property. By statement (1), we have |M| ≤ f 7 (k). Let S be the set of endpoints of elements of M. Then |S| ≤ 2 f 7 (k). Suppose for a contradiction that there is a nonedge x y of G such that some T /2-branch rooted at x shares a vertex with some T /2-branch rooted at y, but neither x nor y lies in S. Then we may add nonedge x y to M to create a larger collection, contradicting the maximality of M. By contradiction, S has the required property, and statement (2) is proven.   Now we can prove Theorem 3. Recall that this theorem states that, for a tree T , there exist infinitely many uniquely T -saturated graphs if and only if T is a balanced double star. One direction follows from Proposition 6. The other direction follows from our next result. Theorem 6 There exists a function f 8 : Z+ → Z+ such that the following holds. Let T be a tree of order k, and let G be a uniquely T -saturated graph. If G has order greater than f 8 (k), then there exists s ≥ 0 such that the following are both true. 1. Tree T is isomorphic to Ds,s . 2. Graph G is the disjoint union of copies of K s+1 . Proof Let f 5 be the function from Lemma 10, let f 6 be the function from Lemma 11, and let f 7 be the function from Lemma 12. Let s(k) =  k2  − 1. Define function f 8 as follows: f 8 (k) = max {[ f 5 (k) + 2 f 7 (k)] [1 + f 6 (k)], [ f 5 (k) + 2 f 7 (k)] + [s(k) + 2] f 6 (k)} . Let T, k, and G be as in the statement of the result. Suppose that the order of G is greater than f 8 (k). Let s = s(k). Note that, since G must be a nontrivial uniquely T -saturated graph, T has at least one edge. Thus k ≥ 2, and so s ≥ 0.

123

Graphs and Combinatorics

Proof of (1) We show that T ∼ = Ds,s . Let R be the set of all vertices v of G such that the number of T /2-branches rooted at v is not exactly 1. By Lemma 10, |R| ≤ f 5 (k). By Lemma 12 there is a set S ⊆ V (G) with |S| ≤ 2 f 7 (k) such that, if x y is a nonedge of G and some T /2-branch rooted at x shares a vertex with some T /2-branch rooted at y, then one of x, y lies in S. We will denote this set by S for the remainder of this proof. Let W = V (G)−(R ∪ S). Then for each w ∈ W , vertex w is the root of exactly one T /2-branch. And for each nonedge x y with both endpoints in W , the T /2-branches rooted at x, y share no vertices. Define an oriented graph G ∗ as follows. The vertex set of G ∗ is V (G). For x, y ∈ V (G) the arc x y is in G ∗ if y lies in some T /2-branch rooted at x. A T /2-branch contains s + 1 vertices. Each vertex in W thus has outdegree s in G ∗ . By Lemma 11, each vertex in G ∗ has indegree at most f 6 (k). The number of arcs in G ∗ having both endpoints in W is at least the number of arcs whose tail is in W minus the number of arcs whose head is not in W . This is at least |W | · s − |R ∪ S| · f 6 (k) ≥ |W | · s − [ f 5 (k) + 2 f 7 (k)] f 6 (k) ≥ |W | · s − [ f 8 (k) − ( f 5 + 2 f 7 )] > |W | · s − [|V | − |R ∪ S|] = |W | · s − |W | = |W | · (s − 1). So the number of arcs in G ∗ having both endpoints in W is greater than |W |·(s −1). Thus, some vertex in W has more than s − 1 inneighbors in W . Let a ∈ W be such a vertex, and let U be a set of inneighbors of a such that U ⊆ W and |U | = s. Each vertex in U ∪ {a} lies in W ; thus each such vertex is the root of a unique T /2-branch. Let x, y be distinct vertices in U ∪ {a}. The T /2-branches rooted at x, y share a vertex in common, namely a. If x, y are not adjacent in G, then at least one of x, y lies in S, by our choice of S. But S ∩ W = ∅, and so x, y are adjacent in G. The set U ∪ {a} thus induces a complete subgraph of G. We have |U ∪ {a}| = s + 1. Hence, by Lemma 11, there are at most (s + 1) f 6 (k) T /2-branches in G that contain one or more vertices of U ∪ {a}. Since |W | = |V (G)| − |R ∪ S| > f 8 (k) − [ f 5 (k) + 2 f 7 (k)] ≥ [s + 2] f 6 (k) > [s + 1] f 6 (k), there must be a vertex in W such that the (unique) T /2-branch rooted at this vertex does not contain any vertex in U ∪ {a}. Let b be such a vertex. Since b ∈ W , vertex b is the root of a unique T /2-branch. A T /2-branch is a rooted tree with s + 1 vertices. Each such rooted tree is a subgraph of K s+1 and thus can be found in the subgraph of G induced by U ∪ {a}. Therefore, if the edge ab lies in G,

123

Graphs and Combinatorics

then there is a copy of T using this edge, the T /2-branch rooted at b, and a rooted tree whose vertex set is U ∪ {a}. Thus a, b are not adjacent in G. Adding edge ab to G produces a copy of T as described above, and so U ∪ {a} must be the vertex set of the (unique) T /2-branch rooted at a. Now suppose for a contradiction that T is not Ds,s . Then a T /2-branch must include vertices that are not adjacent to the root via edges in the T /2-branch. It is not hard to see that at least two copies of such a rooted tree, both rooted at a, can be found in the clique U ∪ {a}. Then adding edge ab to G results in the creation of more than one copy of T , which is impossible. Thus, T ∼ = Ds,s , and statement (1) is proven. Proof of (2) We show that G is the disjoint union of copies of K s+1 . Recall that k ≥ 2 and s =  k2  − 1 ≥ 0. It is not hard (though perhaps a bit tedious) to show that f 8 (k) ≥ s 2 + 3s + 2. Since T ∼ = Ds,s , and G has order at least s 2 + 3s + 2, it follows from Theorem 2 that G is a disjoint union of cliques. If one of these cliques has order less than s + 1, then adding an edge to G with one endpoint in this clique, will not form a copy of Ds,s . If one of these cliques has order greater than s + 1, then adding an edge to G with one endpoint in this clique, will form multiple copies of Ds,s . Thus, G is a disjoint union   of copies of K s+1 , and statement (2) is proven. By Proposition 6 and Theorem 6, we conclude that our main result (Theorem 3) holds.

5 Open Problems Question 1 asked for which trees T there exist nontrivial uniquely T -saturated graphs. In Conjecture 1 we hypothesized that these are precisely the double stars. Conjecture 1 Let T be a tree. Then the following are equivalent. 1. There exists a nontrivial uniquely T -saturated graph. 2. T is a double star. We proved that (2) ⇒ (1) holds (see Proposition 1). The (1) ⇒ (2) direction remains open in general; it has been verified for paths (see Theorem 1) and trees of order at most 6 (see Proposition 5). Question 2 asked for which trees T there exist an infinite number of uniquely T saturated graphs. However this is not an open problem; Theorem 3 states that these trees are precisely the balanced double stars. It follows from Theorem 6 that for each tree T , all but a finite number of uniquely T -saturated graphs must be disjoint unions of cliques. Conjecture 2 concerned which trees uniquely saturate any graphs at all that are not disjoint unions of cliques. Conjecture 2 Let T be a tree. Then the following are equivalent. 1. There exists a uniquely T -saturated graph that is not a disjoint union of cliques. 2. T is K 1,t for some t ≥ 5.

123

Graphs and Combinatorics

Once again, we proved that (2) ⇒ (1) holds (see Proposition 4), while the (1) ⇒ (2) direction remains open. In each nontrivial uniquely H -saturated graph we know of—and here we do not require H to be a tree—adding a nonedge to the host graph results in a copy of H in which the added edge always plays the same role. More formally, for each graph H and each known nontrivial uniquely H -saturated graph G, there is a unique isomorphism class of edges in H such that the added edge lies in this class in the copy of H that is formed. This is trivially true of the uniquely saturated graphs found by Cooper et al. [1], by Wenger [7], and by Hartke and Stolee [5], as the graph “H ” in each of these papers is edge-transitive, and so there is only a single isomorphism class of edges in H . It is also true of all the uniquely tree-saturated graphs we have found. In particular, if H is the double star Ds,t , then H has a vertex u of degree s + 1 and a vertex v of degree t + 1, and u, v are adjacent. In all cases we have examined, adding a nonedge to a nontrivial uniquely H -saturated graph G results in a copy of H in which the added edge plays the role of uv in H . We ask whether this always holds. Question 3 Let H be a graph, and let G be a nontrivial uniquely H -saturated graph. Does there necessarily exist a single isomorphism class of edges in H such that adding a nonedge to G results in a copy of H in which the added edge lies in this class? Note that for different H -saturated graphs, nonedges may be from two different isomorphism classes of edges in H . For example, let H = K 4 − e, a graph with two isomorphism classes of edges. Let G 1 be a triangle plus a pendant vertex adjacent to one vertex of the triangle. Let G 2 be a 4-cycle. Then both G 1 and G 2 are nontrivial uniquely H -saturated graphs, but the nonedges of G 1 and G 2 are from different isomorphism classes of edges in H .

References 1. Cooper, J., Lenz, J., LeSaulnier, T.D., Wenger, P.S., West, D.B.: Uniquely C4 -saturated graphs. Graphs Combin. 28(2), 189–197 (2012) 2. Erd˝os, P., Hajnal, A., Moon, J.W.: A problem in graph theory. Am. Math. Mon. 71, 1107–1110 (1964) 3. Erd˝os, P., Moser, L.: On the representation of directed graphs as unions of orderings. Magy. Tud. Akad. Mat. Kut. Int. Közl. 9, 125–132 (1964) 4. Faudree, J.R., Faudree, R.J., Schmitt, J.R.: A survey of minimum saturated graphs. Electron. J. Combin. 18, 36 (2011) 5. Hartke, S.G., Stolee, D.: Uniquely K r -saturated graphs. Electron. J. Combin. 19(4), 39 (2012). Paper 6 6. Turán, P.: Eine extremalaufgabe aus der graphentheorie (Hungarian). Mat. Fiz. Lapok 48, 436–452 (1941) 7. Wenger, P.S.: Three existence problems in extremal graph theory, Ph.D. Thesis, University of Illinois (2010) 8. West, D.B.: Introduction to Graph Theory. Prentice Hall Inc, Upper Saddle River (1996)

123