STRUCTURAL PROPERTIES OF CRYSTAL TREES

The work investigates the structural properties of Crystal Trees (CT), a class of graphs proposed by Andrade (2024), seeking to answer open theoretical questions. The research explores topological properties and considers Minimum Spanning Trees (MST) as a particular case of stable CTs, analyzing the relationship between suboptimal characteristics and the optimality of these trees. The methodology is based on exploratory computer simulations, using exhaustive enumeration algorithms and combinatorial pruning techniques. Results are presented for graphs with up to 12 vertices, facing exponential computational limitations in the enumeration of generating trees. The study investigates whether CTs can be obtained from MSTs by edge swaps and the possible NP-complete complexity of the problem. The results show that changing a single edge can generate instability, and that this instability grows with the size of the graph.