On extremal sizes of locally $k$-tree graphs

Mieczysław Borowiecki; Piotr Borowiecki; Elżbieta Sidorowicz; Zdzisław Skupień

Displaying similar documents to “On extremal sizes of locally $k$ -tree graphs”

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

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.

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

Regular graphs and their spanning trees

Jiří Sedláček (1970)

Časopis pro pěstování matematiky

Similarity:

Displaying similar documents to “On extremal sizes of locally k -tree graphs”

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

Cyclic decompositions of complete graphs into spanning trees

Minimum degree, leaf number and traceability

Regular graphs and their spanning trees

Displaying similar documents to “On extremal sizes of locally $k$ -tree graphs”