Queue Layouts of Toroidal Grids

Kung-Jui PAI; Jou-Ming CHANG; Yue-Li WANG; Ro-Yu WU

doi:10.1587/transfun.E97.A.1180

Queue Layouts of Toroidal Grids

Kung-Jui PAI, Jou-Ming CHANG, Yue-Li WANG, Ro-Yu WU

Full Text Views

0

Cite this

Summary :

A queue layout of a graph G 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. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G₁ = (V₁,E₁) and G₂ = (V₂,E₂), denoted by G₁ × G₂, is the graph with {<v₁,v₂>:v₁ ∈ V₁ and v₂ ∈ V₂} as its vertex set and an edge (<u₁,u₂>,<v₁,v₂>) belongs to G₁×G₂ if and only if either (u₁,v₁) ∈ E₁ and u₂ = v₂ or (u₂,v₂) ∈ E₂ and u₁ = v₁. Let T_{k₁,k₂,...,k_n} denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., T_{k₁,k₂,...,k_n} = C_k₁ × C_k₂ × … × C_{k_n}, where C_{k_i} is a cycle of length k_i ≥ 3. If k₁ = k₂ = … = k_n = k, the graph is also called the k-ary n-cube and is denoted by Q_n^k. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(T_{k₁,k₂,...,k_n}) ≤ 2n-2 if n ≥ 2 and k_i ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k₁,k₂ ≥ 3, we acquire qn(T_k₁,k₂) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Q_n^k) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Q_n^k) when n ≥2 and k ≥9.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1180-1186

Publication Date: 2014/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.1180

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Kung-Jui PAI
  New Taipei City
Jou-Ming CHANG
  National Taipei College of Business
Yue-Li WANG
  National Taiwan University of Science and Technology
Ro-Yu WU
  Lunghwa University of Science and Technology

Keyword

Queue layout, Toroidal grids, Cartesian product, Arched leveled-planar graphs

Cite this

Copy

Kung-Jui PAI, Jou-Ming CHANG, Yue-Li WANG, Ro-Yu WU, "Queue Layouts of Toroidal Grids" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1180-1186, June 2014, doi: 10.1587/transfun.E97.A.1180.
Abstract: A queue layout of a graph G 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. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G₁ = (V₁,E₁) and G₂ = (V₂,E₂), denoted by G₁ × G₂, is the graph with {<v₁,v₂>:v₁ ∈ V₁ and v₂ ∈ V₂} as its vertex set and an edge (<u₁,u₂>,<v₁,v₂>) belongs to G₁×G₂ if and only if either (u₁,v₁) ∈ E₁ and u₂ = v₂ or (u₂,v₂) ∈ E₂ and u₁ = v₁. Let T_{k₁,k₂,...,k_n} denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., T_{k₁,k₂,...,k_n} = C_k₁ × C_k₂ × … × C_{k_n}, where C_{k_i} is a cycle of length k_i ≥ 3. If k₁ = k₂ = … = k_n = k, the graph is also called the k-ary n-cube and is denoted by Q_n^k. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(T_{k₁,k₂,...,k_n}) ≤ 2n-2 if n ≥ 2 and k_i ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k₁,k₂ ≥ 3, we acquire qn(T_k₁,k₂) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Q_n^k) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Q_n^k) when n ≥2 and k ≥9.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1180/_p

Copy

@ARTICLE{e97-a_6_1180,
author={Kung-Jui PAI, Jou-Ming CHANG, Yue-Li WANG, Ro-Yu WU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Queue Layouts of Toroidal Grids},
year={2014},
volume={E97-A},
number={6},
pages={1180-1186},
abstract={A queue layout of a graph G 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. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G₁ = (V₁,E₁) and G₂ = (V₂,E₂), denoted by G₁ × G₂, is the graph with {<v₁,v₂>:v₁ ∈ V₁ and v₂ ∈ V₂} as its vertex set and an edge (<u₁,u₂>,<v₁,v₂>) belongs to G₁×G₂ if and only if either (u₁,v₁) ∈ E₁ and u₂ = v₂ or (u₂,v₂) ∈ E₂ and u₁ = v₁. Let T_{k₁,k₂,...,k_n} denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., T_{k₁,k₂,...,k_n} = C_k₁ × C_k₂ × … × C_{k_n}, where C_{k_i} is a cycle of length k_i ≥ 3. If k₁ = k₂ = … = k_n = k, the graph is also called the k-ary n-cube and is denoted by Q_n^k. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(T_{k₁,k₂,...,k_n}) ≤ 2n-2 if n ≥ 2 and k_i ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k₁,k₂ ≥ 3, we acquire qn(T_k₁,k₂) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Q_n^k) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Q_n^k) when n ≥2 and k ≥9.},
keywords={},
doi={10.1587/transfun.E97.A.1180},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Queue Layouts of Toroidal Grids
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1180
EP - 1186
AU - Kung-Jui PAI
AU - Jou-Ming CHANG
AU - Yue-Li WANG
AU - Ro-Yu WU
PY - 2014
DO - 10.1587/transfun.E97.A.1180
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - A queue layout of a graph G 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. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G₁ = (V₁,E₁) and G₂ = (V₂,E₂), denoted by G₁ × G₂, is the graph with {<v₁,v₂>:v₁ ∈ V₁ and v₂ ∈ V₂} as its vertex set and an edge (<u₁,u₂>,<v₁,v₂>) belongs to G₁×G₂ if and only if either (u₁,v₁) ∈ E₁ and u₂ = v₂ or (u₂,v₂) ∈ E₂ and u₁ = v₁. Let T_{k₁,k₂,...,k_n} denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., T_{k₁,k₂,...,k_n} = C_k₁ × C_k₂ × … × C_{k_n}, where C_{k_i} is a cycle of length k_i ≥ 3. If k₁ = k₂ = … = k_n = k, the graph is also called the k-ary n-cube and is denoted by Q_n^k. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(T_{k₁,k₂,...,k_n}) ≤ 2n-2 if n ≥ 2 and k_i ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k₁,k₂ ≥ 3, we acquire qn(T_k₁,k₂) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Q_n^k) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Q_n^k) when n ≥2 and k ≥9.
ER -