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

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, 1710, 8116, 1145, 130, 14, 1, 0, 1, 12061, 216432, 29958, 2415, 196, 16, 1, 0, 1, 93706, 9512947, 2026922, 78265, 4434, 276, 19, 1

Offset

1,9

Links

Table of n, a(n) for n=1..55.

Gary Chartrand, Linda Eroh, Mark A. Johnson, and Ortrud R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics 105 (2000), 99-113.

Richard C. Tillquist, Rafael M. Frongillo, and Manuel E. Lladser, Getting the lay of the land in discrete space: a survey of metric dimension and its applications, arXiv:2104.07201 [math.CO], 2021.

Wikipedia, Metric dimension

Formula

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).

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).

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).

Example

Triangle begins:
  n\k| 0  1     2       3       4     5    6   7  8  9
  ---+------------------------------------------------
   1 | 1
   2 | 0  1
   3 | 0  1     1
   4 | 0  1     4       1
   5 | 0  1    13       6       1
   6 | 0  1    62      39       9     1
   7 | 0  1   275     488      77    11    1
   8 | 0  1  1710    8116    1145   130   14   1
   9 | 0  1 12061  216432   29958  2415  196  16  1
  10 | 0  1 93706 9512947 2026922 78265 4434 276 19  1

Crossrefs

Cf. A047209, A303735.

Row sums: A001349.

Sequence in context: A369971 A362868 A055105 * A200545 A294522 A058710

Adjacent sequences: A348597 A348598 A348599 * A348601 A348602 A348603

Keyword

nonn,tabl

Author

Pontus von Brömssen, Jan 26 2022

Status

approved