Cyclic decompositions of complete graphs into spanning trees

Dalibor Froncek

Displaying similar documents to “Cyclic decompositions of complete graphs into spanning trees”

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.

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 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).

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...

Multi-faithful spanning trees of infinite graphs

Norbert Polat (2001)

Czechoslovak Mathematical Journal

Similarity:

For an end $τ$ and a tree $T$ of a graph $G$ we denote respectively by $m (τ)$ and $m_{T} (τ)$ the maximum numbers of pairwise disjoint rays of $G$ and $T$ belonging to $τ$ , and we define $t m (τ) : = min {m_{T} (τ) T is a spanning tree of G}$ . In this paper we give partial answers—affirmative and negative ones—to the general problem of determining if, for a function $f$ mapping every end $τ$ of $G$ to a cardinal $f (τ)$ such that $t m (τ) \leq f (τ) \leq m (τ)$ , there exists a spanning tree $T$ of $G$ such that $m_{T} (τ) = f (τ)$ for every end $τ$ of $G$ .

A characterization of roman trees

Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is $w (f) = \sum_{v \in V} f (v)$ . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number...

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite connected graph with minimum degree $δ$ . The leaf number $L (G)$ of $G$ is defined as the maximum number of leaf vertices contained in a spanning tree of $G$ . We prove that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....

Signpost systems and spanning trees of graphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

By a ternary system we mean an ordered pair $(W, R)$ , where $W$ is a finite nonempty set and $R \subseteq W \times W \times W$ . By a signpost system we mean a ternary system $(W, R)$ satisfying the following conditions for all $x, y, z \in W$ : if $(x, y, z) \in R$ , then $(y, x, x) \in R$ and $(y, x, z) \notin R$ ; if $x \neq y$ , then there exists $t \in W$ such that $(x, t, y) \in R$ . In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G, T)$ , where $G$ is a connected graph and $T$ is a spanning tree of $G$ . If $(G, T)$ is a ct-pair, then by...