The search session has expired. Please query the service again.
In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree of order and each integer , there is a -packing of in a complete bipartite graph whose order is . We prove the conjecture is true for .
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 of a Boolean algebra is defined as the minimum size of a subset such that for each -partition of unity, some member of meets less than elements of . We show that for each , as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every -branching tree whose maximal nodes are coloured with colours contains an -branching subtree using at most colours if and only if .
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.
We present a new pruning procedure on discrete trees by adding marks on the nodes of trees. This procedure allows us to construct and study a tree-valued Markov process by pruning Galton–Watson trees and an analogous process by pruning a critical or subcritical Galton–Watson tree conditioned to be infinite. Under a mild condition on offspring distributions, we show that the process run until its ascension time has a representation in terms of . A similar result was obtained by Aldous and...
Currently displaying 1 –
17 of
17