论文标题
总干燥盖和量子步行
Total tessellation cover and quantum walk
论文作者
论文摘要
我们提出了总交错的量子步行模型和图形的总镶嵌盖。该模型使用总镶嵌覆盖物的概念来描述沃克的运动，该运动被允许跳到图形的顶点和边缘，与先前的沃克跳动到顶点或边缘的模型相比。我们在$ t_t（g）$上建立了界限，这是$ g $的总镶嵌盖中最少的镶嵌数量。我们突出显示了这些下限的两个$ t_t（g）\ geqω（g）$和$ t_t（g）\ geq is（g）+1 $，其中$ω（g）$是最大群集的大小，$ is $ is（g）$是最大诱导星星子的边数。使用这些边界，我们用$ t_t（g）=ω（g）$或$ t_t（g）= is（g）+1 $来定义良好的总可镶嵌图。 $ k $ - 总计镶嵌性问题旨在决定给定的图$ g $是否具有$ t_t（g）\ leq k $。我们证明，$ k $ - 总计镶嵌性在$ \ mathcal {p} $中，对于良好的总可软形图。我们建立了$ \ Mathcal {np} $ - 仅限于以下类时的以下问题的完整性：（$ is（g）+1 $） - $ω（g）= 2 $的图形的总镶嵌性； $ω（g）$ - 图形的总镶嵌性$ g $ with $ is（g）+1 = 3 $; $ k $ -total Tessellable for Graphs $ g $带有$ \ max \ {ω（g），是（g）+1 \} $远离$ k $; $ 4 $ - $ -TOMPAL-g $ a $ g $的$ 4 $ - （g）= is（g）+1 = 4 $。结果，我们为两分图，三角形图，通用图，平面图和$（2,1）$ - 弦弦图建立了硬度结果。
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.
