A tight bound on the min-ratio edge-partitioning problem of a tree

In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k≤n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight.     

Approximating k-hop minimum-spanning trees

Given a complete graph on~n nodes with metric edge costs, the minimum-costk-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most k edges. We present an algorithm that computes such a tree of total expected cost times that of a minimum-cost k-hop spanning-tree.     

Pebble game algorithms and sparse graphs

A multi-graph G on n vertices is (k,?)-sparse if every subset of n^′?n vertices spans at most kn^′-? edges. G is tight if, in addition, it has exactly kn-? edges. For integer values k and ?∈[0,2k), we characterize the (k,?)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,?)-pebble games.     

Efficient implementation of a shifting algorithm

An efficient implementation of the shifting algorithm [2] for min-max tree partitioning is given. The complexity is reduced from ORk³ + kn) to O(Rk(k + log d) + n) where a tree of n vertices, radius, of R edges, and maximum degree d is partitioned into k + 1 subtrees. The improvement is mainly due to the new junction tree data structure which suggests a succinct representation for subsets of edges, of a given tree, that preserves the interrelation betqween the edges on the tree.     

The Erd s-Sós conjecture for graphs of girth 5

We prove that every graph of girth at least 5 with minimum degree δ k/2 contains every tree with k edges, whose maximum degree does not exceed the maximum degree of the graph. An immediate consequence is that the famous Erd s-Sós Conjecture, saying that every graph of order n with more than n(k − 1)/2 edges contains every tree with k edges, is true for graphs of girth at least 5.     

On domination and reinforcement numbers in trees

The reinforcement number of a graph is the smallest number of edges that have to be added to a graph to reduce the domination number. We introduce the k-reinforcement number of a graph as the smallest number of edges that have to be added to a graph to reduce the domination number by k. We present an O(k²n) dynamic programming algorithm for computing the maximum number of vertices that can be dominated using γ(G)-k dominators for trees. A corollary of this is a linear-time algorithm for computing the k-reinforcement number of a tree. We also discuss extensions and related problems.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Solving Non-Homogeneous Nested Recursions Using Trees

The solutions to certain nested recursions, such as Conolly’s C(n) = C(n?C(n?1)) + C(n?1?C(n?2)), with initial conditions C(1) = 1, C(2) = 2, have a well-established combinatorial interpretation in terms of counting leaves in an infinite binary tree. This tree-based interpretation, and its generalization to a similar k-term nested recursion, only apply to homogeneous recursions and only solve each recursion for one set of initial conditions determined by the tree. In this paper, we extend the tree-based interpretation to solve a non-homogeneous version of the k-term recursion that includes a constant term. To do so we introduce a tree-grafting methodology that inserts copies of a finite tree into the infinite k-ary tree associated with the solution of the corresponding homogeneous k-term recursion. This technique also solves the given non-homogeneous recursion with various sets of initial conditions.     

Hamilton ?-cycles in uniform hypergraphs

We say that a k-uniform hypergraph C is an ?-cycle if there exists a cyclic ordering of the vertices of C such that every edge of C consists of k consecutive vertices and such that every pair of consecutive edges (in the natural ordering of the edges) intersects in precisely ? vertices. We prove that if 1??<k and k−? does not divide k then any k-uniform hypergraph on n vertices with minimum degree at least contains a Hamilton ?-cycle. This confirms a conjecture of Hàn and Schacht. Together with results of Rödl, Ruciński and Szemerédi, our result asymptotically determines the minimum degree which forces an ?-cycle for any ? with 1??<k.     

An approximate version of the Loebl-Komlós-Sós conjecture

Loebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have degree at least some k∈N, then every tree with at most k edges is a subgraph of G. Our main result is an approximate version of this conjecture for large enough n=|V(G)|, assumed that n=O(k).Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(Tk,Tm)?k+m+o(k+m), as k+m→∞.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Finding odd cycle transversals

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.     

The Harmonious Chromatic Number of Deep and Wide Complete n- ary Trees

The harmonious chromatic number of a graph G is the least number of colors which can be used to color V(G) such that adjacent vertices are colored differently and no two edges have the same color pair on their vertices. Unsolved Problem 17.5 of Graph Coloring Problems by Jensen and Toft asks for the harmonious chromatic number of T_m,n the complete n-ary tree on m levels. Let q be the number of edged of T_m,n and k be the smallest positive integer such that the binomial coefficient C(k, 2) ≥ q. We show that for all sufficiently large m, n, the harmonious chromatic number of T_m,n is at most k + 1, and that many such T_m,n have harmonious chromatic number k.     

Achievable sets, brambles, and sparse treewidth obstructions

One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors.     

An approximate version of the tree packing conjecture

We prove that for any pair of constants ? > 0 and Δ and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most Δ, and with at most (_n²) edges in total packs into \({K_{(1 + \varepsilon )n}}\). This implies asymptotic versions of the Tree Packing Conjecture of Gyárfás from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

The Erdös-Sós conjecture for spiders

A classical result on extremal graph theory is the Erdös-Gallai theorem: if a graph on n vertices has more than edges, then it contains a path of k edges. Motivated by the result, Erdös and Sós conjectured that under the same condition, the graph should contain every tree of k edges. A spider is a rooted tree in which each vertex has degree one or two, except for the root. A leg of a spider is a path from the root to a vertex of degree one. Thus, a path is a spider of 1 or 2 legs. From the motivation, it is natural to consider spiders of 3 legs. In this paper, we prove that if a graph on n vertices has more than edges, then it contains every k-edge spider of 3 legs, and also, every k-edge spider with no leg of length more than 4, which strengthens a result of Wo?niak on spiders of diameter at most 4.     

Reconstructing graphs from size and degree properties of their induced k-subgraphs

As a variant of the famous graph reconstruction problem we characterize classes of graphs of order n such that all their induced subgraphs on k?n vertices satisfy some property related to the number of edges or to the vertex degrees.We give complete solutions for the properties (i) to be regular, (ii) to be regular modulo m?2 or (iii) to have one of two possible numbers of edges. Furthermore, for an order n large enough, we give solutions for the properties (iv) to be bi-regular or (v) to have a bounded difference between the maximum and the minimum degree.     

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)}$ .