Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is $val\left(f\right)={\Sigma }_{e\in E\left(G\right)}{f}^{\text{'}}K\left(e\right)$. The maximum value of a γ-labeling of G is defined as $va{l}_{max}\left(G\right)=maxval\left(f\right):fisa\gamma -labelingofG$; while the minimum value of a γ-labeling of G is $va{l}_{min}\left(G\right)=minval\left(f\right):fisa\gamma -labelingofG$; The values $va{l}_{max}\left(S_{p,q}\right)$ and $va{l}_{min}\left(S_{p,q}\right)$ are determined for double stars $S_{p,q}$. We present characterizations of connected graphs G of order n for which $va{l}_{min}\left(G\right)=n$ or $va{l}_{min}\left(G\right)=n+1$.

The reverse Wiener index of a connected graph $G$ is defined as $$\Lambda \left(G\right)=\frac{1}{2}n(n-1)d-W\left(G\right),$$ where $n$ is the number of vertices, $d$ is the diameter, and $W\left(G\right)$ is the Wiener index (the sum of distances between all unordered pairs of vertices) of $G$. We determine the $n$-vertex non-starlike trees with the first four largest reverse Wiener indices for $n\ge 8$, and the $n$-vertex non-starlike non-caterpillar trees with the first four largest reverse Wiener indices for $n\ge 10$.

In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree $T$ of order $n$ and each integer $k\ge 2$, there is a $k$-packing of $T$ in a complete bipartite graph $B_{n+k-1}$ whose order is $n+k-1$. We prove the conjecture is true for $k=4$.

We show that if a sequence of trees T1, T2, ..., Tn−1 can be packed into Kn then they can be also packed into any n-chromatic graph.

We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.

A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...

The reaping number ${𝔯}_{m,n}\left(𝔹\right)$ of a Boolean algebra $𝔹$ is defined as the minimum size of a subset $𝒜\subseteq 𝔹\setminus \left\{𝐎\right\}$ such that for each $m$-partition $𝒫$ of unity, some member of $𝒜$ meets less than $n$ elements of $𝒫$. We show that for each $𝔹$, ${𝔯}_{m,n}\left(𝔹\right)={𝔯}_{\lceil \frac{m}{n-1}\rceil ,2}\left(𝔹\right)$ as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every $k$-branching tree whose maximal nodes are coloured with $\ell$ colours contains an $m$-branching subtree using at most $n$ colours if and only if $\lceil \frac{\ell }{n}\rceil <\lceil \frac{k}{m-1}\rceil$.

The aim of this paper is to characterize the patterns of successive distances of leaves in plane trivalent trees, and give a very short characterization of their parity pattern. Besides, we count how many trees satisfy some given sequences of patterns.

Starting with the computation of the appropriate Poisson kernels, we review, complement, and compare results on drifted Laplace operators in two different contexts: homogeneous trees and the hyperbolic half-plane.