Search

We prove that if T1, ..., Tn is a sequence of bounded degree trees such that Ti has i vertices, then Kn has a decomposition into T1, ..., Tn. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees (in fact, we can allow the first o.n/ trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemerédi's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions. [ABSTRACT FROM AUTHOR]

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by $$c_\mathrm{ind}(G)$$ . We prove that if G is an r-regular graph of order n, then $$c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}$$ and we prove that if G is a cubic, claw-free graph on order n, then $$c_\mathrm{ind}(G) > \frac{13}{20}n$$ and this bound is asymptotically best possible. [ABSTRACT FROM AUTHOR]

If $$G$$ is a claw-free Hamiltonian graph of order $$n$$ and maximum degree $$\Delta $$ with $$\Delta \ge 24$$ , then $$G$$ has cycles of at least $$\min \left\{ n,\left\lceil \frac{3}{2}\Delta \right\rceil \right\} -2$$ many different lengths. [ABSTRACT FROM AUTHOR]

We characterize the graphs for which the independence number equals the packing number. As a consequence we obtain simple structural descriptions of the graphs for which (i) the distance- k -packing number equals the distance- 2 k -packing number, and (ii) the distance- k -matching number equals the distance- 2 k -matching number. This last result considerably simplifies and extends previous results of Cameron and Walker (2005). For positive integers k 1 and k 2 with k 1 < k 2 and ⌈ ( 3 k 2 + 1 ) / 2 ⌉ ≤ 2 k 1 + 1 , we prove that it is NP-hard to determine for a given graph whether its distance- k 1 -packing number equals its distance- k 2 -packing number. [ABSTRACT FROM AUTHOR]

The Gallai graph Gal ( G ) of a graph G has the edges of G as its vertices, and two distinct vertices e and f of Gal ( G ) are adjacent in Gal ( G ) if the edges e and f of G are adjacent in G but do not span a triangle in G . In the present paper we characterize those graphs whose Gallai graphs are forests or trees, respectively. [ABSTRACT FROM AUTHOR]

Abstract: The intersection graphs of stars in some tree are known as substar graphs. In this paper we give a characterization of substar graphs by the list of minimal forbidden induced subgraphs. This corrects a flaw in the main result of Chang, Jacobson, Monma and West (1993) and this leads to a different list of minimal forbidden induced subgraphs. [Copyright &y& Elsevier]

As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the in- tersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap. [ABSTRACT FROM AUTHOR]