Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees

LIN Yi-shu, CHANG Cai-bing, LIU Yan

doi:10.13371/j.cnki.chin.q.j.m.2022.04.003

Chinese Quarterly Journal of Mathematics >

2022 , Vol. 37 >Issue 4: 355 - 365

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.04.003

Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees

Expand

1. School of Internet Finance and Information Engineering, Guangdong University of Finance,
Guangzhou 510000, China; 2. School of Mathematical Science, South China Normal University,
Guangzhou 510000, China

: LIN Yi-shu (1987-), female, native of Jieyang, Guangdong, lecturer of Guangdong University of Finance, engages in graph theory; CHANG Cai-bing (1994-), female, native of Zhanjiang, Guangdong, student of South China Normal University, engages in graph theory; LIU Yan (1986-), female, native of Hami, Xinjiang, professor of South China Normal University, engages in graph theory.

Received date: 2022-11-14

Online published: 2022-12-30

Supported by

Supported by Science and Technology Program of Guangzhou (Grant No. 202002030183); Natural Science Foundation of Guangdong (Grant No. 2021A1515012045); National Natural Science Foundation of China (Grant No. 12161073); Natural Science Foundation of Qinghai (Grant No. 2020-ZJ-924).

Fold

Abstract

Bandwidth, cutwidth, cyclic bandwidth, bandwidth sum and cyclic bandwidth
sum are well-known indices about optimal labeling of graphs applied in VLSI design,
network communications, and other areas involving the graph layout. To design the
graphs with the given indices, we need to study the ergodicity. Let F be a set of graphs
under consideration and ϕ an integer-valued function defined on F, namely, ϕ is an index,
such as bandwidth and cutwidth. If there exists a graph G ∈ F such that ϕ(G) =x for
any integer x in the interval [a,b], where a and b are the minimum and maximum of ϕ
on F, respectively, then ϕ is said to have ergodicity on F. Let G_n be the set of simple
connected graphs with order n and T_n the set of trees with order n. In this paper, we
investigate the ergodicity of bandwidth, cutwidth, cyclic bandwidth, the bandwidth sum
and cyclic bandwidth sum on T_n and G_n.

Key words： Ergodicity; Bandwidth; Cutwidth; Cyclic bandwidth; Bandwidth sum

Cite this article

LIN Yi-shu, CHANG Cai-bing, LIU Yan . Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(4) : 355 -365 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.003

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article