Counting graphs with different numbers of spanning trees through the counting of prime partitions

Jernej Azarija

Displaying similar documents to “Counting graphs with different numbers of spanning trees through the counting of prime partitions”

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

Uniquely partitionable planar graphs with respect to properties having a forbidden tree

Jozef Bucko, Jaroslav Ivančo (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁, ₂ be graph properties. A vertex (₁,₂)-partition of a graph G is a partition V₁,V₂ of V(G) such that for i = 1,2 the induced subgraph $G [V_{i}]$ has the property $_{i}$ . A property ℜ = ₁∘₂ is defined to be the set of all graphs having a vertex (₁,₂)-partition. A graph G ∈ ₁∘₂ is said to be uniquely (₁,₂)-partitionable if G has exactly one vertex (₁,₂)-partition. In this note, we show the existence of uniquely partitionable planar graphs with respect to hereditary additive properties having a...

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.

Degree sequences of graphs containing a cycle with prescribed length

Jian Hua Yin (2009)

Czechoslovak Mathematical Journal

Similarity:

Let $r \geq 3$ , $n \geq r$ and $π = (d_{1}, d_{2}, ..., d_{n})$ be a non-increasing sequence of nonnegative integers. If $π$ has a realization $G$ with vertex set $V (G) = {v_{1}, v_{2}, ..., v_{n}}$ such that $d_{G} (v_{i}) = d_{i}$ for $i = 1, 2, ..., n$ and $v_{1} v_{2} \dots v_{r} v_{1}$ is a cycle of length $r$ in $G$ , then $π$ is said to be potentially $C_{r}^{''}$ -graphic. In this paper, we give a characterization for $π$ to be potentially $C_{r}^{''}$ -graphic.

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

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.