A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph ${\mathscr{H}}_{d̲,d̅}\left(S\right)=(V,)$ where V = S and $=e\subseteq S:d̲<\left|e\right|<d̅\wedge {\sum }_{v\in e}v\in S$. For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices $w₁,...,w_{\sigma }\notin V$ such that $\mathscr{H}\cup w₁,...,w_{\sigma }$ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities...

A graph is called splitting if there is a 0-1 labelling of its vertices such that for every infinite set C of natural numbers there is a sequence of labels along a 1-way infinite path in the graph whose restriction to C is not eventually constant. We characterize the countable splitting graphs as those containing a subgraph of one of three simple types.

The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.

We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order $\Theta \left(d^{(r-1)n+1}\right)$, which improves and generalizes previous results.

We examine decompositions of complete graphs with an even number of vertices, $K_{2n}$, into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.