2020/02/20 by Alexandre Abreu, Luís Cunha, Abreu, Alexandre +11
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05C #Advanced biosensing and bioanalysis techniques #Bipartite graph #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cover (algebra) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Geometry #Graph #Mathematics #Quantum Computing Algorithms and Architecture #Tessellation (computer graphics) #acm:05C #cs.CC #cs.DM #math.CO #msc:05C
paper · pdf · doi:10.48550/arxiv.2002.08992
arxiv created 2020/02/20 · openalex publication_date 2020/02/20 · arxiv updated 2020/02/24 · openalex created_date 2020/03/06 · openalex updated_date 2026/07/28
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 Tt(G), which is the smallest number of tessellations required in a total tessellation cover of G. We highlight two of these lower bounds Tt(G) ≥ ω(G) and Tt(G)≥ 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 Tt(G)=ω(G) or Tt(G)=is(G)+1. The k-total tessellability problem aims to decide whether a given graph G has Tt(G) ≤ k. We show that k-total tessellability is in P for good total tessellable graphs. We establish the 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.