***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001690 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- 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) ----------------------------------------------------------------------------- Statistic 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 ([(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 ----------------------------------------------------------------------------- Created: Feb 26, 2021 at 20:00 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Feb 28, 2021 at 16:17 by Martin Rubey