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

On (\(\hbox {K}_t-e\))-Saturated Graphs

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

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Given a graph H, we say a graph G is H-saturated if G does not contain H as a subgraph and the addition of any edge \(e'\not \in E(G)\) results in H as a subgraph. In this paper, we construct \((K_4-e)\)-saturated graphs with |E(G)| either the size of a complete bipartite graph, a 3-partite graph, or in the interval \(\left[ 2n-4, \left\lfloor \frac{n}{2}\right\rfloor \left\lceil \frac{n}{2}\right\rceil -n+6\right] \). We then extend the \((K_4-e)\)-saturated graphs to \((K_t-e)\)-saturated graphs.

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

Similar content being viewed by others

References

  1. Amin, K., Faudree, J., Gould, R.J.: The edge spectrum of \(K_4\)-saturated graphs. Combin. Math Combin. Comput. 81, 233–242 (2012)

    MathSciNet  MATH  Google Scholar 

  2. Amin, K., Faudree, J., Gould, R.J., Sidorowicz, E.: On the non \((p-1)\)-partite \(K_p\)-free graphs. Discuss. Math. Graph Theory 33(1), 9–23 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Barefoot, C., Casey, K., Fisher, D., Fraughnaugh, K., Harary, F.: Size in maximal triangle-free graphs and minimal graphs of diameter 2. Discret. Math. 138, 93–99 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chartrand, G., Lesniak, L.: Graphs & Digraphs, 5th edn. Chapman & Hall/CRC, Boca Raton (2010)

    MATH  Google Scholar 

  5. Chen, G., Faudree, R.J., Gould, R.J.: Saturation numbers of books. Electron. J. Combin. 15(1), Research Paper 118, 12 (2008)

  6. Gould, R.J., Tang, W., Wei, E., Zhang, C.Q.: Edge spectrum of saturation numbers for small paths. Discret. Math. 312, 2682–2689 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the referees for their thorough reading and providing exceedingly helpful comments. The second author is supported by the Heilbrun Distinguished Emeritus Fellowship.

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Emory University, Atlanta, GA, USA

    Jessica Fuller & Ronald J. Gould

Authors
  1. Jessica Fuller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ronald J. Gould
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ronald J. Gould.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fuller, J., Gould, R.J. On (\(\hbox {K}_t-e\))-Saturated Graphs. Graphs and Combinatorics 34, 85–95 (2018). https://doi.org/10.1007/s00373-017-1857-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1857-5

Keywords

Search

Navigation