Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

On the spectral radius of weighted trees with given number of pendant vertices and a positive weight set

Let 𝒯(n,?r;?W _n?1) be the set of all n-vertex weighted trees with r vertices of degree 2 and fixed positive weight set W _n?1, 𝒫(n,?γ;?W _n?1) the set of all n-vertex weighted trees with q pendants and fixed positive weight set W _n?1, where W _n?1?=?{w ₁,?w ₂,?…?,?w _n?1} with w ₁???w ₂???···???w _n?1?>?0. In this article, we first identify the unique weighted tree in 𝒯(n,?r;?W _n?1) with the largest adjacency spectral radius. Then we characterize the unique weighted trees with the largest adjacency spectral radius in 𝒫(n,?γ;?W _n?1).     

The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices

In this paper, we consider the conjugate-Toeplitz (CT) and conjugate-Hankel (CH) matrices. It is proved that the inverse of these special matrices can be expressed as the sum of products of lower and upper triangular matrices. Firstly, we get access to the explicit inverse of conjugate-Toeplitz matrix. Secondly, the decomposition of the inverse is obtained. Similarly, the formulae and the decomposition on inverse of conjugate-Hankel are provided. Thirdly, the stability of the inverse formulae of CT and CH matrices are discussed. Finally, examples are provided to verify the feasibility of the algorithms provided in this paper.     

New upper bounds on the spectral radius of trees with the given number of vertices and maximum degree

This paper studies the problem of estimating the spectral radius of trees with the given number of vertices and maximum degree. We obtain the new upper bounds on the spectral radius of the trees, and the results are the best upper bounds expressed by the number of vertices and maximum degree, at present.     

Asymptotic formulas for the number of oriented graphs

Wille found an asymptotic approximation to r(n, q), the number of unlabeled oriented graphs on n points and q directed lines, for a wide interval of q and conjectured that, for given n, the maximum of r(n, q) occurs at $\text{q = [}\text{2(N + 1)}\text{3}\text{]}$. We find the (different) asymptotic approximation to r(n, q) valid for the remaining interval of q and prove Wille's conjecture for all large n.     

Extremal energies of trees with a given domination number

The energy of a graph is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. Let T(n,γ) be the set of trees of order n and with domination number γ. In this paper, we characterize the tree from T(n,γ) with the minimal energy, and determine the tree from T(n,γ) where n=kγ with maximal energy for .     

Graphs with given odd sets and the least number of vertices

This note presents a solution to the following problem posed by Chen, Schelp, and Šoltés: find a simple graph with the least number of vertices for which only the degrees of the vertices that appear an odd number of times are given. © 1997 John Wiley & Sons, Inc.     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

On the number of vertices of given degree in a random graph

This note can be treated as a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G ∈ ??(n, p) asymptotically has a normal distribution.     

Graphs with given number of cut vertices and extremal Merrifield-Simmons index

The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by G(n,k) the set of connected graphs with n vertices and k cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield-Simmons index, respectively, among all graphs in G(n,k) for all possible k values.     

Distance spectral radius of trees with fixed number of pendent vertices

The distance spectral radius ρ(G)$\rho (G)$ of a graph G   is the largest eigenvalue of the distance matrix D(G)$D(G)$. In this paper, we characterize the graph with minimum distance spectral radius among trees with fixed number of pendent vertices.     

An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

This paper presents a new edge-swap heuristic for generating spanning trees with a minimum number of branch vertices, i.e. vertices of degree greater than two. This problem was introduced in Gargano et al. (Lect Notes Comput Sci 2380:355–365, 2002) and has been called the minimum branch vertices problem by Cerulli et al. (Comput Optim Appl 42:353–370, 2009). The heuristic starts with a random spanning tree and iteratively reduces the number of branch vertices by swapping tree edges with edges not currently in the tree. It can be easily implemented as a multi-start heuristic. We report on extensive computational experiments comparing single-start and multi-start variants on our heuristic with other heuristics previously proposed in the literature.     

The extremal irregularity of connected graphs with given number of pendant vertices

Czechoslovak Mathematical Journal - The irregularity of a graph G = (V, E) is defined as the sum of imbalances ∣du ? dv∣ over all edges uv ∈ E, where du denotes the degree...     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.