Frogs jumping on trees
The frog game on a Tree:
- Default start of the game is placing one frog on each node (vertex).
- The goal is to move all the frogs to one single node.
- A single move consists of moving all $n$ frogs from node $A$ to nonempty node $B$, which is allowed only if there exists a path from $A$ to $B$ containing exactly $n$ unique edges. Node $B$ is called nonempty if there is at least one frog on it.
- If it is possible for all frogs to end up on some node $N$ (the game is solvable at N), then that implies that the frog on node $N$ never moves during the game, hence that node will be called a lazy toad.
Question: How can one characterize lazy and non-lazy toad nodes within trees?
Spliting trees into sets and characterizing lazy toads within those sets
I was initially observing tree sets based on leafs, but Bob Krueger suggested in the comments that it's better to look at branching nodes instead. Indeed, this is a better way to look at the trees.
A branching node is a node of degree at least $3$.
I decided to observe $b$ branching node tree cases - sets of trees with $b$ branching nodes.
They are further split into sets $[m_1,m_2,dots,m_b]=$ a set of all trees whose branching nodes $b_1,b_2,dots,b_b$ have degrees $m_1,m_2,dots,m_b$.
$0$ Branching nodes case
This case is basically the Frog Jumping game showed on Numberphile.
Tree with $n$ nodes that is categorized under this case always looks like a simple chain:
1-2-3-...-(n-2)-(n-1)-n
This case was already fully solved at the linked video. I will formalize the proof below:
Theorem. All trees that have no branching nodes are always fully lazy (All
nodes are lazy toads).
Proof.
$(1)$ Given tree with $n$ nodes labeled as "$1-2-3-...-n$", it is always solvable at nodes $1$ and $n$ :
If $n$ is odd, start at middle node $frac{n+1}{2}$. Then by repeated jumping "left-right" we end up with all frogs at node $n$. Symmetrically, repeated "right-left" jumps will solve the game at node $1$.
If $n$ is even, we can start at $frac{n}{2}$ and by repeating "right-left" solve the game at $n$. Again, symmetrically, starting at $frac{n}{2}+1$ and repeating "left-right", solve the game at $1$.
If we can always solve the tree at leaf nodes ($1$ and $n$), then we can solve it at any node:
- Simply split the tree into two parts: "$1-2-dots-k$" and "$k-(k+1)-dots-n$". Now solve both parts at $k$ as explained in $(1).implies$ tree is solvable at node $k$, where $k$ is any node.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases
This case can be split into sub-cases $[m]$, where $[m]$ stands for the set of all trees with one branching node of degree $mge3$. Those trees will have at least $n=m+1$ nodes.
The $[n-1]$ tree set
If $m$ is not constant but set to $m=n-1$, where $n$ is the number of the nodes of the tree, then this set of trees is trivial. All of them look like a "sun" or "flower head"; Label nodes from $0$ to $n+1=m$, and let node $0$ be the node of degree $m$.
3 2 1
| /
4 - 0 - m
/ |
5 ... m-1
Theorem. All trees in this set have exactly one lazy toad node, node $0$.
Proof.
To show that $0$ is lazy is trivial: For every other node, move its frogs to node $0$.
To show that the leafs are not lazy toad nodes (nodes $1dots m$):
The longest path in these trees is always $2$, which means you can't have more than $2$ frogs on any node other than the leaf node you are trying to solve the game at. This implies all other leafs must reach target leaf $k_0$ with at most $2$ frogs (since that's already their distance to it as well, it must be exactly $2$ frogs).
The only node that can supplement leaf nodes with frogs up to $2$ frogs is node $0$. After using node $0$ to bring leaf $k_1$ frogs to target leaf $k_0$, all other leafs will have no moves to bring their frogs to $k_0.implies$ game is not solvable at leaf $k_0$, regardless of leaf choices for $k_0,k_1$ as everything is symmetric.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases without [n-1] trees = The $[m]_0$ tree sets
Lets exclude examples from $[n-1]$ set, from sets $[m]$; Let $[m]_0$ be a set of all trees with one branching node of degree $mge3$, that have at least $m+2$ nodes.
For $m=3$:
Theorem. Trees in $[3]_0$ are all fully lazy for $nge9$. They are also fully lazy for $nlt9$ except for these $4$ examples with exactly one non-lazy toad node (colored in red) shown here:
For $m=4$:
Theorem. Trees in $[4]_0$ are all fully lazy for $nge15$. They are also fully lazy for $nlt15$ except for a finite set of examples which are sorted below:
$1$ non-lazy toad examples, $2$ non-lazy toads examples, $3$ non-lazy toads examples, $5$ non-lazy toads example, $6$ non-lazy toads examples.
For $mge5$:
Conjecture. Trees in $[m]_0$ are all fully lazy for $nge n_m$. They are also fully lazy for $nlt n_m$ except for a finite set of
examples with varying number of non-lazy toad nodes.
I believe one can compute solutions for enough examples to guess $n_m$ for some $[m]_0$ set and then prove it with help of an algorithm by reconstructing the solvability of nodes. The examples for $nlt n_m$ can be computed as there should be finitely many of them.
But solving each $m$ individually with mainly relying on a computation, won't solve this problem for all $[m]_0$ sets. A characterizations of these trees is needed that will help mathematically prove the laziness of nodes of these trees.
Question: Any ideas how to reach such characterization(s)?
$bge2$ Branching nodes cases
Each of these cases can be further split into sets $[m_1,m_2,dots,m_b]=$ set of all trees with $b$ branching nodes that have degrees $m_1,m_2,dots,m_b$.
Each of those sets should have their $n_{(m_1,m_2,dots,m_b)}$ such that all trees with $nge n_{(m_1,m_2,dots,m_b)}$ nodes are fully lazy, where set of trees with $nlt n_{(m_1,m_2,dots,m_b)}$ nodes will have a finite number of examples with varying number of non-lazy toad nodes.
Question: Any ideas how to effectively find $n_{(m_1,m_2,dots,m_b)}$?
For example, for $b=1$, I conjecture that it is enough to observe this type of trees:
3 2 1
| /
4 - 0 - m - m+1 - m+2 - m+3 - ... - m+k-1 - m+k
/ |
5 ... m-1
And by finding $k_0$ such that all those trees are fully lazy for all $kge k_0$, we get $n_m$.
graph-theory recreational-mathematics trees
add a comment |
The frog game on a Tree:
- Default start of the game is placing one frog on each node (vertex).
- The goal is to move all the frogs to one single node.
- A single move consists of moving all $n$ frogs from node $A$ to nonempty node $B$, which is allowed only if there exists a path from $A$ to $B$ containing exactly $n$ unique edges. Node $B$ is called nonempty if there is at least one frog on it.
- If it is possible for all frogs to end up on some node $N$ (the game is solvable at N), then that implies that the frog on node $N$ never moves during the game, hence that node will be called a lazy toad.
Question: How can one characterize lazy and non-lazy toad nodes within trees?
Spliting trees into sets and characterizing lazy toads within those sets
I was initially observing tree sets based on leafs, but Bob Krueger suggested in the comments that it's better to look at branching nodes instead. Indeed, this is a better way to look at the trees.
A branching node is a node of degree at least $3$.
I decided to observe $b$ branching node tree cases - sets of trees with $b$ branching nodes.
They are further split into sets $[m_1,m_2,dots,m_b]=$ a set of all trees whose branching nodes $b_1,b_2,dots,b_b$ have degrees $m_1,m_2,dots,m_b$.
$0$ Branching nodes case
This case is basically the Frog Jumping game showed on Numberphile.
Tree with $n$ nodes that is categorized under this case always looks like a simple chain:
1-2-3-...-(n-2)-(n-1)-n
This case was already fully solved at the linked video. I will formalize the proof below:
Theorem. All trees that have no branching nodes are always fully lazy (All
nodes are lazy toads).
Proof.
$(1)$ Given tree with $n$ nodes labeled as "$1-2-3-...-n$", it is always solvable at nodes $1$ and $n$ :
If $n$ is odd, start at middle node $frac{n+1}{2}$. Then by repeated jumping "left-right" we end up with all frogs at node $n$. Symmetrically, repeated "right-left" jumps will solve the game at node $1$.
If $n$ is even, we can start at $frac{n}{2}$ and by repeating "right-left" solve the game at $n$. Again, symmetrically, starting at $frac{n}{2}+1$ and repeating "left-right", solve the game at $1$.
If we can always solve the tree at leaf nodes ($1$ and $n$), then we can solve it at any node:
- Simply split the tree into two parts: "$1-2-dots-k$" and "$k-(k+1)-dots-n$". Now solve both parts at $k$ as explained in $(1).implies$ tree is solvable at node $k$, where $k$ is any node.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases
This case can be split into sub-cases $[m]$, where $[m]$ stands for the set of all trees with one branching node of degree $mge3$. Those trees will have at least $n=m+1$ nodes.
The $[n-1]$ tree set
If $m$ is not constant but set to $m=n-1$, where $n$ is the number of the nodes of the tree, then this set of trees is trivial. All of them look like a "sun" or "flower head"; Label nodes from $0$ to $n+1=m$, and let node $0$ be the node of degree $m$.
3 2 1
| /
4 - 0 - m
/ |
5 ... m-1
Theorem. All trees in this set have exactly one lazy toad node, node $0$.
Proof.
To show that $0$ is lazy is trivial: For every other node, move its frogs to node $0$.
To show that the leafs are not lazy toad nodes (nodes $1dots m$):
The longest path in these trees is always $2$, which means you can't have more than $2$ frogs on any node other than the leaf node you are trying to solve the game at. This implies all other leafs must reach target leaf $k_0$ with at most $2$ frogs (since that's already their distance to it as well, it must be exactly $2$ frogs).
The only node that can supplement leaf nodes with frogs up to $2$ frogs is node $0$. After using node $0$ to bring leaf $k_1$ frogs to target leaf $k_0$, all other leafs will have no moves to bring their frogs to $k_0.implies$ game is not solvable at leaf $k_0$, regardless of leaf choices for $k_0,k_1$ as everything is symmetric.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases without [n-1] trees = The $[m]_0$ tree sets
Lets exclude examples from $[n-1]$ set, from sets $[m]$; Let $[m]_0$ be a set of all trees with one branching node of degree $mge3$, that have at least $m+2$ nodes.
For $m=3$:
Theorem. Trees in $[3]_0$ are all fully lazy for $nge9$. They are also fully lazy for $nlt9$ except for these $4$ examples with exactly one non-lazy toad node (colored in red) shown here:
For $m=4$:
Theorem. Trees in $[4]_0$ are all fully lazy for $nge15$. They are also fully lazy for $nlt15$ except for a finite set of examples which are sorted below:
$1$ non-lazy toad examples, $2$ non-lazy toads examples, $3$ non-lazy toads examples, $5$ non-lazy toads example, $6$ non-lazy toads examples.
For $mge5$:
Conjecture. Trees in $[m]_0$ are all fully lazy for $nge n_m$. They are also fully lazy for $nlt n_m$ except for a finite set of
examples with varying number of non-lazy toad nodes.
I believe one can compute solutions for enough examples to guess $n_m$ for some $[m]_0$ set and then prove it with help of an algorithm by reconstructing the solvability of nodes. The examples for $nlt n_m$ can be computed as there should be finitely many of them.
But solving each $m$ individually with mainly relying on a computation, won't solve this problem for all $[m]_0$ sets. A characterizations of these trees is needed that will help mathematically prove the laziness of nodes of these trees.
Question: Any ideas how to reach such characterization(s)?
$bge2$ Branching nodes cases
Each of these cases can be further split into sets $[m_1,m_2,dots,m_b]=$ set of all trees with $b$ branching nodes that have degrees $m_1,m_2,dots,m_b$.
Each of those sets should have their $n_{(m_1,m_2,dots,m_b)}$ such that all trees with $nge n_{(m_1,m_2,dots,m_b)}$ nodes are fully lazy, where set of trees with $nlt n_{(m_1,m_2,dots,m_b)}$ nodes will have a finite number of examples with varying number of non-lazy toad nodes.
Question: Any ideas how to effectively find $n_{(m_1,m_2,dots,m_b)}$?
For example, for $b=1$, I conjecture that it is enough to observe this type of trees:
3 2 1
| /
4 - 0 - m - m+1 - m+2 - m+3 - ... - m+k-1 - m+k
/ |
5 ... m-1
And by finding $k_0$ such that all those trees are fully lazy for all $kge k_0$, we get $n_m$.
graph-theory recreational-mathematics trees
1
Purely based off of the pictures you provided, perhaps the important thing to look at is not the number of leaves, but the number of "branch vertices", those vertices of degree at least 3.
– Bob Krueger
Sep 2 '18 at 16:27
add a comment |
The frog game on a Tree:
- Default start of the game is placing one frog on each node (vertex).
- The goal is to move all the frogs to one single node.
- A single move consists of moving all $n$ frogs from node $A$ to nonempty node $B$, which is allowed only if there exists a path from $A$ to $B$ containing exactly $n$ unique edges. Node $B$ is called nonempty if there is at least one frog on it.
- If it is possible for all frogs to end up on some node $N$ (the game is solvable at N), then that implies that the frog on node $N$ never moves during the game, hence that node will be called a lazy toad.
Question: How can one characterize lazy and non-lazy toad nodes within trees?
Spliting trees into sets and characterizing lazy toads within those sets
I was initially observing tree sets based on leafs, but Bob Krueger suggested in the comments that it's better to look at branching nodes instead. Indeed, this is a better way to look at the trees.
A branching node is a node of degree at least $3$.
I decided to observe $b$ branching node tree cases - sets of trees with $b$ branching nodes.
They are further split into sets $[m_1,m_2,dots,m_b]=$ a set of all trees whose branching nodes $b_1,b_2,dots,b_b$ have degrees $m_1,m_2,dots,m_b$.
$0$ Branching nodes case
This case is basically the Frog Jumping game showed on Numberphile.
Tree with $n$ nodes that is categorized under this case always looks like a simple chain:
1-2-3-...-(n-2)-(n-1)-n
This case was already fully solved at the linked video. I will formalize the proof below:
Theorem. All trees that have no branching nodes are always fully lazy (All
nodes are lazy toads).
Proof.
$(1)$ Given tree with $n$ nodes labeled as "$1-2-3-...-n$", it is always solvable at nodes $1$ and $n$ :
If $n$ is odd, start at middle node $frac{n+1}{2}$. Then by repeated jumping "left-right" we end up with all frogs at node $n$. Symmetrically, repeated "right-left" jumps will solve the game at node $1$.
If $n$ is even, we can start at $frac{n}{2}$ and by repeating "right-left" solve the game at $n$. Again, symmetrically, starting at $frac{n}{2}+1$ and repeating "left-right", solve the game at $1$.
If we can always solve the tree at leaf nodes ($1$ and $n$), then we can solve it at any node:
- Simply split the tree into two parts: "$1-2-dots-k$" and "$k-(k+1)-dots-n$". Now solve both parts at $k$ as explained in $(1).implies$ tree is solvable at node $k$, where $k$ is any node.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases
This case can be split into sub-cases $[m]$, where $[m]$ stands for the set of all trees with one branching node of degree $mge3$. Those trees will have at least $n=m+1$ nodes.
The $[n-1]$ tree set
If $m$ is not constant but set to $m=n-1$, where $n$ is the number of the nodes of the tree, then this set of trees is trivial. All of them look like a "sun" or "flower head"; Label nodes from $0$ to $n+1=m$, and let node $0$ be the node of degree $m$.
3 2 1
| /
4 - 0 - m
/ |
5 ... m-1
Theorem. All trees in this set have exactly one lazy toad node, node $0$.
Proof.
To show that $0$ is lazy is trivial: For every other node, move its frogs to node $0$.
To show that the leafs are not lazy toad nodes (nodes $1dots m$):
The longest path in these trees is always $2$, which means you can't have more than $2$ frogs on any node other than the leaf node you are trying to solve the game at. This implies all other leafs must reach target leaf $k_0$ with at most $2$ frogs (since that's already their distance to it as well, it must be exactly $2$ frogs).
The only node that can supplement leaf nodes with frogs up to $2$ frogs is node $0$. After using node $0$ to bring leaf $k_1$ frogs to target leaf $k_0$, all other leafs will have no moves to bring their frogs to $k_0.implies$ game is not solvable at leaf $k_0$, regardless of leaf choices for $k_0,k_1$ as everything is symmetric.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases without [n-1] trees = The $[m]_0$ tree sets
Lets exclude examples from $[n-1]$ set, from sets $[m]$; Let $[m]_0$ be a set of all trees with one branching node of degree $mge3$, that have at least $m+2$ nodes.
For $m=3$:
Theorem. Trees in $[3]_0$ are all fully lazy for $nge9$. They are also fully lazy for $nlt9$ except for these $4$ examples with exactly one non-lazy toad node (colored in red) shown here:
For $m=4$:
Theorem. Trees in $[4]_0$ are all fully lazy for $nge15$. They are also fully lazy for $nlt15$ except for a finite set of examples which are sorted below:
$1$ non-lazy toad examples, $2$ non-lazy toads examples, $3$ non-lazy toads examples, $5$ non-lazy toads example, $6$ non-lazy toads examples.
For $mge5$:
Conjecture. Trees in $[m]_0$ are all fully lazy for $nge n_m$. They are also fully lazy for $nlt n_m$ except for a finite set of
examples with varying number of non-lazy toad nodes.
I believe one can compute solutions for enough examples to guess $n_m$ for some $[m]_0$ set and then prove it with help of an algorithm by reconstructing the solvability of nodes. The examples for $nlt n_m$ can be computed as there should be finitely many of them.
But solving each $m$ individually with mainly relying on a computation, won't solve this problem for all $[m]_0$ sets. A characterizations of these trees is needed that will help mathematically prove the laziness of nodes of these trees.
Question: Any ideas how to reach such characterization(s)?
$bge2$ Branching nodes cases
Each of these cases can be further split into sets $[m_1,m_2,dots,m_b]=$ set of all trees with $b$ branching nodes that have degrees $m_1,m_2,dots,m_b$.
Each of those sets should have their $n_{(m_1,m_2,dots,m_b)}$ such that all trees with $nge n_{(m_1,m_2,dots,m_b)}$ nodes are fully lazy, where set of trees with $nlt n_{(m_1,m_2,dots,m_b)}$ nodes will have a finite number of examples with varying number of non-lazy toad nodes.
Question: Any ideas how to effectively find $n_{(m_1,m_2,dots,m_b)}$?
For example, for $b=1$, I conjecture that it is enough to observe this type of trees:
3 2 1
| /
4 - 0 - m - m+1 - m+2 - m+3 - ... - m+k-1 - m+k
/ |
5 ... m-1
And by finding $k_0$ such that all those trees are fully lazy for all $kge k_0$, we get $n_m$.
graph-theory recreational-mathematics trees
The frog game on a Tree:
- Default start of the game is placing one frog on each node (vertex).
- The goal is to move all the frogs to one single node.
- A single move consists of moving all $n$ frogs from node $A$ to nonempty node $B$, which is allowed only if there exists a path from $A$ to $B$ containing exactly $n$ unique edges. Node $B$ is called nonempty if there is at least one frog on it.
- If it is possible for all frogs to end up on some node $N$ (the game is solvable at N), then that implies that the frog on node $N$ never moves during the game, hence that node will be called a lazy toad.
Question: How can one characterize lazy and non-lazy toad nodes within trees?
Spliting trees into sets and characterizing lazy toads within those sets
I was initially observing tree sets based on leafs, but Bob Krueger suggested in the comments that it's better to look at branching nodes instead. Indeed, this is a better way to look at the trees.
A branching node is a node of degree at least $3$.
I decided to observe $b$ branching node tree cases - sets of trees with $b$ branching nodes.
They are further split into sets $[m_1,m_2,dots,m_b]=$ a set of all trees whose branching nodes $b_1,b_2,dots,b_b$ have degrees $m_1,m_2,dots,m_b$.
$0$ Branching nodes case
This case is basically the Frog Jumping game showed on Numberphile.
Tree with $n$ nodes that is categorized under this case always looks like a simple chain:
1-2-3-...-(n-2)-(n-1)-n
This case was already fully solved at the linked video. I will formalize the proof below:
Theorem. All trees that have no branching nodes are always fully lazy (All
nodes are lazy toads).
Proof.
$(1)$ Given tree with $n$ nodes labeled as "$1-2-3-...-n$", it is always solvable at nodes $1$ and $n$ :
If $n$ is odd, start at middle node $frac{n+1}{2}$. Then by repeated jumping "left-right" we end up with all frogs at node $n$. Symmetrically, repeated "right-left" jumps will solve the game at node $1$.
If $n$ is even, we can start at $frac{n}{2}$ and by repeating "right-left" solve the game at $n$. Again, symmetrically, starting at $frac{n}{2}+1$ and repeating "left-right", solve the game at $1$.
If we can always solve the tree at leaf nodes ($1$ and $n$), then we can solve it at any node:
- Simply split the tree into two parts: "$1-2-dots-k$" and "$k-(k+1)-dots-n$". Now solve both parts at $k$ as explained in $(1).implies$ tree is solvable at node $k$, where $k$ is any node.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases
This case can be split into sub-cases $[m]$, where $[m]$ stands for the set of all trees with one branching node of degree $mge3$. Those trees will have at least $n=m+1$ nodes.
The $[n-1]$ tree set
If $m$ is not constant but set to $m=n-1$, where $n$ is the number of the nodes of the tree, then this set of trees is trivial. All of them look like a "sun" or "flower head"; Label nodes from $0$ to $n+1=m$, and let node $0$ be the node of degree $m$.
3 2 1
| /
4 - 0 - m
/ |
5 ... m-1
Theorem. All trees in this set have exactly one lazy toad node, node $0$.
Proof.
To show that $0$ is lazy is trivial: For every other node, move its frogs to node $0$.
To show that the leafs are not lazy toad nodes (nodes $1dots m$):
The longest path in these trees is always $2$, which means you can't have more than $2$ frogs on any node other than the leaf node you are trying to solve the game at. This implies all other leafs must reach target leaf $k_0$ with at most $2$ frogs (since that's already their distance to it as well, it must be exactly $2$ frogs).
The only node that can supplement leaf nodes with frogs up to $2$ frogs is node $0$. After using node $0$ to bring leaf $k_1$ frogs to target leaf $k_0$, all other leafs will have no moves to bring their frogs to $k_0.implies$ game is not solvable at leaf $k_0$, regardless of leaf choices for $k_0,k_1$ as everything is symmetric.
$$tag*{$blacksquare$}$$
$1$ Branching nodes cases without [n-1] trees = The $[m]_0$ tree sets
Lets exclude examples from $[n-1]$ set, from sets $[m]$; Let $[m]_0$ be a set of all trees with one branching node of degree $mge3$, that have at least $m+2$ nodes.
For $m=3$:
Theorem. Trees in $[3]_0$ are all fully lazy for $nge9$. They are also fully lazy for $nlt9$ except for these $4$ examples with exactly one non-lazy toad node (colored in red) shown here:
For $m=4$:
Theorem. Trees in $[4]_0$ are all fully lazy for $nge15$. They are also fully lazy for $nlt15$ except for a finite set of examples which are sorted below:
$1$ non-lazy toad examples, $2$ non-lazy toads examples, $3$ non-lazy toads examples, $5$ non-lazy toads example, $6$ non-lazy toads examples.
For $mge5$:
Conjecture. Trees in $[m]_0$ are all fully lazy for $nge n_m$. They are also fully lazy for $nlt n_m$ except for a finite set of
examples with varying number of non-lazy toad nodes.
I believe one can compute solutions for enough examples to guess $n_m$ for some $[m]_0$ set and then prove it with help of an algorithm by reconstructing the solvability of nodes. The examples for $nlt n_m$ can be computed as there should be finitely many of them.
But solving each $m$ individually with mainly relying on a computation, won't solve this problem for all $[m]_0$ sets. A characterizations of these trees is needed that will help mathematically prove the laziness of nodes of these trees.
Question: Any ideas how to reach such characterization(s)?
$bge2$ Branching nodes cases
Each of these cases can be further split into sets $[m_1,m_2,dots,m_b]=$ set of all trees with $b$ branching nodes that have degrees $m_1,m_2,dots,m_b$.
Each of those sets should have their $n_{(m_1,m_2,dots,m_b)}$ such that all trees with $nge n_{(m_1,m_2,dots,m_b)}$ nodes are fully lazy, where set of trees with $nlt n_{(m_1,m_2,dots,m_b)}$ nodes will have a finite number of examples with varying number of non-lazy toad nodes.
Question: Any ideas how to effectively find $n_{(m_1,m_2,dots,m_b)}$?
For example, for $b=1$, I conjecture that it is enough to observe this type of trees:
3 2 1
| /
4 - 0 - m - m+1 - m+2 - m+3 - ... - m+k-1 - m+k
/ |
5 ... m-1
And by finding $k_0$ such that all those trees are fully lazy for all $kge k_0$, we get $n_m$.
graph-theory recreational-mathematics trees
graph-theory recreational-mathematics trees
edited 2 days ago
asked Sep 2 '18 at 12:14
Vepir
2,95221041
2,95221041
1
Purely based off of the pictures you provided, perhaps the important thing to look at is not the number of leaves, but the number of "branch vertices", those vertices of degree at least 3.
– Bob Krueger
Sep 2 '18 at 16:27
add a comment |
1
Purely based off of the pictures you provided, perhaps the important thing to look at is not the number of leaves, but the number of "branch vertices", those vertices of degree at least 3.
– Bob Krueger
Sep 2 '18 at 16:27
1
1
Purely based off of the pictures you provided, perhaps the important thing to look at is not the number of leaves, but the number of "branch vertices", those vertices of degree at least 3.
– Bob Krueger
Sep 2 '18 at 16:27
Purely based off of the pictures you provided, perhaps the important thing to look at is not the number of leaves, but the number of "branch vertices", those vertices of degree at least 3.
– Bob Krueger
Sep 2 '18 at 16:27
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2902660%2ffrogs-jumping-on-trees%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2902660%2ffrogs-jumping-on-trees%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Purely based off of the pictures you provided, perhaps the important thing to look at is not the number of leaves, but the number of "branch vertices", those vertices of degree at least 3.
– Bob Krueger
Sep 2 '18 at 16:27