We study semigroups of labellings associated to a graph. These generalise the Jukes-Cantor model and phylogenetic toric varieties defined in Buczynska W., Phylogenetic toric varieties on graphs, J. ...Algebraic Combin., 2012, 35(3), 421–460. Our main theorem bounds the degree of the generators of the semigroup by
g
+ 1 when the graph has first Betti number
g
. Also, we provide a series of examples where the bound is sharp.
A gap-k-vertex-labelling of a simple graph G = (V, E) is a pair (π, cπ) in which π : V (G) → {1, 2, ..., k} is an assignment of labels to the vertices of G and cπ : V (G) → {0, 1, ..., k} is a proper ...vertex-colouring of G such that, for every v ∈ V (G) of degree at least two, cπ(v) is induced by the largest difference, i.e. the largest gap, between the labels of its neighbours (cases where d(v) = 1 and d(v) = 0 are treated separately). Introduced in 2013 by A. Dehghan et al. Dehghan, A., M. Sadeghi and A. Ahadi, Algorithmic complexity of proper labeling problems, Theoretical Computer Science 495 (2013), pp. 25–36., they show that deciding whether a bipartite graph admits a gap-2-vertex-labelling is NP-complete and question the computational complexity of deciding whether cubic bipartite graphs admit such a labelling. In this work, we advance the study of the computational complexity for this class, proving that this problem remains NP-complete even when restricted to subcubic bipartite graphs.
This paper takes a close look at graceful labelling and its applications. We pay special attention to the famous Graceful Tree Conjecture, which has attracted a lot of interest and engaged many ...researchers over the last 40+ years, and yet to this day remains unsolved. We describe applications of graceful and graceful-like labellings of trees to several well known combinatorial problems and we expose yet another one, namely the connection between
α
-labelling of paths and near transversals in Latin squares. Finally, we show how spectral graph theory can be used to further the progress on the Graceful Tree Conjecture.
PDF
