OFFSET
1,2
COMMENTS
Given a rooted undirected graph G(n) where, the unfolding process produces a new rooted graph G(n+1). a(n) is the number of nodes in G(n). G(n+1) is obtained by taking the temporally sensitive union of all walks through a modified G(n) with self-loops at each node, which start at the root and terminate when a node is first visited for the second time.
LINKS
Max Brylski, Python program.
EXAMPLE
Unfolding G(1) to G(2):
Let the initial condition, G(1), be a single node. We'll call this node 'A'.
Because nodes contain implicit edges to themselves, the only walk here will be 'A' to 'A':
A
|
A
Relabel the nodes such that each (node, distance) pair will be unique:
A
|
B
This gives the next graph: G(2) = {A <-> B}.
The node count for G(2) is 2.
Unfolding G(2) to G(3):
List all walks through G(2) which start at 'A', and repeat exactly one node:
A A A
| \ \
A B B
| /
B A
Represent the walks as (node, distance) pairs:
(A,0) (A,0) (A,0)
| \ \
(A,1) (B,1) (B,1)
| /
(B,2) (A,2)
To simplify this representation, relabel each unique (node, distance) pair:
A A A
| \ \
B C C
| /
D E
Take the union of these walks to be a new undirected graph, G(3):
A
/ \
B C
/ \
D E
The node count for G(3) is 5.
Unfolding G(3) to G(4) gives 9 walks in the G(3) graph: AA, ABA, ABB, ACA, ACC, ACDC, ACDD, ACEC, ACEE.
Node A appears at distances 0,1,2; B at 1,2; C at 1,2,3; D at 2,3; E at 2,3. In total 12 nodes are created in G(4) and the edges are shown below. This is the first instance in which the graph is not a tree.
--- A0
/ / \
A1 B1 C1 ----
/ \ / | \ \
B2 A2 D2 E2 C2
/ \ / \
D3 C3 E3
Continue this pattern for G(5) and so on, to get node counts for each term in the sequence.
CROSSREFS
KEYWORD
nonn,more,hard,walk
AUTHOR
Max Brylski, Sep 16 2024
STATUS
approved