Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the edge-vertex ratio of maximal thrackles
141
0
0.0
(
0
)
Added by
Boris Klemz
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conways conjecture states that a thrackle has at most as many edges as vertices. In this paper, we investigate the edge-vertex ratio of maximal thrackles, that is, thrackles in which no edge between already existing vertices can be inserted such that the resulting drawing remains a thrackle. For maximal geometric and topological thrackles, we show that the edge-vertex ratio can be arbitrarily small. When forbidding isolated vertices, the edge-vertex ratio of maximal geometric thrackles can be arbitrarily close to the natural lower bound of 1/2. For maximal topological thrackles without isolated vertices, we present an infinite family with an edge-vertex ratio of 5/6.
rate research
Read More
We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $ell ge 1$ the problem of finding a minimum weight maximal distance-$2ell$ matching and the problem of finding a minimum weight $(2 ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $delta ln |V(G)|$ unless $mathrm{P} = mathrm{NP}$, where $delta$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs.
Given a planar graph $G$, we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $pi$ of the vertex set of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $pi$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $pi$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.
We extend Cellular Automata to time-varying discrete geometries. In other words we formalize, and prove theorems about, the intuitive idea of a discrete manifold which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same. For this purpose we develop a correspondence between complexes and labeled graphs. In particular we reformulate the properties that characterize discrete manifolds amongst complexes, solely in terms of graphs. In dimensions $n<4$, over bounded-star graphs, it is decidable whether a Cellular Automaton maps discrete manifolds into discrete manifolds.
A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such coloring is denoted by $chi_a(G)$. We prove that $chi_a(G) = 2R + 1$ for most circulant graphs $C_n([1, R])$.
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {em graphs with semi-edges}. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello et al. asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show that the presence of semi-edges makes the covering problem considerably harder; e.g., it is no longer sufficient to specify the vertex mapping induced by the covering, but one necessarily has to deal with the edge mapping as well. We show some solvable cases, and completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. This provides a strengthening of previously known results for covering graphs without semi-edges, and may contribute to better understanding of this notion and its complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
