图族和树族的带宽和割宽的遍历性

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

数学季刊 ›› 2022, Vol. 37 ›› Issue (4): 355-365.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.003

图族和树族的带宽和割宽的遍历性

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

收稿日期:2022-11-14 出版日期:2022-12-30 发布日期:2022-12-30
通讯作者: LIU Yan (1986-), female, native of Hami, Xinjiang, professor of South China Normal University, engages in graph theory. E-mail:iuyan@scnu.edu.cn
作者简介:: 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 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).

Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees

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 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.

关键词: Ergodicity, Bandwidth, Cutwidth, Cyclic bandwidth, Bandwidth sum

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

中图分类号:

O157.5

林艺舒, 常彩冰, 刘岩. 图族和树族的带宽和割宽的遍历性[J]. 数学季刊, 2022, 37(4): 355-365.

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.

[1]	张振坤, 叶稀琼. K 割宽临界树的构造[J]. 数学季刊, 2022, 37(4): 366-379.
[2]	郝建修, 李湘露. L_∞模下的二维带宽问题[J]. 数学季刊, 2004, 19(4): 362-367.

图族和树族的带宽和割宽的遍历性

Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价