Let T be a tree, let u be its vertex. The branch weight b(u) of u is the maximum number of vertices of a branch of T at u. The set of vertices u of T in which b(u) attains its minimum is the branch weight centroid B(T) of T. For finite trees the present author proved that B(T) coincides with the median of T, therefore it consists of one vertex or of two adjacent vertices. In this paper we show that for infinite countable trees the situation is quite different.
Let T be an infinite locally finite tree. We say that T has exactly one end, if in T any two one-way infinite paths have a common rest (infinite subpath). The paper describes the structure of such trees and tries to formalize it by algebraic means, namely by means of acyclic monounary algebras or tree semilattices. In these algebraic structures the homomorpisms and direct products are considered and investigated with the aim of showing, whether they give algebras with the required properties. At the end some further assertions on the structure of such trees are stated, without the algebraic formalization.
The domatic numbers of a graph $G$ and of its complement $\bar{G}$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs $G$ having $d(G) = d(\bar{G})$. Further, we will present a partial solution to the problem: Is it true that if $G$ is a graph satisfying $d(G) = d(\bar{G})$, then $\gamma (G) = \gamma (\bar{G})$? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement.
Generalized Petersen graphs are certain graphs consisting of one quadratic factor. For these graphs some numerical invariants concerning the domination are studied, namely the domatic number $d(G)$, the total domatic number $d_t(G)$ and the $k$-ply domatic number $d^k(G)$ for $k=2$ and $k=3$. Some exact values and some inequalities are stated.
The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the $n$-dimensional cube $Q_n$.
A subset D of the vertex set V (G) of a graph G is called dominating in G, if each vertex of G either is in D, or is adjacent to a vertex of D. If moreover the subgraph hDi of G induced by D is regular of degree 1, then D is called an induced-paired dominating set in G. A partition of V (G), each of whose classes is an induced-paired dominating set in G, is called an induced-paired domatic partition of G. The maximum number of classes of an induced-paired domatic partition of G is the induced-paired domatic number dip(G) of G. This paper studies its properties.
The paper concerns infinite paths (in particular, the maximum number of pairwise vertex-disjoint ones) in locally finite graphs and in spanning trees of such graphs.
A graph G is called locally s-regular if the neighbourhood of each vertex of G nduces a subgraph of G which is regular of degree s. We study graphs which are locally s-regular and simultaneously regular of degree r.
One of numerical invariants concerning domination in graphs is the $k$-subdomination number $\gamma ^{-11}_{kS}(G)$ of a graph $G$. A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph $G$ with $n$ vertices and any $k$ with $\frac{1}{2} n < k \leqq n$ the inequality $\gamma ^{-11}_{kS}(G) \leqq 2k - n$ holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and $k=5$.