edit this statistic or download as text // json
Identifier
Values
([],1) => 0
([],2) => 0
([(0,1)],2) => 0
([],3) => 0
([(1,2)],3) => 0
([(0,2),(1,2)],3) => 0
([(0,1),(0,2),(1,2)],3) => 2
([],4) => 0
([(2,3)],4) => 0
([(1,3),(2,3)],4) => 0
([(0,3),(1,3),(2,3)],4) => 0
([(0,3),(1,2)],4) => 0
([(0,3),(1,2),(2,3)],4) => 0
([(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) => 0
([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 3
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 3
([],5) => 0
([(3,4)],5) => 0
([(2,4),(3,4)],5) => 0
([(1,4),(2,4),(3,4)],5) => 0
([(0,4),(1,4),(2,4),(3,4)],5) => 0
([(1,4),(2,3)],5) => 0
([(1,4),(2,3),(3,4)],5) => 0
([(0,1),(2,4),(3,4)],5) => 0
([(2,3),(2,4),(3,4)],5) => 2
([(0,4),(1,4),(2,3),(3,4)],5) => 0
([(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) => 0
([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 0
([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3
([(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) => 3
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 0
([(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) => 0
([(0,1),(2,3),(2,4),(3,4)],5) => 2
([(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) => 3
([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 0
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 3
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 4
([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 3
([(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) => 4
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 3
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 4
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4
([],6) => 0
([(4,5)],6) => 0
([(3,5),(4,5)],6) => 0
([(2,5),(3,5),(4,5)],6) => 0
([(1,5),(2,5),(3,5),(4,5)],6) => 0
([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0
([(2,5),(3,4)],6) => 0
([(2,5),(3,4),(4,5)],6) => 0
([(1,2),(3,5),(4,5)],6) => 0
([(3,4),(3,5),(4,5)],6) => 2
([(1,5),(2,5),(3,4),(4,5)],6) => 0
([(0,1),(2,5),(3,5),(4,5)],6) => 0
([(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 0
([(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) => 2
([(2,4),(2,5),(3,4),(3,5)],6) => 0
([(0,5),(1,5),(2,4),(3,4)],6) => 0
([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 0
([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 0
([(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) => 0
([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 0
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(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) => 0
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 0
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 0
([(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) => 3
([(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) => 0
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,4),(2,3)],6) => 0
([(1,5),(2,4),(3,4),(3,5)],6) => 0
([(0,1),(2,5),(3,4),(4,5)],6) => 0
([(1,2),(3,4),(3,5),(4,5)],6) => 2
([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 0
([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 2
([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(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) => 3
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3
([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 0
([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 0
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 0
>>> Load all 208 entries. <<<
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 2
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 0
([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 0
([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 2
([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 0
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 2
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 2
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 2
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 3
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 0
([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 3
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 0
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 4
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 0
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 4
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 3
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6) => 4
([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 2
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 3
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 4
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 4
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 4
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 4
([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5
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 length of a longest path in a graph such that after removing the paths edges, every vertex of the path has distance two from some other vertex of the path.
Put differently, for every vertex $v$ of such a path $P$, there is a vertex $w\in P$ and a vertex $u\not\in P$ such that $(v, u)$ and $(u, w)$ are edges.
The length of such a path is $0$ if the graph is a forest.
It is maximal, if and only if the graph is obtained from a graph $H$ with a Hamiltonian path by joining a new vertex to each of the vertices of $H$.
References
[1] user173856 Is every path with this property shorter than another path with the same endpoints? MathOverflow:319916
Code
def good_vertices(G, P):
    good = []
    U = set(G.vertices()).difference(P)
    todo = [v for v in P]
    while todo:
        v = todo.pop()
        for w in P:
            if w != v and any(G.has_edge(u, v) and G.has_edge(u, w) for u in U):
                good.append(v)
                if w in todo:
                    good.append(w)
                    todo.remove(w)
                break
    return set(good)

def statistic(G):
    lP = [P for u, v in Subsets(G, 2) for P in G.all_paths(u,v)]
    return max((len(P) for P in lP if len(good_vertices(G, P)) == len(P)), default=0)

Created
Feb 26, 2021 at 20:00 by Martin Rubey
Updated
Feb 28, 2021 at 16:17 by Martin Rubey