Branching structure and maximum degree of an evolving random tree

We introduce the concept of an evolving random tree. The proposed model is a combination of a preferential attachment model and a uniform model. We consider the branch structure and maximum degree of the evolving random tree, which can partially explain the robustness under random attack and the vulnerability to targeted attack in the world wide web.     

On the largest tree of given maximum degree in a connected graph

We prove that every connected graph G contains a tree T of maximum degree at most k that either spans G or has order at least kδ(G) + 1, where δ(G) is the minimum degree of G. This generalizes and unifies earlier results of Bermond [1] and Win [7]. We also show that the square of a connected graph contains a spanning tree of maximum degree at most three.     

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.     

Coloring graphs of various maximum degree from random lists

Let G = G(n) be a graph on n vertices with maximum degree Δ =Δ (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k‐subsets of a color set of size . Such a list assignment is called a random ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as n →∞) of the existence of a proper coloring φ of G, such that for every vertex v of G, a so‐called L‐coloring. We give various lower bounds on σ, in terms of n, k, and Δ, which ensures that with probability tending to 1 as n →∞ there is an L‐coloring of G. In particular, we show, for all fixed k and growing n, that if and , then the probability that G has an L‐coloring tends to 1 as . If and , then the same conclusion holds provided that . We also give related results for other bounds on Δ, when k is constant or a strictly increasing function of n.     

The maximum surplus before ruin and related problems in a jump-diffusion renewal risk process

In this paper, we investigate a Sparre Andersen risk model perturbed by diffusion with phase-type inter-claim times. We mainly study the distribution of maximum surplus prior to ruin. A matrix form of integro-differential equation for this quantity is derived, and its solution can be expressed as a linear combination of particular solutions of the corresponding homogeneous integro-differential equations. By using the divided differences technique and nonnegative real part roots of Lundberg’s equation, the explicit Laplace transforms of particular solutions are obtained. Specially, we can deduce closed-form results as long as the individual claim size is rationally distributed. We also give a concise matrix expression for the expected discounted dividend payments under a barrier dividend strategy. Finally, we give some examples to present our main results.     

On the maximal energy tree with two maximum degree vertices

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacent matrix.For Δ?3 and t?3, denote by T_a(Δ,t) (or simply T_a) the tree formed from a path P_t on t vertices by attaching Δ-1P₂’s on each end of the path P_t, and T_b(Δ,t) (or simply T_b) the tree formed from P_t+2 by attaching Δ-1P₂’s on an end of the P_t+2 and Δ-2P₂’s on the vertex next to the end.In Li et al.(2009) [16] proved that among trees of order n with two vertices of maximum degree Δ, the maximal energy tree is either the graph T_a or the graph T_b, where t=n+4-4Δ?3.However, they could not determine which one of T_a and T_b is the maximal energy tree.This is because the quasi-order method is invalid for comparing their energies.In this paper, we use a new method to determine the maximal energy tree.It turns out that things are more complicated.We prove that the maximal energy tree is T_b for Δ?7 and any t?3, while the maximal energy tree is T_a for Δ=3 and any t?3.Moreover, for Δ=4, the maximal energy tree is T_a for all t?3 but one exception that t=4, for which T_b is the maximal energy tree.For Δ=5, the maximal energy tree is T_b for all t?3 but 44 exceptions that t is both odd and 3?t?89, for which T_a is the maximal energy tree.For Δ=6, the maximal energy tree is T_b for all t?3 but three exceptions that t=3,5,7, for which T_a is the maximal energy tree.One can see that for most cases of Δ, T_b is the maximal energy tree,Δ=5 is a turning point, and Δ=3 and 4 are exceptional cases, which means that for all chemical trees (whose maximum degrees are at most 4) with two vertices of maximum degree at least 3, T_a has maximal energy, with only one exception T_a(4,4).     

The Witt ring kernel for a fourth degree field extension and related problems

In the first part of this paper we compute the Witt ring kernel for an arbitrary field extension of degree 4 and characteristic different from 2 in terms of the coefficients of a polynomial determining the extension. In the case where the lower field is not formally real we prove that the intersection of any power n of its fundamental ideal and the Witt ring kernel is generated by n-fold Pfister forms.In the second part as an application of the main result we give a criterion for the tensor product of quaternion and biquaternion algebras to have zero divisors. Also we solve the similar problem for three quaternion algebras.In the last part we obtain certain exact Witt group sequences concerning dihedral Galois field extensions. These results heavily depend on some similar cohomological results of Positselski, as well as on the Milnor conjecture, and the Bloch-Kato conjecture for exponent 2, which was proven by Voevodsky.     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

The irredundance number and maximum degree of a graph

A vertex η in a subset X of vertices of an undirected graph is redundant if its closed neighborhood is contained in the union of closed neighborhoods of vertices of X-{η}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X-{η}. The irredundance number ir(G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) ? n/(2Δ-1) for a graph G having n vertices and maximum degree Δ.     

The uniform random tree in a Brownian excursion

Summary To any Brownian excursione with duration (e) and anyt ₁, ...,t _p [0,(e)], we associate a branching tree withp branches denoted byT _p (e, t ₁,...,t _p ), which is closely related to the structure of the minima ofe. Our main theorem states that, ife is chosen according to the Itô measure and (t ₁, ...,t _p ) according to Lebesgue measure on [0,(e)] ^p , the treeT _p (e, t ₁, ...,t _p ) is distributed according to the uniform measure on the set of trees withp branches. The proof of this result yields additional information about the subexcursions ofe corresponding to the different branches of the tree, thus generalizing a well-known representation theorem of Bismut. If we replace the Itô measure by the law of the normalized excursion, a simple conditioning argument leads to another remarkable result originally proved by Aldous with a very different method.     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The maximum degree of a minimally hamiltonian-connected graph

We determine the possible maximum degrees of a minimally hamiltonian-connected graph with a given order. This answers a question posed by Modalleliyan and Omoomi in 2016. We also pose two unsolved problems.     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The distribution of degrees in a large random tree

For labeled trees, Rényi showed that the probability that an arbitrary point of a random tree has degree k approaches l/e(k?l)!. For unlabeled trees, the answer is different because the number of ways to label a given tree depends on the order of its automorphism group. Using arguments involving combinatorial enumeration and asymptotics, we evaluate the corresponding probabilities for large unlabeled trees.     

Isotropic random walks in a tree

Summary Let T be an infinite homogeneous tree of order a+1. We study Markov chains {X _n} in T whose transition functions p(x, y)=A[d(x,y)] depend only on the shortest distance between x and y in the graph. The graph T can be represented as a symmetric space of a p-adic matrix group; we prove a series of results using essentially the spherical functions of this symmetric space. Theorem 1. d(X _n,x) n a.s., where >0 if A(0) 1, X ₀=x. Assuming {X _n} is strongly aperiodic, Theorem 2. p ₂(x, y)CRⁿ/n^3/2 for fixed x, y where R=(d) A(d)<1, and if E[d(X₁, X₀)²]<, Theorem 3. R(1–u, x, y) = (1–u)ⁿp_n(x, y)=Ca^–d[exp(–du/)+o_d(1)] as d=d(x,y) uniformly for 0u2. Using Theorem 3, we calculate the Martin boundary Dirichlet kernel of p(x, y) on T, which turns out to be independent of {itA(d)}. We also consider a stepping-stone model of a randomly-mating-and-migrating population on the nodes of T. If initially all individuals are distinct, then in generation n approximately half of the individuals of a given type are within n of a typical one and essentially all are within 2n.This work was partially supported by the National Science Foundation under grant number MCS 75-08098-A01For the academic year 1977–78: Department of Mathematics GN-50, University of Washington, Seattle, Washington 98195 USA     

The Ramsey number of a graph with bounded maximum degree

The Ramsey number of a graph G is the least number t for which it is true that whenever the edges of the complete graph on t vertices are colored in an arbitrary fashion using two colors, say red and blue, then it is always the case that either the red subgraph contains G or the blue subgraph contains G. A conjecture of P. Erdös and S. Burr is settled in the affirmative by proving that for each d ≥ 1, there exists a constant c so that if G is any graph on n vertices with maximum degree d, then the Ramsey number of G is at most cn.