On the Erdős-Sós Conjecture for Stars, Paths and Some of Their Variants

摘要

Modern supercomputers are massively parallel systems: they consist of hundreds of thousands of compute nodes. The interconnection network of supercomputers, and networks in computing generally, face several sorts of constraints and limitations, for instance a maximum number of links per compute node. Extremal graph theory enables to measure how the global properties of a network impact the network locally, and is thus very interesting to address network topology issues, providing a theoretical basis for such problems. The Erdős-Sós conjecture is a well-known open problem of extremal graph theory. This conjecture is that a finite graph G with an average degree greater than k−1 contains every tree of k edges (k≥2). Following on previous works that establish the correctness of the conjecture for a few particular trees, we formally show in this paper that the conjecture holds for several particular classes of trees of k edges, precisely a star, a variant of a star which we call a "mutant" star, a path and a variant of a path which we call a "mutant" path. Regarding the contribution of this paper, the author insists on the elegance and readability of the proofs proposed in this paper, compared to those of previous works.