Multi-faithful spanning trees of infinite graphs

Norbert Polat

Displaying similar documents to “Multi-faithful spanning trees of infinite graphs”

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $c n^{3 / 4}$ (at most n).

End-faithful spanning trees of countable graphs with prescribed sets of rays

Norbert Polat (2001)

Czechoslovak Mathematical Journal

Similarity:

We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.

Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

Jernej Azarija, Riste Škrekovski (2013)

Mathematica Bohemica

Similarity:

Let $α (n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n \geq 3$ spanning trees. Similarly, define $β (n)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n \geq 3$ spanning trees. As an $n$ -cycle has exactly $n$ spanning trees, it follows that $α (n), β (n) \leq n$ . In this paper, we show that $α (n) \leq \frac{1}{3} (n + 4)$ and $β (n) \leq \frac{1}{3} (n + 7)$ if and only if $n \notin {3, 4, 5, 6, 7, 9, 10, 13, 18, 22}$ , which is a subset of Euler’s idoneal numbers. Moreover, if $n \neg \equiv 2 (mod 3)$ and $n \neq 25$ we show that $α (n) \leq \frac{1}{4} (n + 9)$ and $β (n) \leq \frac{1}{4} (n + 13) .$ This improves some previously estabilished...

Spanning trees of infinite graphs

Norbert Polat (1991)

Czechoslovak Mathematical Journal

Similarity:

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees

Michael Kubesa (2005)

Discussiones Mathematicae Graph Theory

Similarity:

We examine constructions of non-symmetric trees with a flexible q-labeling or an α-like labeling, which allow factorization of $K_{2 n}$ into spanning trees, arising from the trees with α-labelings.

Cyclic decompositions of complete graphs into spanning trees

Dalibor Froncek (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We examine decompositions of complete graphs with an even number of vertices, $K_{2 n}$ , 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.

On extremal sizes of locally $k$ -tree graphs

Mieczysław Borowiecki, Piotr Borowiecki, Elżbieta Sidorowicz, Zdzisław Skupień (2010)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a if for any vertex $v$ the subgraph induced by the neighbours of $v$ is a $k$ -tree, $k \geq 0$ , where $0$ -tree is an edgeless graph, $1$ -tree is a tree. We characterize the minimum-size locally $k$ -trees with $n$ vertices. The minimum-size connected locally $k$ -trees are simply $(k + 1)$ -trees. For $k \geq 1$ , we construct locally $k$ -trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an $n$ -vertex locally $k$ -tree graph is between $Ω (n)$ and $O (n^{2})$ , where both bounds...