login
Number of nodes after the n-th unfolding of a single vertex (see comments for definition).
0

%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