[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Uniquely Tree-saturated Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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 \(D_{s,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; \(D_{s,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}\). 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

References

  1. Cooper, J., Lenz, J., LeSaulnier, T.D., Wenger, P.S., West, D.B.: Uniquely \(C_4\)-saturated graphs. Graphs Combin. 28(2), 189–197 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  2. Erdős, P., Hajnal, A., Moon, J.W.: A problem in graph theory. Am. Math. Mon. 71, 1107–1110 (1964)

    Article  Google Scholar 

  3. Erdős, 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)

    Google Scholar 

  4. Faudree, J.R., Faudree, R.J., Schmitt, J.R.: A survey of minimum saturated graphs. Electron. J. Combin. 18, 36 (2011)

    Google Scholar 

  5. Hartke, S.G., Stolee, D.: Uniquely \(K_r\)-saturated graphs. Electron. J. Combin. 19(4), 39 (2012). Paper 6

    MathSciNet  Google Scholar 

  6. Turán, P.: Eine extremalaufgabe aus der graphentheorie (Hungarian). Mat. Fiz. Lapok 48, 436–452 (1941)

    MathSciNet  Google Scholar 

  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)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Leah Wrenn Berman, Jill R. Faudree & John Gimbel

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

    Glenn G. Chappell & Chris Hartman

Authors
  1. Leah Wrenn Berman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Glenn G. Chappell
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jill R. Faudree
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. John Gimbel
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Chris Hartman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Leah Wrenn Berman.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Berman, L.W., Chappell, G.G., Faudree, J.R. et al. Uniquely Tree-saturated Graphs. Graphs and Combinatorics 32, 463–494 (2016). https://doi.org/10.1007/s00373-015-1589-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-015-1589-3

Keywords

Search

Navigation