A357815 - OEIS

%I #7 Nov 27 2022 11:20:19

%S 0,1,2,3,3,4,4,4,4,5,6,6,7,8,9,10,11,12,12,13,14,14,15,16,16,17,18,18,

%T 19,20,20,21,22,22,23,24,24,25,26,26,27,28,28,29,30,30,31,32,32,33,34,

%U 34,35,36,36,37,38,38,39,40

%N Smallest maximum degree over all maximal 2-degenerate graphs with diameter 2 and n vertices.

%C A maximal 2-degenerate graph can be constructed from a 2-clique by iteratively adding a new 2-leaf (vertex of degree 2) adjacent to two existing vertices.

%C Examples of sharpness for all n are given in the Bickle 2021 paper.

%C The smallest maximum degree over all 2-trees with diameter 2 and n vertices is ceiling(2/3*n).

%H Allan Bickle, <a href="https://allanbickle.files.wordpress.com/2016/05/kpathpaper.pdf">k-Paths of k-Trees</a>, Springer PROMS 388 (2020) 287-291.

%H Allan Bickle, <a href="https://allanbickle.files.wordpress.com/2016/05/degeneratediam2-2.pdf">Wiener indices of maximal k-degenerate graphs</a>, International Journal of Mathematical Combinatorics 2 (2021) 68-79.

%H Allan Bickle and Zhongyuan Che, <a href="https://arxiv.org/abs/1908.09202">Wiener indices of maximal k-degenerate graphs</a>, arXiv:1908.09202 [math.CO], 2019.

%F a(n) = ceiling(2/3*(n-1)) for n>15.

%e For n=5, the graph formed by subdividing one edge of a 4-clique is maximal 2-degenerate with diameter 2, and has maximum degree 3. Thus a(5) = 3.

%Y Cf. A004523.

%K nonn

%O 1,3

%A _Allan Bickle_, Oct 13 2022