We deal with rectangular m×n boards of square cells, using the cut technics of the height function. We investigate combinatorial properties of this function, and in particular we give lower and upper bounds for the number of essentially different cuts. This number turns out to be the cardinality of the height function’s range, in case the height function has maximally many rectangular islands.

We exhibit a monoidal structure on the category of finite sets indexed by P-trees for a finitary polynomial endofunctor P. This structure categorifies the monoid scheme (over Spec ℕ) whose semiring of functions is (a P-version of) the Connes-Kreimer bialgebra H of rooted trees (a Hopf algebra after base change to ℤ and collapsing H 0). The monoidal structure is itself given by a polynomial functor, represented by three easily described set maps; we show that these maps are the same as those occurring...

Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) - D is dominated at least k times by D. The k-domination number γₖ(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.

The eccentricity of a vertex $v$ of a connected graph $G$ is the distance from $v$ to a vertex farthest from $v$ in $G$. The center of $G$ is the subgraph of $G$ induced by the vertices having minimum eccentricity. For a vertex $v$ in a 2-edge-connected graph $G$, the edge-deleted eccentricity of $v$ is defined to be the maximum eccentricity of $v$ in $G-e$ over all edges $e$ of $G$. The edge-deleted center of $G$ is the subgraph induced by those vertices of $G$ having minimum edge-deleted eccentricity. The edge-deleted central...

The Traveling Salesman Problem (TSP) is still one of the most researched topics in computational mathematics, and we introduce a variant of it, namely the study of the closed k-walks in graphs. We search for a shortest closed route visiting k cities in a non complete graph without weights. This motivates the following definition. Given a set of k distinct vertices = x₁, x₂, ...,xₖ in a simple graph G, the closed k-stop-distance of set is defined to be $dₖ\left(\right)=mi{n}_{\Theta \in \left(\right)}(d(\Theta \left(x₁\right),\Theta \left(x₂\right))+d(\Theta \left(x₂\right),\Theta \left(x₃\right))+...+d(\Theta \left(xₖ\right),\Theta \left(x₁\right)))$, where () is the set of all permutations from...

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $de{g}_{G}u+de{g}_{G}v\ge n-1$, G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $de{g}_{G}u+de{g}_{G}v$ and the structure of the distant area for u and v. We prove that if the...

The definition of n-width of a bounded subset A in a normed linear space X is based on the existence of n-dimensional subspaces. Although the concept of an n-dimensional subspace is not available for metric trees, in this paper, using the properties of convex and compact subsets, we present a notion of n-widths for a metric tree, called Tn-widths. Later we discuss properties of Tn-widths, and show that the compact width is attained. A relationship between the compact widths and Tn-widths is also...

The aim of this paper is to provide upper bounds for the entropy numbers of summation operators on trees in a critical case. In a recent paper [Studia Math. 202 (2011)] we elaborated a framework of weighted summation operators on general trees where we related the entropy of the operator to those of the underlying tree equipped with an appropriate metric. However, the results were left incomplete in a critical case of the entropy behavior, because this case requires much more involved techniques....

We investigate compactness properties of weighted summation operators $V_{\alpha ,\sigma }$ as mappings from ℓ₁(T) into ${\ell }_q\left(T\right)$ for some q ∈ (1,∞). Those operators are defined by $\left(V_{\alpha ,\sigma }x\right)\left(t\right):=\alpha \left(t\right){\sum }_{s⪰t}\sigma \left(s\right)x\left(s\right)$, t ∈ T, where T is a tree with partial order ⪯. Here α and σ are given weights on T. We introduce a metric d on T such that compactness properties of (T,d) imply two-sided estimates for $eₙ\left(V_{\alpha ,\sigma }\right)$, the (dyadic) entropy numbers of $V_{\alpha ,\sigma }$. The results are applied to concrete trees, e.g. moderately increasing, biased or binary trees and to weights with α(t)σ(t)...

Comparing q-ary relations on a set $𝒪$ of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the context...