Search

A key feature of Simonovits' proof of the classic Erdőos--Pósa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to A-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erdős--Pósa property for long and for even A-paths. We also show that even A-paths do not have the edge-Erdős--Pósa property. [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]

For a graph G, let νs(G) be the strong matching number of G. We prove the sharp bound νs(G) ≥ n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This result implies a strengthening of a consequence, namely, νs(G) ≥ m(G)/18 for such graphs and νs(G) ≥ m(G)/20 for a graph of maximum degree 4, of the well-known conjecture of Erdős and Nešetřil, which says that the strong chromatic index χ's(G) of a graph G is at most 5/4Δ(G)², since νs(G) ≥ m(G)/χ's(G) and n(G) ≥ 2m(G)/Δ(G). This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size. [ABSTRACT FROM AUTHOR]

We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solves the problem for Cartesian powers of arbitrary graphs. In detail, let G be a connected graph on k vertices, Gn be the nth Cartesian power of G, αi be the number of vertices of degree i of G, λ be a positive real number, and Gnp be the graph obtained from Gn by deleting every edge independently with probability 1 − p. If ∑i αi(1 − p)i = λ 1/n , then limn→∞ ℙ[Gnp is connected] = exp(−λ). This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of G itself, but only on the degree sequence of the graph. [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]