A348600 - OEIS

%I #9 Jan 27 2022 21:00:42

%S 1,0,1,0,1,1,0,1,4,1,0,1,13,6,1,0,1,62,39,9,1,0,1,275,488,77,11,1,0,1,

%T 1710,8116,1145,130,14,1,0,1,12061,216432,29958,2415,196,16,1,0,1,

%U 93706,9512947,2026922,78265,4434,276,19,1

%N Triangle read by rows: T(n,k) is the number of (unlabeled) connected graphs with n nodes and metric dimension k, 0 <= k < n.

%H Gary Chartrand, Linda Eroh, Mark A. Johnson, and Ortrud R. Oellermann, <a href="https://doi.org/10.1016/S0166-218X(00)00198-0">Resolvability in graphs and the metric dimension of a graph</a>, Discrete Applied Mathematics 105 (2000), 99-113.

%H Richard C. Tillquist, Rafael M. Frongillo, and Manuel E. Lladser, <a href="https://arxiv.org/abs/2104.07201">Getting the lay of the land in discrete space: a survey of metric dimension and its applications</a>, arXiv:2104.07201 [math.CO], 2021.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Metric_dimension_(graph_theory)">Metric dimension</a>

%F T(n,1) = 1 for n >= 2, because the only graphs with metric dimension 1 are the paths of positive lengths (Chartrand et al. 2000).

%F T(n,n-2) = A047209(n-2) = floor(5*n/2-6) for n >= 3 (follows from the complete description of graphs with n nodes and metric dimension n-2 by Chartrand et al. 2000).

%F T(n,n-1) = 1 for n >= 1 , because the only graph with n nodes and metric dimension n-1 is the complete graph (Chartrand et al. 2000).

%e Triangle begins:

%e   n\k| 0  1     2       3       4     5    6   7  8  9

%e   ---+------------------------------------------------

%e    1 | 1

%e    2 | 0  1

%e    3 | 0  1     1

%e    4 | 0  1     4       1

%e    5 | 0  1    13       6       1

%e    6 | 0  1    62      39       9     1

%e    7 | 0  1   275     488      77    11    1

%e    8 | 0  1  1710    8116    1145   130   14   1

%e    9 | 0  1 12061  216432   29958  2415  196  16  1

%e   10 | 0  1 93706 9512947 2026922 78265 4434 276 19  1

%Y Cf. A047209, A303735.

%Y Row sums: A001349.

%K nonn,tabl

%O 1,9

%A _Pontus von Brömssen_, Jan 26 2022