Source author record

Luís Cunha

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Computational Complexity

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Simpler and efficient characterizations of tree t-spanners for graphs with few P4's and (k, l)-graphs

A tree $t$ -spanner of a graph $G$ is a spanning tree $T$ in which the distance between any two adjacent vertices of $G$ is at most $t$ . The smallest $t$ for which $G$ has a tree $t$ -spanner is called tree stretch index. The $t$ -admissibility problem aims to decide whether the tree stretch index is at most $t$ . Regarding its optimization version, the smallest $t$ for which $G$ is $t$ -admissible is the stretch index of $G$ , denoted by $σ_T(G)$ . Given a graph with $n$ vertices and $m$ edges, the recognition of $2$ -admissible graphs can be done $O(n+m)$ time, whereas $t$ -admissibility is NP-complete for $σ_T(G) \leq t$ , $t \geq 4$ and deciding if $t = 3$ is an open problem, for more than 20 years. Since the structural knowledge of classes can be determinant to classify $3$ -admissibility's complexity, in this paper we present simpler and faster algorithms to check $2$ and $3$ -admissibility for families of graphs with few $P_4$ 's and $(k,\ell)$ -graphs. Regarding $(0,\ell)$ -graphs, we present lower and upper bounds for the stretch index of these graphs and characterize graphs whose stretch indexes are equal to the proposed upper bound. Moreover, we prove that $t$ -admissibility is NP-complete even for line graphs of subdivided graphs.

preprint2020arXiv

Total tessellation cover and quantum walk

We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph, in contrast with previous models in which the walker hops either to vertices or edges. We establish bounds on $T_t(G)$ , which is the smallest number of tessellations required in a total tessellation cover of $G$ . We highlight two of these lower bounds $T_t(G) \geq ω(G)$ and $T_t(G)\geq is(G)+1$ , where $ω(G)$ is the size of a maximum clique and $is(G)$ is the number of edges of a maximum induced star subgraph. Using these bounds, we define the good total tessellable graphs with either $T_t(G)=ω(G)$ or $T_t(G)=is(G)+1$ . The $k$ -total tessellability problem aims to decide whether a given graph $G$ has $T_t(G) \leq k$ . We show that $k$ -total tessellability is in $\mathcal{P}$ for good total tessellable graphs. We establish the $\mathcal{NP}$ -completeness of the following problems when restricted to the following classes: ( $is(G)+1$ )-total tessellability for graphs with $ω(G) = 2$ ; $ω(G)$ -total tessellability for graphs $G$ with $is(G)+1 = 3$ ; $k$ -total tessellability for graphs $G$ with $\max\{ω(G), is(G)+1\}$ far from $k$ ; and $4$ -total tessellability for graphs $G$ with $ω(G) = is(G)+1 = 4$ . As a consequence, we establish hardness results for bipartite graphs, line graphs of triangle-free graphs, universal graphs, planar graphs, and $(2,1)$ -chordal graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.