Chinese Quarterly Journal of Mathematics ›› 2022, Vol. 37 ›› Issue (4): 355-365.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.003

Previous Articles     Next Articles

Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees

  

  1. 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
  • Received:2022-11-14 Online:2022-12-30 Published:2022-12-30
  • Contact: LIU Yan (1986-), female, native of Hami, Xinjiang, professor of South China Normal University, engages in graph theory. E-mail:iuyan@scnu.edu.cn
  • About author:: 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.
  • 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). 

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 Gn be the set of simple
connected graphs with order n and Tn 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 Tn and Gn.


Key words:  Ergodicity, Bandwidth, Cutwidth, Cyclic bandwidth, Bandwidth sum

CLC Number: