A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.

We examine constructions of non-symmetric trees with a flexible q-labeling or an α-like labeling, which allow factorization of $K_{2n}$ into spanning trees, arising from the trees with α-labelings.

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V=v₀,v₁,...,v_{n-1}$, $E₁=v₀v₁,...,v₀v_{n-3},v_{n-4}{v}_{n-2},v_{n-3}{v}_{n-1}$ and $E₂=v₀v₁,...,v₀v_{n-3},v_{n-3}{v}_{n-2},v_{n-3}{v}_{n-1}$. For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r(Tₘ,T{ₙ}^i)$, where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in $O\left(\right|V|+|E\left|\right)$ time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared.

The problem of embedding graphs into other graphs is much studied in the graph theory. In fact, much effort has been devoted to determining the conditions under which a graph G is a subgraph of a graph H, having a particular structure. An important class to study is the set of graphs which are embeddable into a hypercube. This importance results from the remarkable properties of the hypercube and its use in several domains, such as: the coding theory, transfer of information, multicriteria rule,...

The problem of embedding graphs into other graphs is much studied in the graph theory. In fact, much effort has been devoted to determining the conditions under which a graph G is a subgraph of a graph H, having a particular structure. An important class to study is the set of graphs which are embeddable into a hypercube. This importance results from the remarkable properties of the hypercube and its use in several domains, such as: the coding theory, transfer of information, multicriteria rule,...