A135445 Number of connected graphs on n vertices such that any two distinct vertices that are connected by at least 2 distinct paths of length 2 are also connected by an edge.

1, 1, 2, 4, 10, 25, 76, 255, 1017, 4678

Offset

1,3

Comments

These graphs don't have the following induced subgraphs:

o-o o-o

| | |/|

o-o o-o

In other words, this sequence enumerates connected graphs that are fixed points of the transformation N_{2,2}, where N_{m,k} is a transformation of a simple graph G defined as follows: for all pairs of distinct vertices x,y in G, if k paths of length m exist between x and y then add an edge xy. (N is for "Near".) For example, N_{1,1}(G) = G for all G.

Links

Table of n, a(n) for n=1..10.

Example

n=1
    o
n=2
    o-o
n=3
    o-o-o    o-o
             |/
             o
n=4
    o-o-o-o    o-o-o    o-o-o    o-o
                 |      |/       |x|
                 o      o        o-o
n=5
    o-o-o-o-o    o-o-o-o    o-o-o-o    o-o-o    o-o-o-o
                   |        |/         |   |      |/
                   o        o          o___o      o
.
         o-o-o     o-o-o     o-o-o      o-o-o
          /|       |/|       |/         |x|     K_5
         o o       o o       o-o        o-o
.

Prog

(SageMath)
g1, g2 = graphs.CycleGraph(4), graphs.DiamondGraph()
def a(n): return len([g for g in graphs(n) if g.is_connected() and g.subgraph_search(g1, induced=True) is None and g.subgraph_search(g2, induced=True) is None]) # Andrei Zabolotskii, Jan 20 2026

Crossrefs

Cf. A079566, A079573.

Sequence in context: A124419 A148096 A006901 * A123422 A123413 A085633

Adjacent sequences: A135442 A135443 A135444 * A135446 A135447 A135448

Keyword

nonn,more

Author

Yasutoshi Kohmoto, Feb 18 2008

Extensions

Edited and terms a(6)-a(10) added by Andrei Zabolotskii, Jan 20 2026

Status

approved