Strong Tree Labelling Conjecture
Vertex Properties For any vertex, there exists label n. For any label n, there exists an integer I i such that i is from one t to the count of the improper subtree’s vertices, V. The label n is constructed while the graph is constructed by a current count which is incremented AFTER the vertex is labeled.
Vertex Example: The circle has 1 inside.
Edge Properties For any edge e, there exists a two tuple (i, j) such that i equals the vertex’s label towards the improper subtree’s root and j towards the improper subtree’s leaves. Remark: For any edge e, the edge may or may not have a weight w such that w is a real number.
Edge Example: The integer 1 is inside the top circle. The top circle is attached to an edge which is a line segment which is labeled 1 towards the top circle and 2 towards the bottom circle. There is a bottom circle with 2 inside.
Required Fully Connected Subtree Properties The function si domain is a a subtree’s vertex root’s label s and a vertex’s label attached the subtree v.. The function si co-domain is a integer i such that is from one to the count of the subtree’s vertices. The function si modulo the count of vertices in the subtree is defined to be the subtree’s root vertex’s label plus the vertex’s label modulo the count of vertices in the subtree.
The function sj domain is a a subtree’s vertex root’s label s and a vertex’s label attached the subtree v.. The function sj co-domain is a natural number i such that is from one to the count of the subtree’s vertices. The function sj modulo the count of vertices in the subtree is defined to be the subtree’s root vertex’s label plus the vertex’s label modulo the count of vertices in the subtree.
For any subtree s, s vertex’s constructed by the function si, and the edges constructed by the two tuple (si(.,.), sj(., .)). The constructed subtree meets the vertex properties and the edge properties.
Conjecture (Not Sure How To Prove) For Simple Trees Claim: For any improper subset of a simple tree t, t can be labelled to meet the required connected subtree’s properties. Also, t meets the vertex properties and edge properties.
I am not sure how to prove this or what methods to prove, so I have tried a proof for a binary search tree.
Lemma: There Exists A Binary Search Tree With The Labelling
Proof By Cases
Case: Leaf Vertex Without Children Leaf Vertex Property: Consider the definition of the function si. Since (i + 0)(mod i) = 0, the vertex property is meet.
Edge Properties: Since there is no edge, the property is vacuously true.
Case Left Vertex Without Right Vertex Leaf Vertex Property: Consider the definition of the function si. Since (i + 0)(mod i) = 0, the vertex property is meet.
Left Child Vertex Property: Consider the definition of the function si. Since (i + 1)(mod i) = 1, the vertex property is meet.
Edge Properties: For the edge e, let i = 0 and j = 0.
Case Right Vertex Without Left Vertex Leaf Vertex Property: Consider the definition of the function si. Since (i + 0)(mod i) = 0, the vertex property is meet.
Right Child Vertex Property: Consider the definition of the function si. Since (i + 1)(mod i) = 1, the vertex property is meet.
Edge Properties: For the edge e, let i = 0 and j = 0.
Case Left Vertex And Right Vertex Leaf Vertex Property: Consider the definition of the function si. Since (i + 0)(mod i) = 0, the vertex property is meet. Therefore, the vertex property is meet
Left Vertex Property: Consider the definition of the function si. Since the vertex is constructed first, si becomes n for the left vertex becomes (i + 0)(mod i) which equals zero.
Right Child Vertex Property: Consider the definition of the function si..Since the vertex is constructed last, si becomes (i + 2)(mod i) which equals two.
Edge Properties: For the edge between the left vertex and the improper subtree’s root, let i = 0 and j = 1. For the edge between the right vertex and the improper subtree’s root, let i = 0 and j = 1./
Solution For a Complete Tree
The tree is constructed one vertex at a time in an in-order traversal. The count of vertices added is incremented AFTER the vertex is constructed.
Case: Root of Improper Subtree: Vertex Property of Root: The label is constructed to be zero. Consider the definition of the function si. The function si (mod 1) becomes (0 + 0) mod 1 which is zero.
Edge Property of Root: Let i = 0 in the edges. The j value is constructed after the vertex attached to the root is constructed.
Case: Leaf of Improper Subtree Vertex Property: If the tree is constructed in an in-order ordering then the leaf's vertex is exactly one more than the leaf's parent's vertex.
Since the vertex's are constructed one at a time, this label is unique and meets the strong label requirements for the tree.
For the subtree, consider the definition of the function si. The function si mod count of vertices becomes (count of vertices + 0) mod count of vertices which equals zero. Since a subtree of a single vertex meets the interval for the labels, this meets the vertex properties.
Edge Property: let i = parent's i and j = parent vertex's i plus one.
Case: Not Root of Subtree or leaf of Subtree Vertex Property: The vertex's parent vertex has a degree d. Also, the vertex's parent has a vertex label of i. Consider the definition of the function si. The function si becomes (i + d)(mod count of vertices). Since there are child vertex's, i + d is less than the count of vertices. In fact, before the vertex's first child vertex is added, i + d is less than the count of vertices. This implies the function's i + d portion never went over count of vertices, which simplifies to i + d. Since the vertex's degree is incremented, the formula produced a unique and total ordering to the child vertex's.
Edge Properties: Let i be the parent's vertex and j the child's vertex. Since the edge is constructed after the vertex, this meets the edge properties.