# 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
##### MSC:
 05C75 Structural characterization of families of graphs 05C30 Enumeration in graph theory