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.

1, 2, 4, 11, 32, 120, 498, 2425, 13107, 79002, 526502, 3918731, 33238798, 334851298, 4273597722

Offset: 1

Author

Jim Nastos, Jul 07 2025

Keywords

• nonn
• more

Comments

These numbers include both connected and disconnected graphs.

Crossrefs

Cf. A000088.

Euler transform of A079564.

Programs

Sage

def has_induced_P5(g):
    n = g.order()
    if n < 5:
        return False
    from itertools import combinations
    for vertices in combinations(range(n), 5):
        subgraph = g.subgraph(vertices)
        if subgraph.is_isomorphic(graphs.PathGraph(5)):
            return True
    return False
for n in range(3, 11):
    count = 0
    max_edges = n * (n - 1) // 2
    for g in graphs.nauty_geng(f"{n}"):
        edge_count = g.size()
        if edge_count < max_edges / 2:
            if not has_induced_P5(g) and not has_induced_P5(g.complement()):
                count += 2
        elif edge_count == max_edges / 2:
            if not has_induced_P5(g) and not has_induced_P5(g.complement()):
                count += 1
    print(f"n = {n}: {count} graphs with no P5 in G or co-G")

Extensions

a(9)-a(15) from Sean A. Irvine, Jul 22 2025