Select All    Deselect All << 1 >> List View  | Citations  | Details
 Araujo, J., Ducoffe, G., Nisse, N., & Suchan, K. (2018). On interval number in cycle convexity. Discret. Math. Theor. Comput. Sci., 20(1), 35 pp. Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomial-time algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q – 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems. Permanent link  | Save citation:  RTF  PDF  LaTeX  | Export record:  Atom XML  MODS XML  ODF XML Hernandez, R., & Martin, M. J. (2015). Pre-Schwarzian and Schwarzian Derivatives of Harmonic Mappings. J. Geom. Anal., 25(1), 64–91. Abstract: In this paper we introduce a definition of the pre-Schwarzian and the Schwarzian derivatives of any locally univalent harmonic mapping f in the complex plane without assuming any additional condition on the (second complex) dilatation omega(f) of f. Using the new definition for the Schwarzian derivative of harmonic mappings, we prove theorems analogous to those by Chuaqui, Duren, and Osgood. Also, we obtain a Becker-type criterion for the univalence of harmonic mappings. Permanent link  | Save citation:  RTF  PDF  LaTeX  | Export record:  Atom XML  MODS XML  ODF XML
 Select All    Deselect All << 1 >> List View  | Citations  | Details