Uniquely Tree-saturated Graphs

Autor: Leah Wrenn Berman, Chris Hartman, Glenn G. Chappell, John Gimbel, Jill R. Faudree
Rok vydání: 2015
Předmět:
Zdroj: Graphs and Combinatorics. 32:463-494
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-015-1589-3
Popis: 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$$G+e contains exactly one subgraph isomorphic to H. The double star$$D_{s,t}$$Ds,t is the graph formed by beginning with $$K_2$$K2 and adding $$s+t$$s+t new vertices, making s of these adjacent to one endpoint of the $$K_2$$K2 and the other t adjacent to the other endpoint; $$D_{s,s}$$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} = D_{0, t-1}$$K1,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.
Databáze: OpenAIRE
Externí odkaz: