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

Michael Kubesa

The search session has expired. Please query the service again.

Displaying similar documents to “Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees”

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.

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

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

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

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 $d e g_{G} u + d e g_{G} v \geq 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 $d e g_{G} u + d e g_{G} v$ and the structure of the distant area for u and v. We prove...

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

Tree pattern matching from regular tree expressions

Ahlem Belabbaci, Hadda Cherroun, Loek Cleophas, Djelloul Ziadi (2018)

Kybernetika

Similarity:

In this work we deal with tree pattern matching over ranked trees, where the pattern set to be matched against is defined by a regular tree expression. We present a new method that uses a tree automaton constructed inductively from a regular tree expression. First we construct a special tree automaton for the regular tree expression of the pattern $E$ , which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree $t$ . The pattern...

Pruning Galton–Watson trees and tree-valued Markov processes

Romain Abraham, Jean-François Delmas, Hui He (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We present a new pruning procedure on discrete trees by adding marks on the nodes of trees. This procedure allows us to construct and study a tree-valued Markov process ${𝒢 (u)}$ by pruning Galton–Watson trees and an analogous process ${𝒢^{*} (u)}$ by pruning a critical or subcritical Galton–Watson tree conditioned to be infinite. Under a mild condition on offspring distributions, we show that the process ${𝒢 (u)}$ run until its ascension time has a representation in terms of ${𝒢^{*} (u)}$ . A similar result was obtained by...