cp's OEIS Frontend

A385697 Number of unlabeled simple graphs on n vertices with no induced subgraphs isomorphic to a P5 or complement of a P5, where P5 = path on 5 vertices.

%I A385697 #8 Jul 22 2025 19:00:35
%S A385697 1,2,4,11,32,120,498,2425,13107,79002,526502,3918731,33238798,
%T A385697 334851298,4273597722
%N A385697 Number of unlabeled simple graphs on n vertices with no induced subgraphs isomorphic to a P5 or complement of a P5, where P5 = path on 5 vertices.
%C A385697 These numbers include both connected and disconnected graphs.
%o A385697 (Sage)
%o A385697 def has_induced_P5(g):
%o A385697     n = g.order()
%o A385697     if n < 5:
%o A385697         return False
%o A385697     from itertools import combinations
%o A385697     for vertices in combinations(range(n), 5):
%o A385697         subgraph = g.subgraph(vertices)
%o A385697         if subgraph.is_isomorphic(graphs.PathGraph(5)):
%o A385697             return True
%o A385697     return False
%o A385697 for n in range(3, 11):
%o A385697     count = 0
%o A385697     max_edges = n * (n - 1) // 2
%o A385697     for g in graphs.nauty_geng(f"{n}"):
%o A385697         edge_count = g.size()
%o A385697         if edge_count < max_edges / 2:
%o A385697             if not has_induced_P5(g) and not has_induced_P5(g.complement()):
%o A385697                 count += 2
%o A385697         elif edge_count == max_edges / 2:
%o A385697             if not has_induced_P5(g) and not has_induced_P5(g.complement()):
%o A385697                 count += 1
%o A385697     print(f"n = {n}: {count} graphs with no P5 in G or co-G")
%Y A385697 Cf. A000088.
%Y A385697 Euler transform of A079564.
%K A385697 nonn,more
%O A385697 1,2
%A A385697 _Jim Nastos_, Jul 07 2025
%E A385697 a(9)-a(15) from _Sean A. Irvine_, Jul 22 2025