Edge‐maximal (k, i)‐graphs
Hong‐Jian Lai, Cun‐Quan Zhang · Journal of Graph Theory · 1994
Abstract A graph G is a (k, l)‐graph if for any subgraph H of G, that |V(H)| ≧ implies that k(H) ≦ k − 1. An edge‐maximal (k, l‐graph G is one such that for any e ϵ E(Gc), G + e is not a (k, l)‐graph. In [F. T. Boesch and J. A. M. McHugh, „An Edge Extremal Result for Subcohesion,”︁ Journal of Combinatorial Theory B, vol. 38 (1985), pp. 1–7] a class of edge‐maximal graphs was found and used to show best possible upper bounds of the size of edge‐maximal (k, l)‐graphs. In this paper, we investigate the lower bounds of the size of edge‐maximal (k, l)‐graphs. Let f(n, k, l) denote the minimum size of edge‐maximal (k, l)‐graphs of order n. We shall give a characterization of edge‐maximal (k, l)‐graphs. This characterization is used to determine f(n, k, l) and to characterize the edge‐maximal (k, l)‐graphs with minimum sizes, for all n ≦ k + 2 ≦ 5. Thus prior results in [F.T. Boesch and J. A. M. McHugh, op. cit.; H.‐J. Lai, „The Size of Strength‐Maximal Graphs,”︁ Journal of Graph Theory, vol. 14 (1990), pp. 187–197] are extended.