- FindStat

edit this statistic or download as text // json

Identifier

St000778: Graphs ⟶ ℤ

Values

([],1) => 0

([],2) => 1

([(0,1)],2) => 1

([],3) => 2

([(1,2)],3) => 1

([(0,2),(1,2)],3) => 1

([(0,1),(0,2),(1,2)],3) => 2

([],4) => 3

([(2,3)],4) => 2

([(1,3),(2,3)],4) => 1

([(0,3),(1,3),(2,3)],4) => 2

([(0,3),(1,2)],4) => 2

([(0,3),(1,2),(2,3)],4) => 1

([(1,2),(1,3),(2,3)],4) => 2

([(0,3),(1,2),(1,3),(2,3)],4) => 2

([(0,2),(0,3),(1,2),(1,3)],4) => 2

([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 2

([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 3

([],5) => 4

([(3,4)],5) => 3

([(2,4),(3,4)],5) => 2

([(1,4),(2,4),(3,4)],5) => 2

([(0,4),(1,4),(2,4),(3,4)],5) => 3

([(1,4),(2,3)],5) => 2

([(1,4),(2,3),(3,4)],5) => 1

([(0,1),(2,4),(3,4)],5) => 2

([(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,4),(2,3),(3,4)],5) => 2

([(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(1,3),(1,4),(2,3),(2,4)],5) => 2

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 2

([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 3

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,3),(2,3),(2,4)],5) => 1

([(0,1),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 2

([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 2

([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 2

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 2

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([],6) => 5

([(4,5)],6) => 4

([(3,5),(4,5)],6) => 3

([(2,5),(3,5),(4,5)],6) => 3

([(1,5),(2,5),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 4

([(2,5),(3,4)],6) => 3

([(2,5),(3,4),(4,5)],6) => 2

([(1,2),(3,5),(4,5)],6) => 2

([(3,4),(3,5),(4,5)],6) => 4

([(1,5),(2,5),(3,4),(4,5)],6) => 2

([(0,1),(2,5),(3,5),(4,5)],6) => 3

([(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 3

([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,5),(2,4),(3,4)],6) => 2

([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 2

([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 2

([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3

([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 2

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4

([(0,5),(1,4),(2,3)],6) => 3

([(1,5),(2,4),(3,4),(3,5)],6) => 1

([(0,1),(2,5),(3,4),(4,5)],6) => 2

([(1,2),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 2

([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 2

([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 2

([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 2

([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 2

([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 2

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The metric dimension of a graph.
This is the length of the shortest vector of vertices, such that every vertex is uniquely determined by the vector of distances from these vertices.

References

[1] wikipedia:metric dimension

Code

def statistic(G):
    """
    precisely the paths have statistic 1
    sage: all(statistic(graphs.PathGraph(n))==1 for n in range(2,9))
    True
    sage: all(len([G for G in graphs(n) if G.is_connected() and statistic(G)==1])==1 for n in range(2,6))
    True

    precisely the complete graphs have statistic n-1
    sage: all(statistic(graphs.CompleteGraph(n))==n-1 for n in range(2,9))
    True
    sage: all(len([G for G in graphs(n) if G.is_connected() and statistic(G)==n-1])==1 for n in range(2,6))
    True

    complete bipartite graphs have statistic n-2
    sage: all(statistic(graphs.CompleteBipartiteGraph(m, n))==m+n-2 for m in range(2,5) for n in range(m,6))
    True
    """
    for d in range(G.num_verts()):
        for S in Subsets(G.vertices(), d):
            B = [tuple(G.distance(v, s) for s in S) for v in G.vertices()]
            if len(B) == len(set(B)):
                return d

Created

Apr 13, 2017 at 11:44 by Martin Rubey

Updated

Apr 13, 2017 at 11:44 by Martin Rubey