Queue Layouts of Strong Products: Wheel Graphs with Paths and Cycles
Yueyang Hao, Xin Geng, Weihua Yang · Journal of Interconnection Networks · 2025
A queue layout (respectively, strict queue layout) of a graph [Formula: see text] consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested (overlapping). The queue number [Formula: see text] is the minimum number of queues required in a queue layout of [Formula: see text]. Denote [Formula: see text] as a path graph on [Formula: see text] vertices, where [Formula: see text]. Denote [Formula: see text] as a cycle graph on [Formula: see text] vertices, where [Formula: see text]. Denote [Formula: see text] as a wheel graph on [Formula: see text] vertices, where [Formula: see text]. Let the minimum degree of [Formula: see text] be [Formula: see text]. Prior to this work, Wood in [Queue layouts of graph products and powers, Discrete Math. Theor. Comput. Sci. 7(1) (2005) 255–268] showed that [Formula: see text] and for all graphs [Formula: see text] and [Formula: see text], [Formula: see text]. That is, [Formula: see text] and [Formula: see text], where [Formula: see text]. In this work, we prove that [Formula: see text] and [Formula: see text]. In particular, when [Formula: see text], [Formula: see text].