Search

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of K2n+1 into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large n. [ABSTRACT FROM AUTHOR]

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]

For a graph G, let vs(G) be the size of a largest induced matching of G. We prove that vs(G) ≥ n(G)/(⌈Δ/2⌇+1)(⌈Δ/2⌇+1) for every graph of sufficiently large maximum degree Δ and without isolated vertices. This bound is sharp. Moreover, there is a polynomial-time algorithm which computes induced matchings of the size stated above. [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]

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well-known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357-3363 (2012)). [ABSTRACT FROM AUTHOR]

We show that the maximum number of different sizes of maximal complete k -partite induced subgraphs of a graph G of sufficiently large order n is at least ( n − k + 1 ) − log 2 ( n − k + 1 ) − 4 and at most n − ⌊ log 2 ( n k ! ) ⌋ . We analyze some features of the structure of graphs with the maximum possible number of different sizes of maximal independent sets, and give best-possible estimates for K 1 , k -free graphs and regular graphs. [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]

Abstract: The domination number and the total domination number of a graph without an isolated vertex are among the most well-studied parameters in graph theory. While the inequality is an almost immediate consequence of the definition, the extremal graphs for this inequality are not well understood. Furthermore, even very strong additional assumptions do not allow us to improve the inequality by much. In the present paper we consider the relation of and for cubic graphs of large girth. Clearly, in this case is at least where is the order of . If is close to , then this forces a certain structure within . We exploit this structure and prove an upper bound on , which depends on the value of . As a consequence, we can considerably improve the inequality for cubic graphs of large girth. [Copyright &y& Elsevier]

Abstract: We prove that and for every triangle-free graph with maximum degree at most , where is the independence number and is the matching number of , respectively. These results are sharp for a graph on vertices. Furthermore we show for -free graphs, where is the chromatic number and is the clique number of , respectively. [Copyright &y& Elsevier]

We prove that a cubic graph with m edges has an induced matching with at least M/9 edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (SIAM J. Discrete Math., 26 (2012), pp. 1383-1411) and solves a conjecture of Henning and Rautenbach. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

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]