The smallest values of algebraic connectivity for trees

The algebraic connectivity of a graph G is the second smallest eigenvalue of its Laplacian matrix. Let ■n be the set of all trees of order n. In this paper, we will provide the ordering of trees in ■n up to the last eight trees according to their smallest algebraic connectivities when n ≥ 13. This extends the result of Shao et al. [The ordering of trees and connected graphs by algebraic connectivity. Linear Algebra Appl., 428, 1421-1438 (2008)].     

On the average shape of monotonically labelled tree structures

Let $\text{B}$_k denote one of the families of binary trees, t-aray trees (t> 2) or ordered trees with nodes labelled monotonically by elements of {1 < 2 < ? < k}. The average height of the j-th leaf of the trees of $\text{B}$_k with exactly n nodes is shown to converge to a finite limit (depending on k and j) for n → ∞. The limit is determined explicitly for small values of k and its asymptotic behaviour in j and k is investigated. Some recent results on the average shape of rooted tree structures appear as special cases.     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

Connection reliabilities in stochastic acyclic networks

Acyclic networks are represented by rooted trees T from a given simply generated family ?. Let ?_n,p be the subset of ? containing all trees T with n nodes and p leaves. Assume that T is selected uniformly from ?_n,p and that each edge of t has probability q of failing. Let Z_i = 1 if the path conecting the root of T to the ith leaf does not contain a failed edge, O otherwise. We investigate the stochastic process (_Zi,…,_Zp). Asympototic results, manly for the family of tary trees, are derived. As auxiliary results, a general rotation lemma for simple families of trees is given, and the (joint) asymptotic leaf height destributions in tary trees determined. © 1994 John Wiley & Sons, Inc.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

Trees with second minimum general Randić index for α>0

The general Randi? index R _α (G) of a graph G is the sum of the weights (d(u)d(v)) ^α of all edges uv of G, where α is a real number(α≠0) and d(u) denotes the degree of the vertex u. We have known that P _n has minimum general Randi? index for α>0 among trees when n≥5. In this paper, we prove that P _n,3 has second minimum general Randi? index for α>0 among trees when n≥7.     

On Estrada index of trees

Let G be a graph on n vertices, and let λ₁,λ₂,…,λ_n be its eigenvalues. The Estrada index is defined as . We determine the unique tree with maximum Estrada index among the trees on n vertices with given matching number, and the unique tree with maximum Estrada index among the trees on n vertices with fixed diameter. For , we also determine the tree with maximum Estrada index among the trees on n vertices with maximum degree Δ. It gives a partial solution to the conjecture proposed by Ili? and Stevanovi? in Ref. [14].     

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

Let A _n (n ? 1) be the set of all integers x such that there exists a connected graph on n vertices with precisely x spanning trees. It was shown by Sedlá?ek that |A _n | grows faster than the linear function. In this paper, we show that |A _n | grows faster than \(\sqrt n e^{(2\pi /\sqrt 3 )\sqrt {n/\log n} } \) by making use of some asymptotic results for prime partitions. The result settles a question posed in J. Sedlá?ek, On the number of spanning trees of finite graphs, ?as. Pěst. Mat., 94 (1969), 217–221.     

Subdivisions of graphs: A generalization of paths and cycles

One of the basic results in graph theory is Dirac's theorem, that every graph of order n?3 and minimum degree ?n/2 is Hamiltonian. This may be restated as: if a graph of order n and minimum degree ?n/2 contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to (n-t)/2 if H has t components that are trees.We attempt a similar generalization of the Corrádi-Hajnal theorem that every graph of order ?3k and minimum degree ?2k contains k disjoint cycles. Again, this may be restated as: every graph of order ?3k and minimum degree ?2k contains a subdivision of kK₃. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order ?n and minimum degree ?n-k contains a subdivision of H.     

Packing and covering constants for certain families of trees. I

If ? denotes a family of rooted trees, let p_k(n) and c_k(n) denote the average value of the k-packing and k-covering numbers of trees in ? that have n nodes. We assume, among other things, that the generating function y of trees in ? satisfies a relation of the type y = x?(y) for some power series ?. We show that the limits of p_k(n)/n and c_k(n)/n as n → ∞ exist and we describe how to evaluate these limits.     

On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.     

Structure of cubic mapping graphs for the ring of Gaussian integers modulo n

Let ? _n [i] be the ring of Gaussian integers modulo n. We construct for ?n[i] a cubic mapping graph Γ(n) whose vertex set is all the elements of ?n[i] and for which there is a directed edge from a ∈ ?n[i] to b ∈ ?n[i] if b = a ³. This article investigates in detail the structure of Γ(n). We give suffcient and necessary conditions for the existence of cycles with length t. The number of t-cycles in Γ₁(n) is obtained and we also examine when a vertex lies on a t-cycle of Γ₂(n), where Γ₁(n) is induced by all the units of ?n[i] while Γ₂(n) is induced by all the zero-divisors of ?n[i]. In addition, formulas on the heights of components and vertices in Γ(n) are presented.     

On cographic regular matroids

The presentation of alternating permutatioas via labelled binary trees is used to define polynomials H_2n?1(x) as enumerating polynomials for the height of peaks in alternating permutations of length 2n?1. A divisibility property of the coefficients of these polynomials is proved, which generalizes and explains combinatirially a well-known property of the tangent numbers. Furthermore, a version of the exponential generating function for the H_2n?1(x) is given, leading to a new combinatorial interpretation of Dumont's modified Ghandi-polynomials.     

A note on the probabilistic analysis of patricia trees

We consider random PATRICIA trees constructed from n i.i.d. sequences of independent equiprobable bits. We study the height H_n (the maximal distance between the root and a leaf), and the minimal fill-up level F_n (the minimum distance between the root and a leaf). We give probabilistic proofs of .     

Dual topology of the Heisenberg motion groups

Let ? _n be the (2n + 1)-dimensional Heisenberg group, and let T ⁿ be the n-dimensional torus acting on ? _n by automorphisms. In this paper, we describe the space of admissible coadjoint orbits of the Heisenberg motion group G _n = T ⁿ ? ? _n and we determine the topology of this space. We show that the bijection between the unitary dual ? _n of G _n and its admissible coadjoint orbit space is a homeomorphism.     

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/1³ + 1/2³ + 1/3³ +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log₂ logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log₂ logn, then the weight is doubly-exponentially large in log₂ logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log₂ logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log₂ logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log₂ logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log₂ logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ .     

Upper bounds for permanents of (1, − 1)-matrices

Let Ω _n denote the set of alln×n (1, ? 1)-matrices. In 1974 E. T. H. Wang posed the following problems: Is there a decent upper bound for |perA| whenAσΩ _n is nonsingular? We recently conjectured that the best possible bound is the permanent of the matrix with exactlyn?1 negative entries in the main diagonal, and affirmed that conjecture by the study of a large class of matrices in Ω _n . Here we prove that this conjecture also holds for another large class of (1, ?1)-matrices which are all nonsingular. We also give an upper bound for the permanents of a class of matrices in Ω _n which are not all regular.     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.     

On the tree structure of the power digraphs modulo n

For any two positive integers n and k ? 2, let G(n, k) be a digraph whose set of vertices is {0, 1, …, n ? 1} and such that there is a directed edge from a vertex a to a vertex b if a ^k ≡ b (mod n). Let \(n = \prod\nolimits_{i = 1}^r {p_i^{{e_i}}} \) be the prime factorization of n. Let P be the set of all primes dividing n and let P ₁, P ₂ ? P be such that P ₁ ∪ P ₂ = P and P ₁ ∩ P ₂ = ?. A fundamental constituent of G(n, k), denoted by \(G_{{P_2}}^*(n,k)\), is a subdigraph of G(n, k) induced on the set of vertices which are multiples of \(\prod\nolimits_{{p_i} \in {P_2}} {{p_i}} \) and are relatively prime to all primes q ∈ P ₁. L. Somer and M. K?i?ek proved that the trees attached to all cycle vertices in the same fundamental constituent of G(n, k) are isomorphic. In this paper, we characterize all digraphs G(n, k) such that the trees attached to all cycle vertices in different fundamental constituents of G(n, k) are isomorphic. We also provide a necessary and sufficient condition on G(n, k) such that the trees attached to all cycle vertices in G(n, k) are isomorphic.