Minimum K_2,3-saturated Graphs

Preprint English OPEN
Chen, Ya-Chen;
(2010)
  • Subject: Mathematics - Combinatorics | 05C35, 05C38

A graph is K_{2,3}-saturated if it has no subgraph isomorphic to K_{2,3}, but does contain a K_{2,3} after the addition of any new edge. We prove that the minimum number of edges in a K_{2,3}-saturated graph on n >= 5 vertices is sat(n, K_{2,3}) = 2n - 3.
  • References (21)
    21 references, page 1 of 3

    1. Y. Ashkenazi, C3 saturated graphs, Discrete Math. 297 (2005), 152-158.

    2. C. A. Barefoot; L. H. Clark; R. C. Entringer; T. D. Porter; L. A. Sz´ekely and Zs. Tuza, Cycle-saturated graphs of minimum size. Selected papers in honour of Paul Erd˝os on the occasion of his 80th birthday (Keszthely, 1993), Discrete Math. 150 (1996), 31-48.

    3. T. Bohman, M.Fonoberova, and O. Pikhurko, The saturation function of complete partite graphs, Journal of Combinatorics 1 (2010), 149-170.

    4. B. Bollob´as, On generalized graphs, Acta Math. Acad. Sci. Hungar 16 (1965), 447-452.

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

    6. Y. Chen, Minimum C5-saturated graphs, J. Graph Theory 61 (2009), 111-126.

    7. Y. Chen, All Minimum C5-saturated graphs, J. Graph Theory 67 (2011), 9-26.

    8. P. Erdo˝s, Z. Fu¨redi and Zs. Tuza, Saturated r-uniform hypergraphs, Discrete Math. 98 (1991), 95-104.

    9. P. Erdo˝s, A. Hajnal and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107-1110.

    10. J. Faudree, R. Faudree, and J. Schmitt, A Survey of Minimum Saturated Graphs, Electron. J. Comb. (2011), DS19, Dynamic Survey, 36 pp.

  • Metrics
    No metrics available
Share - Bookmark