***************************************************************************** * 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: St001738 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- Description: The minimal order of a graph which is not an induced subgraph of the given graph. For example, the graph with two isolated vertices is not an induced subgraph of the complete graph on three vertices. By contrast, the minimal number of vertices of a graph which is not a subgraph of a graph is one plus the clique number [[St000097]]. ----------------------------------------------------------------------------- References: ----------------------------------------------------------------------------- Code: def statistic(G): for n in range(1, G.num_verts()+2): for H in graphs(n): if not G.subgraph_search(H, induced=True): return n ----------------------------------------------------------------------------- Statistic values: ([],0) => 1 ([],1) => 2 ([],2) => 2 ([(0,1)],2) => 2 ([],3) => 2 ([(1,2)],3) => 3 ([(0,2),(1,2)],3) => 3 ([(0,1),(0,2),(1,2)],3) => 2 ([],4) => 2 ([(2,3)],4) => 3 ([(1,3),(2,3)],4) => 3 ([(0,3),(1,3),(2,3)],4) => 3 ([(0,3),(1,2)],4) => 3 ([(0,3),(1,2),(2,3)],4) => 3 ([(1,2),(1,3),(2,3)],4) => 3 ([(0,3),(1,2),(1,3),(2,3)],4) => 3 ([(0,2),(0,3),(1,2),(1,3)],4) => 3 ([(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) => 2 ([],5) => 2 ([(3,4)],5) => 3 ([(2,4),(3,4)],5) => 3 ([(1,4),(2,4),(3,4)],5) => 3 ([(0,4),(1,4),(2,4),(3,4)],5) => 3 ([(1,4),(2,3)],5) => 3 ([(1,4),(2,3),(3,4)],5) => 3 ([(0,1),(2,4),(3,4)],5) => 3 ([(2,3),(2,4),(3,4)],5) => 3 ([(0,4),(1,4),(2,3),(3,4)],5) => 3 ([(1,4),(2,3),(2,4),(3,4)],5) => 4 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 4 ([(1,3),(1,4),(2,3),(2,4)],5) => 3 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 3 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 4 ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4 ([(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) => 3 ([(0,1),(2,3),(2,4),(3,4)],5) => 3 ([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 3 ([(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) => 3 ([(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) => 3 ([(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) => 3 ([(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) => 3 ([(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) => 2 ----------------------------------------------------------------------------- Created: Sep 13, 2021 at 11:13 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Sep 13, 2021 at 11:13 by Martin Rubey