Distribution of points by degree and orbit size in a large random tree

Using generating functions and asymptotic techniques, the probability that in a large random tree a point is of degree r and an orbit of size s for r ≤ 7 and s ≤ 7 is calculated. For example, it is found that about 17% of the points of a random tree are fixed and have degree one. This method is readily applied to different types of trees.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Irredundance, secure domination and maximum degree in trees

It is shown that the lower irredundance number and secure domination number of an n vertex tree T with maximum degree Δ?3, are bounded below by 2(n+1)/(2Δ+3)(T≠K_1,Δ) and (Δn+Δ-1)/(3Δ-1), respectively. The bounds are sharp and extremal trees are exhibited.     

Independence,clique size and maximum degree

It was shown before that ifG is a graph of maximum degreep containing no cliques of the sizeq then the independence ratio is greater than or equal to 2 / (p +q). We shall discuss here some extreme cases of this inequality. Dedicated to Paul Erdős on his seventieth birthday     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

On size, order, diameter and minimum degree

Let G be a finite connected graph. We give an asymptotically tight upper bound on the size of G in terms of order, diameter and minimum degree. Our result is a strengthening of an old classical theorem of Ore [Diameters in graphs, J. Combin. Theory, 5 (1968), 75–81] if minimum degree is prescribed and constant.     

Algebraic connectivity and degree sequences of trees

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector.     

Finite size percolation in regular trees

In the context of percolation in a regular tree, we study the size of the largest cluster and the length of the longest run starting within the first d generations. As d tends to infinity, we prove almost sure and weak convergence results.     

Connectivity,toughness, spanning trees of bounded degree,and the spectrum of regular graphs

The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity.     

Starlike trees whose maximum degree exceed 4 are determined by their Q-spectra

Let $A(G)$ and $D(G)$ be the adjacency matrix and the degree matrix of a graph $G$, respectively. The matrix $D(G)+A(G)$ is called the signless Laplacian matrix of $G$. The spectrum of the matrix $D(G)+A(G)$ is called the Q-spectrum of $G$. A graph is said to be determined by its Q-spectrum if there is no other non-isomorphic graph with the same Q-spectrum. In this paper, we prove that all starlike trees whose maximum degree exceed $4$ are determined by their Q-spectra.     

The Laplacian spectral radius of trees and maximum vertex degree

Let $\Delta \left(T\right)$ and $\mu \left(T\right)$ denote the maximum degree and the Laplacian spectral radius of a tree $T$, respectively. In this paper we prove that for two trees $T_1$ and $T_2$ on $n(n\ge 21)$ vertices, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$, and the bound “$\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$” is the best possible. We also prove that for two trees $T_1$ and $T_2$ on $2k(k\ge 4)$ vertices with perfect matchings, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{k}{2}?+2$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$.     

On the degree distribution of the nodes in increasing trees

Simple families of increasing trees can be constructed from simply generated tree families, if one considers for every tree of size n all its increasing labellings, i.e., labellings of the nodes by distinct integers of the set {1,…,n} in such a way that each sequence of labels along any branch starting at the root is increasing. Three such tree families are of particular interest: recursive trees, plane-oriented recursive trees and binary increasing trees. We study the quantity degree of node j in a random tree of size n and give closed formulae for the probability distribution and all factorial moments for those subclass of tree families, which can be constructed via a tree evolution process. Furthermore limiting distribution results of this parameter are given, which completely characterize the phase change behavior depending on the growth of j compared to n.     

Counting and coding identity trees with fixed diameter and bounded degree

Identity trees with bounded maximum degree play a fundamental role in applications-oriented problems, especially when the trees are classified by their diameters. This paper offers results related to enumeration of such tree classes obtained by extending the methods of Gordon and Kennedy [The counting and coding of trees of fixed diameter, SIAM J. Appl. Math. 28 376–398 (1975)]. We set our results into the context of other enumerative work on identity trees.We derive formulae for the numbers of identity trees of various types, with fixed diameter and maximum degree. This then leads to asymptotic formulae (for large diameter). By combining these with formulae derived by Gordon and Kennedy [loc. cit.] we obtain the asymptotic fractions of identity trees among trees in various classes. These fractions are juxtaposed with asymptotic results that have appeared elsewhere.Our final section derives algorithms for integer coding and decoding identity trees in a way that is highly convenient for computer applications.     

Helly EPT graphs on bounded degree trees: Characterization and recognition

The edge-intersection graph of a family of paths on a host tree is called an $EPT$ graph. When the tree has maximum degree $h$, we say that the graph is $[h,2,2]$. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly $[h,2,2]$. In this paper, we present a family of $EPT$ graphs called gates which are forbidden induced subgraphs for $[h,2,2]$ graphs. Using these we characterize by forbidden induced subgraphs the Helly $[h,2,2]$ graphs. As a byproduct we prove that in getting a Helly $EPT$-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly $[h,2,2]$ graphs based on their decomposition by maximal clique separators.     

The largest character degree,conjugacy class size and subgroups of finite groups

Let G be a finite group, let b(G) denote the largest irreducible character degree of the group G and let bcl(G) denote the largest conjugacy class size of the group G. We study the relations between the sizes of the nilpotent and solvable subgroups of G and b(G). We also study the relations between the sizes of the nilpotent and solvable subgroups of G and bcl(G).