%I #45 Oct 19 2024 22:16:39
%S 1,2,5,12,59,1189
%N Number of nodes after the n-th unfolding of a single vertex (see comments for definition).
%C 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.
%H Max Brylski, <a href="https://github.com/helehex/unfolder">Python program</a>.
%e Unfolding G(1) to G(2):
%e Let the initial condition, G(1), be a single node. We'll call this node 'A'.
%e Because nodes contain implicit edges to themselves, the only walk here will be 'A' to 'A':
%e A
%e |
%e A
%e Relabel the nodes such that each (node, distance) pair will be unique:
%e A
%e |
%e B
%e This gives the next graph: G(2) = {A <-> B}.
%e The node count for G(2) is 2.
%e Unfolding G(2) to G(3):
%e List all walks through G(2) which start at 'A', and repeat exactly one node:
%e A A A
%e | \ \
%e A B B
%e | /
%e B A
%e Represent the walks as (node, distance) pairs:
%e (A,0) (A,0) (A,0)
%e | \ \
%e (A,1) (B,1) (B,1)
%e | /
%e (B,2) (A,2)
%e To simplify this representation, relabel each unique (node, distance) pair:
%e A A A
%e | \ \
%e B C C
%e | /
%e D E
%e Take the union of these walks to be a new undirected graph, G(3):
%e A
%e / \
%e B C
%e / \
%e D E
%e The node count for G(3) is 5.
%e Unfolding G(3) to G(4) gives 9 walks in the G(3) graph: AA, ABA, ABB, ACA, ACC, ACDC, ACDD, ACEC, ACEE.
%e 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.
%e --- A0
%e / / \
%e A1 B1 C1 ----
%e / \ / | \ \
%e B2 A2 D2 E2 C2
%e / \ / \
%e D3 C3 E3
%e Continue this pattern for G(5) and so on, to get node counts for each term in the sequence.
%K nonn,more,hard,walk
%O 1,2
%A _Max Brylski_, Sep 16 2024