2阶路和n阶圈强乘积图的最优无线电标号数

The Optimal Radio Labeling Number of Strong Product Graphs with 2⁃Path and n⁃Circle

摘要

无线电标号是用拓扑图对无线通信网络中频率资源分配问题进行建模， 图的顶点表示基站， 边表示基站之间的距离关系， 通过“距离—标号”约束给图中每个顶点分配一个数字（标号）， 最终得到所需的最大标号， 使得最大标号数最小化的分配方案称为最优分配方案， 最终结果为最优无线电标号数。本文主要研究2阶路和n阶圈（n为奇数且n\ge \mathrm{3}）的强乘积图， 根据相关约束赋予这类强乘积图的顶点标号， 并确定最优的无线电标号数。实验数据表明， 本文设计的拓扑模型相对于已有的路图、 圈图、 路和路的强乘积图模型， 相同的顶点数所需要的无线电标号更少。本文研究对无线通信网络的构造具有一定的参考意义。

Abstract

Radio labeling uses a topological graph to build model for the frequency resource allocation problem in wireless communication networks， where the vertices of the graph represent the base stations and the edges represent the distance relationship of different base stations， and each vertex in the graph is assigned a number （labeling） through the “distance-labeling” constraint， finally obtaining the maximum labeling number， and the allocation scheme that minimizes the maximum number of labeling is called the optimal allocation scheme， and the result is the optimal number of radio labeling. This article mainly studied strong product graphs of P_{\mathrm{2}} and C_n（n was odd and n\ge \mathrm{3}）， labeled the vertices of these strong product graphs according to relevant constraints， and determined the optimal radio labeling number. The experimental data show that the topological model designed in this paper requires fewer radio labelings for the same number of vertices compared to the existing paths， circles， and strong product graphs of paths and paths models， which is a reference for wireless communication network construction.

Graphical abstract

关键词

无线电标号 / 频率资源分配 / 圈图 / 强乘积图

Key words

radio labeling / frequency resource allocation / circle graph / strong product graph

0 引　言

随着通信技术的发展， 无线电、 移动电话、 通信卫星等无线技术的出现彻底改变了人们的交流方式。相比固定通信， 无线通信更加便捷且成本较低， 但无线通信并不完美， 现实中很多制约因素限制了无线通信技术的发展， 使其技术潜力难以发挥， 最典型的一方面就是频率资源受限。所以， 合理高效地分配频率资源在无线通信网络中显得尤为重要。

频率资源规划问题实质上是一个组合优化问题。将有限数目的频率分配给较多数目的载频， 由于载频个数远远大于频率个数， 不可避免地会在不同载频分配到相同频率或者相邻的频率时产生干扰。Hale^［1］首次提出用图对频率资源分配问题进行建模， 将基站抽象成顶点， 若两个顶点之间有关联即两个顶点之间有连接线， 此时的边可以看作基站之间的干扰， 当两个基站之间有边时， 若在同一频段通信会相互干扰。所以， 在本文的研究中将频率抽象转化为数字时， 要求每个基站（顶点）标号数值不同并满足相应的限制条件。这样， 便把频率资源分配问题转化为了对图中关联顶点的标号问题， 然后通过科学手段对频率资源进行合理的配置， 就可以最大程度地减少干扰并提高资源利用率。

20世纪90年代， Griggs等^［2］首次引入了距离二标号（L(\mathrm{2,1})-标号）的概念， 对于图G存在函数\varphi： V(G)\to N， 使得

|\varphi (u)-\varphi (v)|\ge \left\{\begin{array}{cc}\mathrm{1},& d_G(u,v)=\mathrm{2},\\ \mathrm{2},& d_G(u,v)=\mathrm{1},\end{array}\right.

式中： V(G)表示图G的顶点集； d_G(u,v)表示顶点u和v之间的最短距离。对于\forall u,v\in V(G)， 图G的L(\mathrm{2,1})-标号表示为\mathrm{m}\mathrm{a}\mathrm{x}\{|\varphi (u)-\varphi (v)|\}。

距离二标号概念被提出后， Chang等^［3］对L(\mathrm{2,1})-标号的定义作了更详细的补充， 吸引了更多的学者对图标号进行研究。研究表明， 计算任意图的最优无线电标号数是极其困难的。因此， 研究人员开始对一些特定的图族进行研究。Liu等^［4-6］确定了路和圈的无线电标号数， 并给出了树的无线电标号数的上下界； Morris-Rivera等^［7］确定了圈和它本身的笛卡尔乘积图的无线电标号数； Kim等^［8］给出了完全图和路的笛卡尔乘积图的无线电标号数； Bantva^［9‐10］根据路径的奇偶性研究了路径中间图的最优无线电标号数， 并根据给定图最优无线电标号下界的条件， 确定了路和轮图的笛卡尔乘积的最优无线电标号数。更多关于无线电标号以及一些特殊图的研究， 如广义Petersen图的无线电标号的最优结果可参考文献［11‐15］。虽然很多学者对笛卡尔乘积图的无线电标号做了大量研究， 但将强乘积图模型与无线电标号结合起来模拟频率资源分配的成果并不是很多。目前， Qi等^［16］根据3阶完全图和n阶路的强乘积图的拓扑结构， 利用中心点确定了这类强乘积图的最优无线电标号数； Vaidyaa等^［17］给出了2阶路和n阶路的强乘积图的最优无线电标号数。本文主要讨论2阶路和n阶圈（n为奇数且n\ge \mathrm{3}）的强乘积图的标号方式， 给出了最优无线电标号数， 并通过图表数据对比证明本文提出的新强乘积图模型比已有的一些模型更适合搭建无线通信网络结构， 可以提高通信质量。

1 预备知识

定义 1^［18］　图G的无线电标号是函数

\varphi :V(G)\to N,

使得

|\varphi (u)-\varphi (v)|\ge diam(G)+\mathrm{1}-

d_G(u,v),\forall u,v\in V(G),

式中： V(G)表示图G顶点集； d_G(u,v)表示图G中顶点u和v之间的最短距离； diam(G)表示图G的直径， 即图G中任意两个顶点之间最短距离的最大值。图G的无线电标号表示为\varphi的跨度， 即span(\varphi )=\mathrm{m}\mathrm{a}\mathrm{x}\{|\varphi (u)-\varphi (v)|\},\forall u,v\in V(G)，图G的最优无线电标号数用rn(G)来表示， 是G的所有无线电标号中的最小跨度， rn(G)=\mathrm{m}\mathrm{i}\mathrm{n}(span(\varphi ))。

定义 2^［19］　设H=(V(H),E(H))， H的一条途径是指一个有限非空序列P=v_{\mathrm{0}}{e}_{\mathrm{1}}{v}_{\mathrm{1}}{e}_{\mathrm{2}}\cdots e_k{v}_k， 它的项是交替出现的顶点和边， 使得对于\mathrm{1}\le i\le k， e_i的端点是v_{i-\mathrm{1}}和v_i， 则称P是从v_{\mathrm{0}}到v_k的一条途径， v_{\mathrm{0}}和v_k分别为P的起点和终点， 而v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{k-\mathrm{1}}称为它的内部顶点， 若途径的顶点互不相同， 则称P为路， 有n个顶点的路记为P_n。若一条途径的长度为正， 且起点和终点相同， 但内部顶点不同， 则称为圈， 有n个顶点的圈记为C_n。

定义 3^［19］　设M=(V_{\mathrm{1}},E_{\mathrm{1}}),N=(V_{\mathrm{2}},E_{\mathrm{2}})是两个简单连通图， M和N的强乘积为G=M\otimes N， 令G=(V,E)， 其中V=V_{\mathrm{1}}\times V_{\mathrm{2}}， 图G中的顶点(x_{\mathrm{1}},y_{\mathrm{1}})和(x_{\mathrm{2}},y_{\mathrm{2}})相邻当且仅当x_{\mathrm{1}}=x_{\mathrm{2}}， y_{\mathrm{1}}{y}_{\mathrm{2}}\in E_{\mathrm{2}}或者x_{\mathrm{1}}{x}_{\mathrm{2}}\in E_{\mathrm{1}}， y_{\mathrm{1}}=y_{\mathrm{2}}或者x_{\mathrm{1}}{x}_{\mathrm{2}}\in E_{\mathrm{1}}， y_{\mathrm{1}}{y}_{\mathrm{2}}\in E_{\mathrm{2}}， 其中， x_{\mathrm{1}},x_{\mathrm{2}}\in V_{\mathrm{1}}， y_{\mathrm{1}},y_{\mathrm{2}}\in V_{\mathrm{2}}。

强乘积图G的直径为

diam(G)=\mathrm{m}\mathrm{a}\mathrm{x}\{diam(M),diam(N)\},

任意两个顶点(x_{\mathrm{1}},y_{\mathrm{1}})和(x_{\mathrm{2}},y_{\mathrm{2}})之间的距离为

d_G((x_{\mathrm{1}},y_{\mathrm{1}}),(x_{\mathrm{2}},y_{\mathrm{2}}))=\mathrm{m}\mathrm{a}\mathrm{x}\{d_M(x_{\mathrm{1}},x_{\mathrm{2}}),d_N(y_{\mathrm{1}},y_{\mathrm{2}})\}\mathrm{。}

2 主要结果

引理 1　若u,v,t\in V(P_{\mathrm{2}}\otimes C_n)（n为奇数且n\ge \mathrm{3}）， 则d(u,v)+d(v,t)+d(u,t)\le n。

证明　将顶点u,v,t用它们的分量顶点表示， 即u=(x_{\mathrm{1}},y_{\mathrm{1}})，v=(x_{\mathrm{2}},y_{\mathrm{2}})，t=(x_{\mathrm{3}},y_{\mathrm{3}})， 其中x_{\mathrm{1}}，x_{\mathrm{2}}，x_{\mathrm{3}}\in V(P_{\mathrm{2}}),y_{\mathrm{1}},y_{\mathrm{2}},y_{\mathrm{3}}\in V(C_n)， 根据定义 3， 有

\begin{array}{c}d(u,v)+d(v,t)+d(u,t)=\\ d((x_{\mathrm{1}},y_{\mathrm{1}}),(x_{\mathrm{2}},y_{\mathrm{2}}))+d((x_{\mathrm{2}},y_{\mathrm{2}}),(x_{\mathrm{3}},y_{\mathrm{3}}))+\\ d((x_{\mathrm{1}},y_{\mathrm{1}}),(x_{\mathrm{3}},y_{\mathrm{3}}))=\\ \mathrm{m}\mathrm{a}\mathrm{x}(d(x_{\mathrm{1}},x_{\mathrm{2}}),d(y_{\mathrm{1}},y_{\mathrm{2}}))+\mathrm{m}\mathrm{a}\mathrm{x}(d(x_{\mathrm{2}},x_{\mathrm{3}}),\\ d(y_{\mathrm{2}},y_{\mathrm{3}}))+\mathrm{m}\mathrm{a}\mathrm{x}(d(x_{\mathrm{1}},x_{\mathrm{3}}),d(y_{\mathrm{1}},y_{\mathrm{3}}))=\\ d(y_{\mathrm{1}},y_{\mathrm{2}})+d(y_{\mathrm{2}},y_{\mathrm{3}})+d(y_{\mathrm{1}},y_{\mathrm{3}})\le n\mathrm{。}\end{array}

引理 2　设\varphi是强乘积图P_{\mathrm{2}}\otimes C_n（n为奇数且n\ge \mathrm{3}）的一个无线电标号， 对于任意3个顶点u,v,t\in V(P_{\mathrm{2}}\otimes C_n)且满足 则

\varphi (t)-\varphi (u)\ge ⌈\frac{n+\mathrm{3}}{\mathrm{4}}⌉\mathrm{。}

证明　因为\varphi是强乘积图P_{\mathrm{2}}\otimes C_n的一个无线电标号且， 所以满足

\begin{array}{c}\varphi (v)-\varphi (u)\ge \mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u,v),\\ \varphi (t)-\varphi (v)\ge \mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(v,t),\\ \varphi (t)-\varphi (u)\ge \mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u,t),\end{array}

联立上述不等式得

\begin{array}{c}\mathrm{2}\varphi (t)-\mathrm{2}\varphi (u)\ge \mathrm{3}+\mathrm{3}diam(P_{\mathrm{2}}\otimes C_n)-\\ d(u,v)-d(v,t)-d(u,t)\mathrm{。}\end{array}

由于diam(P_{\mathrm{2}}\otimes C_n)=\frac{n-\mathrm{1}}{\mathrm{2}}， 且根据引理2有d(u,v)+d(v,t)+d(u,t)\le n， 所以

\mathrm{2}\varphi (t)-\mathrm{2}\varphi (u)\ge \mathrm{3}+\mathrm{3}\left(\frac{n-\mathrm{1}}{\mathrm{2}}\right)-n,

\varphi (t)-\varphi (u)\ge ⌈\frac{n+\mathrm{3}}{\mathrm{4}}⌉\mathrm{。}

定理 1　若n为奇数且n\ge \mathrm{3}， 则强乘积图P_{\mathrm{2}}\otimes C_n的最优无线电标号数满足

rn(P_{\mathrm{2}}\otimes C_n)\ge \left\{\begin{array}{ll}\frac{n^{\mathrm{2}}+\mathrm{2}n+\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4};\\ \frac{n^{\mathrm{2}}+\mathrm{4}n-\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}\mathrm{。}\end{array}\right.

证明　设\varphi是强乘积图P_{\mathrm{2}}\otimes C_n的一个无线电标号， 将P_{\mathrm{2}}\otimes C_n中的顶点重新排列， 表示为\{u_{\mathrm{1}},u_{\mathrm{2}},u_{\mathrm{3}},\cdots ,u_{\mathrm{2}n}\}， 满足。 为了证明rn(P_{\mathrm{2}}\otimes C_n)的下界， 有\varphi (u_{\mathrm{1}})\ge \mathrm{0},\varphi (u_{\mathrm{2}})\ge \varphi (u_{\mathrm{1}})+\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_{\mathrm{1}},u_{\mathrm{2}})\ge \mathrm{1}， 由引理2可知， \varphi (u_{\mathrm{3}})\ge \varphi (u_{\mathrm{1}})+⌈\frac{n+\mathrm{3}}{\mathrm{4}}⌉。不失一般性，

\varphi (u_i)\ge \left\{\begin{array}{cc}\varphi (u_{\mathrm{1}})+\frac{i-\mathrm{1}}{\mathrm{2}}⌈\frac{n+\mathrm{3}}{\mathrm{4}}⌉,& \mathrm{当}i\mathrm{为奇}\mathrm{数};\\ \varphi (u_{\mathrm{2}})+\frac{i-\mathrm{2}}{\mathrm{2}}⌈\frac{n+\mathrm{3}}{\mathrm{4}}⌉,& \mathrm{当}i\mathrm{为偶}\mathrm{数。}\end{array}\right.

因此， rn(P_{\mathrm{2}}\otimes C_n)≥span(\varphi )=\varphi (u_{\mathrm{2}n})-\varphi (u_{\mathrm{1}})≥1+(n-\mathrm{1})⌈\frac{n+\mathrm{3}}{\mathrm{4}}⌉。当n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}时， rn(P_{\mathrm{2}}\otimes C_n)≥1+\frac{(n-\mathrm{1})(n+\mathrm{3})}{\mathrm{4}}=\frac{n^{\mathrm{2}}+\mathrm{2}n+\mathrm{1}}{\mathrm{4}}； 当n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}时， rn(P_{\mathrm{2}}\otimes C_n)≥1+\frac{(n-\mathrm{1})(n+\mathrm{5})}{\mathrm{4}}=\frac{n^{\mathrm{2}}+\mathrm{4}n-\mathrm{1}}{\mathrm{4}}。

引理 3^［20］　若m为偶数， n为奇数， 则存在有序顶点序列\{u_{\mathrm{1}},u_{\mathrm{2}},u_{\mathrm{3}},\cdots ,u_{mn}\}， 使得圈C_n中的每个顶点都出现m次， 且d(u_i,u_{i+\mathrm{1}}),i=\mathrm{1,2},\cdots ,mn-\mathrm{1}的值为\frac{n-\mathrm{1}}{\mathrm{2}}和l的交替序列， 其中，

l=\left\{\begin{array}{ll}\frac{n+\mathrm{3}}{\mathrm{4}},& n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4};\\ \frac{n+\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}\mathrm{。}\end{array}\right.

并且

d(u_i,u_{i+\mathrm{2}})=\left\{\begin{array}{ll}\frac{n-\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4};\\ \frac{n+\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}\mathrm{。}\end{array}\right.

下面的推论显然成立。

推论 1　对于强乘积图P_{\mathrm{2}}\otimes C_n， 存在有序顶点序列\{u_{\mathrm{1}},u_{\mathrm{2}},u_{\mathrm{3}},\cdots ,u_{\mathrm{2}n}\}， 使得d(u_i,u_{i+\mathrm{1}}),i=\mathrm{1,2},\cdots ,\mathrm{2}n-\mathrm{1}的值为\frac{n-\mathrm{1}}{\mathrm{2}}和l的交替序列， 其中，

l=\left\{\begin{array}{ll}\frac{n+\mathrm{3}}{\mathrm{4}},& n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4};\\ \frac{n+\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}\mathrm{。}\end{array}\right.

并且

d(u_i,u_{i+\mathrm{2}})=\left\{\begin{array}{ll}\frac{n-\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4};\\ \frac{n+\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}\mathrm{。}\end{array}\right.

定理 2　若n为奇数且n\ge \mathrm{3}， 则强乘积图P_{\mathrm{2}}\otimes C_n的最优无线电标号数为

rn(P_{\mathrm{2}}\otimes C_n)=\left\{\begin{array}{ll}\frac{n^{\mathrm{2}}+\mathrm{2}n+\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4};\\ \frac{n^{\mathrm{2}}+\mathrm{4}n-\mathrm{1}}{\mathrm{4}},& n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}\mathrm{。}\end{array}\right.

证明　令强乘积图P_{\mathrm{2}}\otimes C_n中的顶点按照推论1中的规则排序， 重新排列为\{u_{\mathrm{1}},u_{\mathrm{2}},u_{\mathrm{3}},…，u_{\mathrm{2}n}\}， 下面分两种情形讨论。

情形一： n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}

首先定义一个函数{\varphi }_{\mathrm{1}}， 对于强乘积图P_{\mathrm{2}}\otimes C_n中的顶点， 满足{\varphi }_{\mathrm{1}}(u_{\mathrm{1}})=\mathrm{0}， {\varphi }_{\mathrm{1}}(u_{i+\mathrm{1}})={\varphi }_{\mathrm{1}}(u_i)+\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{1}})i=1，2，3，…，\mathrm{2}n-\mathrm{1}。基于强乘积图P_{\mathrm{2}}\otimes C_n中顶点的排序特性， 在验证函数{\varphi }_{\mathrm{1}}是强乘积图P_{\mathrm{2}}\otimes C_n的一个无线电标号的过程中， 只需验证顶点u_i和u_{i+\mathrm{2}}， u_i和u_{i+\mathrm{3}}之间是否满足无线电标号的条件。

子情形一： 当i为奇数时， d(u_i,u_{i+\mathrm{1}})=\frac{n-\mathrm{1}}{\mathrm{2}}， d(u_{i+\mathrm{1}},u_{i+\mathrm{2}})=\frac{n+\mathrm{3}}{\mathrm{4}}， d(u_i,u_{i+\mathrm{2}})=\frac{n-\mathrm{1}}{\mathrm{4}}。所以，

\begin{array}{c}{\varphi }_{\mathrm{1}}(u_{i+\mathrm{2}})-{\varphi }_{\mathrm{1}}(u_i)={\varphi }_{\mathrm{1}}(u_{i+\mathrm{2}})-{\varphi }_{\mathrm{1}}(u_{i+\mathrm{1}})+{\varphi }_{\mathrm{1}}(u_{i+\mathrm{1}})-{\varphi }_{\mathrm{1}}(u_i)=\\ (\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_{i+\mathrm{1}},u_{i+\mathrm{2}}))+\end{array}

(\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{1}}))\left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{2}}-\frac{n+\mathrm{3}}{\mathrm{4}}\right)+\left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{2}}-\frac{n-\mathrm{1}}{\mathrm{2}}\right)=

\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{4}}=\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{2}})\mathrm{。}

因为d(u_i,u_{i+\mathrm{3}})\ge d(u_{i+\mathrm{2}},u_{i+\mathrm{3}})-d(u_i,u_{i+\mathrm{2}})=\frac{n-\mathrm{1}}{\mathrm{2}}-\frac{n-\mathrm{1}}{\mathrm{4}}=\frac{n-\mathrm{1}}{\mathrm{4}}， 所以有

\begin{array}{c}{\varphi }_{\mathrm{1}}(u_{i+\mathrm{3}})-{\varphi }_{\mathrm{1}}(u_i)=\\ {\varphi }_{\mathrm{1}}(u_{i+\mathrm{3}})-{\varphi }_{\mathrm{1}}(u_{i+\mathrm{2}})+{\varphi }_{\mathrm{1}}(u_{i+\mathrm{2}})-{\varphi }_{\mathrm{1}}(u_i)=\\ (\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_{i+\mathrm{2}},u_{i+\mathrm{3}}))+\\ \left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{4}}\right)=\left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{2}}-\frac{n-\mathrm{1}}{\mathrm{2}}\right)+\\ \left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{4}}\right)=\mathrm{2}+\frac{n-\mathrm{1}}{\mathrm{4}}>\mathrm{1}+\\ diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{3}})\mathrm{。}\end{array}

子情形二： 当i为偶数时， d(u_i,u_{i+\mathrm{1}})=\frac{n+\mathrm{3}}{\mathrm{4}}， d(u_{i+\mathrm{1}},u_{i+\mathrm{2}})=\frac{n-\mathrm{1}}{\mathrm{2}}， d(u_i,u_{i+\mathrm{2}})=\frac{n-\mathrm{1}}{\mathrm{4}}。与子情形一证法相同， 可得{\varphi }_{\mathrm{1}}(u_{i+\mathrm{2}})-{\varphi }_{\mathrm{1}}(u_i)=\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{2}})， {\varphi }_{\mathrm{1}}(u_{i+\mathrm{3}})-{\varphi }_{\mathrm{1}}(u_i)>\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{3}})。所以， 函数{\varphi }_{\mathrm{1}}是强乘积图P_{\mathrm{2}}\otimes C_n的一个无线电标号， 其中，

{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}n-\mathrm{1}}}d(u_i,u_{i+\mathrm{1}})=

n\left(\frac{n-\mathrm{1}}{\mathrm{2}}\right)+(n-\mathrm{1})\frac{n+\mathrm{3}}{\mathrm{4}}=\frac{\mathrm{3}{n}^{\mathrm{2}}-\mathrm{3}}{\mathrm{4}},

则

rn(P_{\mathrm{2}}\otimes C_n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}n-\mathrm{1}}}({\varphi }_{\mathrm{1}}(u_{i+\mathrm{1}})-{\varphi }_{\mathrm{1}}(u_i))=

(\mathrm{2}n-\mathrm{1})(\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n))-{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}n-\mathrm{1}}}d(u_i,u_{i+\mathrm{1}})=

(\mathrm{2}n-\mathrm{1})\left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{2}}\right)-\frac{\mathrm{3}{n}^{\mathrm{2}}-\mathrm{3}}{\mathrm{4}}=\frac{n^{\mathrm{2}}+\mathrm{2}n+\mathrm{1}}{\mathrm{4}}\mathrm{。}

情形二： n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}

定义一个函数{\varphi }_{\mathrm{2}}， 对于强乘积图P_{\mathrm{2}}\otimes C_n中的顶点， 满足{\varphi }_{\mathrm{2}}(u_{\mathrm{1}})=\mathrm{0}， {\varphi }_{\mathrm{2}}(u_{i+\mathrm{1}})={\varphi }_{\mathrm{2}}(u_i)+\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n)-d(u_i,u_{i+\mathrm{1}}),i=\mathrm{1,2},\mathrm{3},\cdots ,\mathrm{2}n-\mathrm{1}。其证明过程与情形一类似， 同样可以证得{\varphi }_{\mathrm{2}}是强乘积图P_{\mathrm{2}}\otimes C_n的一个无线电标号， 其中，

\begin{array}{c}{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}n-\mathrm{1}}}d(u_i,u_{i+\mathrm{1}})=\\ n(\frac{n-\mathrm{1}}{\mathrm{2}})+(n-\mathrm{1})\frac{n+\mathrm{1}}{\mathrm{4}}=\frac{\mathrm{3}{n}^{\mathrm{2}}-\mathrm{2}n-\mathrm{1}}{\mathrm{4}},\end{array}

则

rn(P_{\mathrm{2}}\otimes C_n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}n-\mathrm{1}}}({\varphi }_{\mathrm{2}}(u_{i+\mathrm{1}})-{\varphi }_{\mathrm{2}}(u_i))=

(\mathrm{2}n-\mathrm{1})(\mathrm{1}+diam(P_{\mathrm{2}}\otimes C_n))-{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}n-\mathrm{1}}}d(u_i,u_{i+\mathrm{1}})=

(\mathrm{2}n-\mathrm{1})\left(\mathrm{1}+\frac{n-\mathrm{1}}{\mathrm{2}}\right)-\frac{\mathrm{3}{n}^{\mathrm{2}}-\mathrm{2}n-\mathrm{1}}{\mathrm{4}}=

\frac{n^{\mathrm{2}}+\mathrm{4}n-\mathrm{1}}{\mathrm{4}}\mathrm{。}

综上所述， 存在强乘积图P_{\mathrm{2}}\otimes C_n顶点的一个标号顺序， 使得按此序标号后， 最大顶点的标号与定理1的下界值一致， 因此， 可以证得强乘积图P_{\mathrm{2}}\otimes C_n（n为奇数且n\ge \mathrm{3}）的最优无线电标号数。

根据定理2给出的结论， 为了方便理解强乘积图P_{\mathrm{2}}\otimes C_n的顶点标号方式， 下面分别给出了满足条件n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}和n\equiv \mathrm{3}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4}两种情形的特例。

例 1　当n=9时， 对强乘积图P_{\mathrm{2}}\otimes C_{\mathrm{9}}的各顶点按照定理2中的情形一进行标号， 其顶点重排序列如图 1 所示， 各顶点标号如图 2 所示， 此时， rn(P_{\mathrm{2}}\otimes C_{\mathrm{9}})=\mathrm{25}。

例 2　当n=\mathrm{7}时， 对强乘积图P_{\mathrm{2}}\otimes C_{\mathrm{7}}的各顶点按照定理2中的情形二进行标号， 其顶点重排序列如图 3 所示， 各顶点标号如图4所示， 此时， rn(P_{\mathrm{2}}\otimes C_{\mathrm{7}})=\mathrm{19}。

3 模型对比分析

为了评估设计的强乘积网络通信模型P_{\mathrm{2}}\otimes C_n对无线通信网络频率分配问题建模的优劣， 在n\ge \mathrm{3}且n为奇数的同等条件下， 将强乘积图P_{\mathrm{2}}\otimes C_n的最优无线电标号数的模拟结果与文献［4］和文献［17］设计的模型进行了数据对比。表 1 通过有限的数据集呈现了路图、 圈图、 2阶路和n阶路的强乘积图以及2阶路和n阶圈的强乘积图的最优无线电标号， 图 5~图 8 更为直观地显示了各模型在模拟无线通信网络频率资源分配问题上的优劣。

表 1　4种拓扑模型的最优无线电标号数

Tab. 1　The optimal radio label number of four topological models

nrn(P_{\mathrm{2}n})rn(C_{\mathrm{2}n})rn(P_{\mathrm{2}}\otimes P_n)rn(P_{\mathrm{2}}\otimes C_n)

3 13 7 7 5

5 41 17 21 9

7 85 31 43 19

9 145 49 73 25

11 221 71 111 41

13 313 97 157 49

15 421 127 211 71

17 545 161 273 81

19 685 199 343 109

21 841 241 421 121

23 1 013 287 507 155

25 1 201 337 601 169

27 1 405 391 703 209

29 1 625 449 813 225

31 1 861 511 931 271

33 2 113 577 1 057 289

35 2 381 647 1 191 341

37 2 665 721 1 333 361

39 2 965 799 1 483 419

41 3 281 881 1 641 441

43 3 613 967 1 807 505

45 3 961 1 057 1 981 529

从图中的线性结果分析可知， 在局域网中， 基站之间的距离越近， 彼此之间通信干扰的可能性越大， 所以本文通过“距离—标号”约束， 寻找最合适的拓扑模型模拟通信网络频率资源分配。图 5 展示了相同顶点数的圈图、 2阶路和n阶路的强乘积图的最优无线电标号的对比， 可以看出连通度更高的2阶路和n阶路的强乘积图所需的无线电标号明显比\mathrm{2}n阶圈图所需的无线电标号更多。图 6~图 8 展示了相同顶点数的路图与圈图、路图与2阶路和n阶路的强乘积图以及圈图与2阶路和n阶圈的强乘积图的最优无线电标号的趋势对比， 发现连通性更强的拓扑图所需的无线电标号反而更少。对比图 5 和图 8 可以看出， 若2阶路和n阶路的强乘积图变成2阶路和n阶圈的强乘积图， 则可适当增加顶点之间的连通性， 使得所需的无线电标号数大大减少。由此可以得出， 构造合适的拓扑模型， 不仅可以增强顶点之间的连通性， 还可以在不存在通信干扰的情形下减少无线电标号。这也表明， 在无线通信网络中， 找到基站之间合适的连接方式以及频率分配方案尤为重要。

由4种模型结果可以看出， 本文构造的2阶路和n阶圈的强乘积图结构在模拟无线通信网络频率资源分配时所消耗的频率数量最少。搭建这种网络结构， 可以在距离和分配的频率资源数之间找到一种平衡， 使得无线通信效率更高。

4 结　论

本文主要确定了2阶路和n阶圈（n为奇数且n\ge \mathrm{3}）的强乘积图的最优无线电标号数， 通过与已有的几种模型数据对比得出： 在相同的基站数量下， 本文构建的模型在现实无线通信网络中所需的频率资源最少。后续将继续研究更为泛化的路和圈的强乘积图的最优无线电标号， 将其结果推广到一般， 并研究更理想的无线通信网络结构模型。

参考文献

[1] HALE W K. Frequency assignment： Theory and applications［C］//Proceedings of the IEEE， 1980， 68（12）： 1497-1514.

[2] GRIGGS J R， YEH R K. Labelling graphs with a condition at distance 2［J］. SIAM Journal on Discrete Mathematics， 1992， 5（4）： 586-595.

[3] CHANG G J， KUO D. The L ( 2,1 ) -labeling problem on graphs［J］. SIAM Journal on Discrete Mathematics， 1996， 9（2）： 309-316.

[4] LIU D D， ZHU X D. Multilevel distance labelings for paths and cycles［J］. SIAM Journal on Discrete Mathematics， 2005， 19（3）： 610-621.

[5] LIU D D. Radio number for trees［J］. Discrete Mathematics， 2008， 308（7）： 1153-1164.

[6] LIU D D， SAHA L， DAS S. Improved lower bounds for the radio number of trees［J］. Theoretical Computer Science， 2021， 851： 1-13.

[7] MORRIS-RIVERA M， TOMOVA M， WYELS C， et al. The radio number of C n ⊗ C n ［J］. Ars Combinatoria， 2015， 120： 7-21.

[8] KIM B M， HWANG W， SONG B C. Radio number for the product of a path and a complete graph［J］. Journal of Combinatorial Optimization， 2015， 30（1）： 139-149.

[9] BANTVA D. Radio number for middle graph of paths［J］. Electronic Notes in Discrete Mathematics， 2017， 63： 93-100.

[10] BANTVA D. Optimal radio labelings of graphs［J］. Discrete Mathematics Letters， 2022， 10： 91-98.

[11] SARASWATHI M， MEERA K N. Radio mean labeling of paths and its total graph［J］. Turkish Journal of Computer and Mathematics Education， 2021， 12（1）： 343- 350.

[12] ELROKH A， BADR E， AL-SHAMIRI M M A， et al. Upper bounds of radio number for triangular snake and double triangular snake graphs［J］. Journal of Mathematics， 2022（1）： 3635499.

[13] AASI M S， ASIF M， IQBAL T， et al. Radio labelings of lexicographic product of some graphs［J］. Journal of Mathematics， 2021： 9177818.

[14] ADEFOKUN T C， AJAYI D O. Bounds of the radio number of stacked book graph with odd paths［J］. International Journal of Mathematical Combinatorics， 2023， 1： 87-97.

[15] ZHANG F， NAZEER S， HABIB M， et al. Radio number for generalized Petersen graphs P ( n , 2 ) ［J］. IEEE Access， 2019， 7： 142000-142008.

[16] QI H X， NAZEER S， KOUSAR I， et al. Radio labeling for strong product K 3 ⊗ P n ［J］. IEEE Access， 2020， 8： 109801-109806.

[17] VAIDYA S K， BANTVAB D. Radio number for strong product P 2 ⊗ P n ［J］. Malaya Journal of Matematik， 2013， 2（1）： 29-36.

[18] CHARTRAND G， ERWIN D， ZHANG P， et al. Radio labelings of graphs［J］. Bulletin of the Institute of Combinatorics and Its Applications， 2001， 33： 77-85.

[19] SABIDUSSI G. Graph multiplication［J］. Mathematische Zeitschrift， 1959， 72（1）： 446-457.

[20] NIRANJAN P K， KOLA S R. The radio number for some classes of the Cartesian products of complete graphs and cycles［J］. Journal of Physics： Conference Series， 2021， 1850（1）： 012014.

基金资助

国家自然科学基金资助项目(11551002)

青海省自然科学基金资助项目(2019-ZJ-7093)