Paper Info
Title
The graph tessellation cover number: extremal bounds, efficient algorithms and hardness.
Abstract
A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges. The t-tessellability problem aims to decide whether there is a tessellation cover of the graph with t tessellations. This problem is motivated by its applications to quantum walk models, in especial, the evolution operator of the staggered model is obtained from a graph tessellation cover. We establish upper bounds on the tessellation cover number given by the minimum between the chromatic index of the graph and the chromatic number of its clique graph and we show graph classes for which these bounds are tight. We prove NP-completeness for t-tessellability if the instance is restricted to planar graphs, chordal (2, 1)-graphs, (1, 2)-graphs, diamond-free graphs with diameter five, or for any fixed t at least 3. On the other hand, we improve the complexity for 2-tessellability to a linear-time algorithm.
Year
DOI
Venue
2018
10.1007/978-3-319-77404-6_1
Lecture Notes in Computer Science
Keywords
DocType
Volume
Staggered quantum walk,Clique graph,Tessellation
Conference
10807
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
8
8
Name
Order
Citations
PageRank
Alexandre Santiago de Abreu100.34
Luís Felipe I. Cunha235.85
Tharso D. Fernandes300.34
Celina M. H. de Figueiredo429638.49
Luis Antonio Brasil Kowada5239.01
F. L. Marquezino6196.66
Daniel F. D. Posner782.18
Renato Portugal85210.01