Queue Layouts of Graph Products and Powers

David R. Wood

doi:10.46298/dmtcs.352

David R. Wood - Queue Layouts of Graph Products and Powers

dmtcs:352 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 - https://doi.org/10.46298/dmtcs.352

Queue Layouts of Graph Products and PowersArticle

Authors: David R. Wood ¹

1 Departament de Matemàtica Aplicada II

A \emphk-queue layout of a graph G consists of a linear order σ of V(G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ . This paper studies queue layouts of graph products and powers

https://doi.org/10.46298/dmtcs.352

Source: HAL:hal-00959041v1

Volume: Vol. 7

Published on: January 1, 2005

Imported on: March 26, 2015

Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [fr] graph, queue layout, cartesian product, d-dimensional grid graph, d-dimensional toroidal grid graph, Hamming graph

Bibliographic References

11 Documents citing this article

Petr Hliněný;Adam Straka, 2024, Stack and queue numbers of graphs revisited, European Journal of Combinatorics, 129, pp. 104094, 10.1016/j.ejc.2024.104094.

Robert Hickingbotham;David R. Wood, 2024, Shallow Minors, Graph Products, and Beyond-Planar Graphs, SIAM Journal on Discrete Mathematics, 38, 1, pp. 1057-1089, 10.1137/22m1540296.

Petr Hlineny;Adam Straka, 2023, Stack and Queue Numbers of Graphs Revisited, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, pp. 601-606, 10.5817/cz.muni.eurocomb23-083.

Vida Dujmovic;Gwenael Joret;Piotr Micek;Pat Morin;Torsten Ueckerdt;et al., 2019, Planar Graphs have Bounded Queue-Number, Homo Politicus (Academy of Humanities and Economics in Lodz), pp. 862-875, 10.1109/focs.2019.00056, https://ruj.uj.edu.pl/xmlui/handle/item/155586.

Kung-Jui PAI;Jou-Ming CHANG;Yue-Li WANG;Ro-Yu WU, 2014, Queue Layouts of Toroidal Grids, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E97.A, 6, pp. 1180-1186, 10.1587/transfun.e97.a.1180.

Martin Milanič;Oliver Schaudt, 2013, Computing square roots of trivially perfect and threshold graphs, Discrete Applied Mathematics, 161, 10-11, pp. 1538-1545, 10.1016/j.dam.2012.12.027.

Petr Gregor;Riste Škrekovski;Vida Vukašinović, 2011, On the queue-number of the hypercube, Electronic Notes in Discrete Mathematics, 38, pp. 413-418, 10.1016/j.endm.2011.09.067.

Kung-Jui Pai;Jou-Ming Chang;Yue-Li Wang, 2010, Erratum to “A new upper bound on the queuenumber of hypercubes” [Discrete Math. 310 (2010) 935–939], Discrete Mathematics, 310, 13-14, pp. 2059, 10.1016/j.disc.2010.02.002.

Kung-Jui Pai;Jou-Ming Chang;Yue-Li Wang, 2009, Upper bounds on the queuenumber of k-ary n-cubes, Information Processing Letters, 110, 2, pp. 50-56, 10.1016/j.ipl.2009.10.006.

Kung-Jui Pai;Jou-Ming Chang;Yue-Li Wang, 2009, A new upper bound on the queuenumber of hypercubes, Discrete Mathematics, 310, 4, pp. 935-939, 10.1016/j.disc.2009.09.007.

Toru Hasunuma;Misa Hirota, 2007, An improved upper bound on the queuenumber of the hypercube, Information Processing Letters, 104, 2, pp. 41-44, 10.1016/j.ipl.2007.05.006.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 642 times.

This article's PDF has been downloaded 750 times.