Unlabeled trees: Distribution of the maximum degree

Pick a tree uniformly at random from among all unlabeled trees on n vertices, and let X_n be the maximum of the degrees of its vertices. For any fixed integer d, as n→∞, where μ_n = c₁ log n, where {μ_n} : = μ_n – ?μ? denotes the fractional part of μ_n and where c_o, c₁, and η_∞ are knnown constants, givenb approximately by c₀ = 3.262 …, c₁ = 0.9227 …, and η_∞ = 0.3383…. © 1994 John Wiley & Sons, Inc.     

The generalized Randić index of trees

The generalized Randi?; index of a tree T is the sum over the edges of T of where is the degree of the vertex x in T. For all , we find the minimal constant such that for all trees on at least 3 vertices, , where is the number of vertices of T. For example, when . This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with . More generally, fix and define , where is the number of leaves of T. We determine the best constant such that for all trees on at least 3 vertices, . Using these results one can determine (up to terms) the maximal Randi?; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007     

Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube

A caterpillar is a tree having a path that contains all vertices of of degree at least 3. We show in this article that every balanced caterpillar with maximum degree 3 and 2ⁿ vertices is a subgraph of the n‐dimensional hypercube. This solves a long‐standing open problem and generalizes a result of Havel and Liebl (1986), who considered only such caterpillars that have a path containing all vertices of degree at least 2.     

From steiner centers to steiner medians

The Steiner distance of set S of vertices in a connected graph G is the minimum number of edges in a connected subgraph of G containing S. For n ≥ 2, the Steiner n-eccentricity e_n(v) of a vertex v of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contain v. The Steiner n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. The Steiner n-distance of a vertex v of G is defined as . The Steiner n-median of G is the subgraph of G induced by the vertices of G of minimum Steiner n-distance. Known algorithms for finding the Steiner n-centers and Steiner n-medians of trees are used to show that the distance between the Steiner n-centre and Steiner n-median of a tree can be arbitrarily large. Centrality measures that allow every vertex on a shortest path from the Steiner n-center to the Steiner n-median of a tree to belong to the “center” with respect to one of these measures are introduced and several proeprties of these centrality measures are established. © 1995 John Wiley & Sons, Inc.     

On the total variation distance between the binomial random graph and the random intersection graph

When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karoński, Scheinerman, and Singer‐Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and Singer‐Cohen showed that the total variation distance between the random graph and the Erdös‐Rényi graph tends to 0 for any if , where is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any whenever .     

Smallest graphs with given generalized quaternion automorphism group

For , a smallest graph whose automorphism group is isomorphic to the generalized quaternion group is constructed. If , then such a graph has vertices and edges. In the special case when , a smallest graph has 16 vertices but 44 edges.     

A remark on N. Korevaar's concavity maximum principle and on the asymptotic uniqueness of solutions to the plasma problem

Recently N. Korevaar developed a method of proving that solutions to elliptic and parabolic boundary value problems on convex domains ω ? R ⁿ are convex functions. He introduced a concavity function and used the classical maximum principle to prove that C ? 0 on ω × ω, i.e. that u is convex. Both he and independently L. Caffarelli and J. Spruck applied this method successfully to various boundary value problems. In this note we weaken the assumptions of their theorems and obtain some interesting new applications which are not covered by their previous results [CS, Ko].     

The decycling number and maximum genus of cubic graphs

Let and denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is , where c and are the number of components of and the number of edges in , respectively. Therefore, S is minimum if and only if is minimum. As an application, this leads to a lower bound for of a k‐regular graph G. In many cases this bound may be sharp.     

On minimum bisection and related cut problems in trees and tree‐like graphs

Minimum bisection denotes the NP‐hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. It is intuitively clear that graphs with a somewhat linear structure are easy to bisect, and therefore our aim is to relate the minimum bisection width of a bounded‐degree graph G to a parameter that measures the similarity between G and a path. First, for trees, we use the diameter and show that the minimum bisection width of every tree T on n vertices satisfies . Second, we generalize this to arbitrary graphs with a given tree decomposition  and give an upper bound on the minimum bisection width that depends on how close  is to a path decomposition. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.     

Generalized Digital Trees and Their Difference—Differential Equations

Consider a tree partitioning process in which n elements are split into b at the root of a tree (b a design parameter), the rest going recursively into two subtrees with a binomial probability distribution. This extends some familiar tree data structures of computer science like the digital trie and the digital search tree. The exponential generating function for the expected size of the tree satisfies a difference–differential equation of order b, The solution involves going to ordinary (rather than exponential) generating functions, analyzing singularities by means of Mellin transforms and contour integration. The method is of some general interest since a large number of related problems on digital structures can be treated in this way via singularity analysis of ordinary generating functions.     

On hitting all maximum cliques with an independent set

We prove that every graph G for which has an independent set I such that ω(G?I)<ω(G). It follows that a minimum counterexample G to Reed's conjecture satisfies and hence also . This also applies to restrictions of Reed's conjecture to hereditary graph classes, and in particular generalizes and simplifies King, Reed and Vetta's proof of Reed's conjecture for line graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 32–37, 2010     

Hamilton Cycles,Minimum Degree,and Bipartite Holes

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large “bipartite hole” (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erd?s. In detail, an ‐bipartite‐hole in a graph G consists of two disjoint sets of vertices S and T with and such that there are no edges between S and T ; and is the maximum integer r such that G contains an ‐bipartite‐hole for every pair of nonnegative integers s and t with . Our central theorem is that a graph G with at least three vertices is Hamiltonian if its minimum degree is at least . From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of k edge‐disjoint Hamilton cycles. We see that for dense random graphs , the probability of failing to contain many edge‐disjoint Hamilton cycles is . Finally, we discuss the complexity of calculating and approximating .     

The minimum number of triangles covering the edges of a graph

Suppose that a connected graph G has n vertices and m edges, and each edge is contained in some triangle of G. Bounds are established here on the minimum number t_min(G) of triangles that cover the edges of G. We prove that ?(n - 1)/2? ? t_min(G) with equality attained only by 3-cactii and by strongly related graphs. We obtain sharp upper bounds: if G is not a 4-clique, then. The triangle cover number t_min(G) is also bounded above by Γ(G) = m - n + c, the cyclomatic number of a graph G of order n with m edges and c connected components. Here we give a combinatorial proof for t_min(G) ? Γ(G) and characterize the family of all extremal graphs satisfying equality.     

Weighted (LF)-spaces of Continuous Functions

.     

Rainbow Arborescence in Random Digraphs

We consider the Erd?s–Rényi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let be a graph with m edges obtained after m steps of this process. Each edge () of independently chooses a color, taken uniformly at random from a given set of colors. We stop the process prematurely at time M when the following two events hold: has at most one vertex that has in‐degree zero and there are at least distinct colors introduced ( if at the time when all edges are present there are still less than colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether has a rainbow arborescence (i.e. a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colors). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is “yes.”     

A central limit theorem on gln(fq)

.     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

On the Number of k‐Dominating Independent Sets

We study the existence and the number of k‐dominating independent sets in certain graph families. While the case namely the case of maximal independent sets—which is originated from Erd?s and Moser—is widely investigated, much less is known in general. In this paper we settle the question for trees and prove that the maximum number of k‐dominating independent sets in n‐vertex graphs is between and if , moreover the maximum number of 2‐dominating independent sets in n‐vertex graphs is between and . Graph constructions containing a large number of k‐dominating independent sets are coming from product graphs, complete bipartite graphs, and finite geometries. The product graph construction is associated with the number of certain Maximum Distance Separable (MDS) codes.     

Simultaneous diagonal flips in plane triangulations

Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with n ≥ 6 vertices has a simultaneous flip into a 4‐connected triangulation, and that the set of edges to be flipped can be computed in (n) time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n‐vertex triangulations, there exists a sequence of (logn) simultaneous flips to transform one into the other. Moreover, Ω(log n) simultaneous flips are needed for some pairs of triangulations. The total number of edges flipped in this sequence is (n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least edges. On the other hand, every simultaneous flip has at most n ? 2 edges, and there exist triangulations with a maximum simultaneous flip of edges. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 307–330, 2007