TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sat, 10 Jun 2023 15:15:16 GMT2023-06-10T15:15:16Z5031Induced matchings in subcubic planar graphshttp://hdl.handle.net/11420/7626Title: Induced matchings in subcubic planar graphs
Authors: Kang, Ross J.; Mnich, Matthias; Müller, Tobias
Abstract: We present a linear-time algorithm that, given a planar graph with m edges and maximum degree 3, finds an induced matching of size at least m/9. This is best possible.
Mon, 22 Nov 2010 00:00:00 GMThttp://hdl.handle.net/11420/76262010-11-22T00:00:00ZLogical limit laws for minor-closed classes of graphshttp://hdl.handle.net/11420/2945Title: Logical limit laws for minor-closed classes of graphs
Authors: Heinig, Peter; Müller, Tobias; Noy, Marc; Taraz, Anusch
Abstract: Let G be an addable, minor-closed class of graphs. We prove that the zero-one law holds in monadic second-order logic (MSO) for the random graph drawn uniformly at random from all connected graphs in G on n vertices, and the convergence law in MSO holds if we draw uniformly at random from all graphs in G on n vertices. We also prove analogues of these results for the class of graphs embeddable on a fixed surface, provided we restrict attention to first order logic (FO). Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface S. We also prove that the closure of the set of limiting probabilities is always the finite union of at least two disjoint intervals, and that it is the same for FO and MSO. For the classes of forests and planar graphs we are able to determine the closure of the set of limiting probabilities precisely. For planar graphs it consists of exactly 108 intervals, each of the same length ≈5.39⋅10 −6 . Finally, we analyse examples of non-addable classes where the behaviour is quite different. For instance, the zero-one law does not hold for the random caterpillar on n vertices, even in FO.
Tue, 01 May 2018 00:00:00 GMThttp://hdl.handle.net/11420/29452018-05-01T00:00:00ZInduced matchings in subcubic planar graphshttp://hdl.handle.net/11420/4544Title: Induced matchings in subcubic planar graphs
Authors: Kang, Ross J.; Mnich, Matthias; Müller, Tobias
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/11420/45442012-01-01T00:00:00Z