zbMATH — the first resource for mathematics

Extremal graphs with the given primitivity. (Russian) Zbl 0609.05058
Finite, non-oriented graphs without loops and multiple edges are considered. The primitivity f(G) of a graph G is such a maximal number k that there exists a skeleton in G with k pendant vertices. Let m(n,k) be the maximal number of edges in an n-vertex connected graph, the primitivity of which does not exceed k. Such a graph is called extremal, if its number of edges is equal m(n,k). In the case \(k=n-3\), all extremal graphs are described and a proof of the formula \(m(n,n-3)=(n^ 2- 5n+10)/2\) is given which differs from the proof of B. Zelinka [Casopis Pest. Mat. 98, 56-66 (1973; Zbl 0256.05116)].
Reviewer: J.Rosenknop
05C75 Structural characterization of families of graphs
05C30 Enumeration in graph theory