2025-11-22T04:01:16.401684

Further Results on Signed Product Cordial Labeling

Rajan, Babujee
In this paper, we look into Signed Product Cordial Labeling for Splitting Graphs of Bull graph and Splitting graph of Star graph , Square of Path graph, Coronaand also for the graph obtained by joining two copies of Helm by a Path of arbitrary length.
academic

Further Results on Signed Product Cordial Labeling

基本信息

  • 论文ID: 2511.05607
  • 标题: Further Results on Signed Product Cordial Labeling
  • 作者: S. Soundar Rajan, J. Baskar Babujee
  • 分类: math.CO (组合数学)
  • 发表期刊: Revista Argentina de Clínica Psicológica, 2023, Vol. XXXII, N°1, 01-04
  • 作者单位: Department of Mathematics, Anna University, MIT Campus, Chennai-44, India
  • 论文链接: https://arxiv.org/abs/2511.05607
  • DOI: 10.24205/03276716.2023.7001

摘要

本文研究了多种图结构的符号积调和标号(Signed Product Cordial Labeling)问题，具体包括：Bull图的分裂图、星图K₁,ₙ的分裂图、路径图的平方Pₙ²、冠图Cₙ ⊙ 3k₁，以及通过任意长度路径连接两个Helm图H₄的图结构。作者证明了这些图结构都允许符号积调和标号。

研究背景与动机

研究问题

本文研究图的符号积调和标号问题，这是图论中图标号理论的一个重要分支。具体要解决的问题是：判断特定图结构是否允许符号积调和标号，即能否为图的顶点分配标号{1, -1}，使得顶点和边的标号分布满足特定的平衡条件。

问题的重要性

  1. 理论意义：图标号是图论与数论的融合领域，具有深刻的数学理论价值
  2. 实际应用：图标号在多个实际领域有应用，包括：
    • 雷达脉冲编码设计
    • 神经网络
    • 通信网络寻址系统
    • 频率分配问题
    • 图分解问题
    • 游戏和谜题设计

现有研究状况

  • Cahit (1987)从优美标号和调和标号发展出调和标号(Cordial labeling)概念
  • Babujee和Loganathan (2011)引入符号积调和标号，并证明了路径图、树和圈图允许此类标号
  • 本文是对该理论的进一步扩展，研究更复杂的图结构

研究动机

现有研究主要集中在基础图结构，对于分裂图、平方图、冠图等复杂构造的研究较少。本文旨在填补这一空白，扩展符号积调和标号的适用范围。

核心贡献

本文的主要贡献包括：

  1. 证明了星图K₁,ₙ的分裂图Spltg(K₁,ₙ)允许符号积调和标号，并给出了明确的标号方案和顶点/边条件的完整分析
  2. 证明了Bull图的分裂图Spltg(BG)允许符号积调和标号，这是首次对Bull图的分裂图进行此类研究
  3. 证明了路径图的平方Pₙ²(n≥3)允许符号积调和标号，分别讨论了n为奇数和偶数的情况
  4. 证明了冠图Cₙ ⊙ 3k₁允许符号积调和标号，给出了系统的标号构造方法
  5. 证明了通过任意长度路径连接两个Helm图H₄的图结构允许符号积调和标号，展示了该标号方法的灵活性
  6. 提供了详细的图示，直观展示了各种图结构的符号积调和标号方案

方法详解

任务定义

符号积调和标号的定义：

对于图G，定义顶点标号函数α: V(G) → {1, -1}和诱导边标号函数α*: E(G) → {1, -1}，其中：

  • α*(uv) = α(u) · α(v)（边标号等于其两个端点标号的乘积）

如果满足以下条件，则称该标号为符号积调和标号：

  1. |vα(-1) - vα(1)| ≤ 1（标号为-1和1的顶点数量差不超过1）
  2. |eα*(-1) - eα*(1)| ≤ 1（标号为-1和1的边数量差不超过1）

其中：

  • vα(1)：标号为1的顶点数量
  • vα(-1)：标号为-1的顶点数量
  • eα*(1)：标号为1的边数量
  • eα*(-1)：标号为-1的边数量

关键图结构定义

  1. 分裂图Spltg(G)：对图G的每个顶点v，添加一个新顶点v'，使得Nbhd(v) = Nbhd(v')（新顶点与原顶点有相同的邻域）
  2. Bull图：具有5个顶点的无向平面三角形图
  3. 路径图的平方Pₙ²：从路径Pₙ通过连接距离为2的顶点对得到
  4. 冠图G₁ ⊙ G₂：取G₁的一个副本和n₁个G₂的副本，将G₁的第i个顶点与第i个G₂副本的所有顶点连接
  5. Helm图Hₙ：从轮图Wₙ在轮缘的每个顶点添加一条悬挂边得到

标号构造方法

定理2.1：星图分裂图Spltg(K₁,ₙ)

图结构：

  • 原星图K₁,ₙ有顶点集{v₀, v₁, ..., vₙ}，其中v₀是中心顶点
  • 分裂图有顶点集：{vᵢ: 0≤i≤n} ∪ {vᵢ': 0≤i≤n}
  • 边集：{v₀vᵢ} ∪ {v₀vᵢ'} ∪ {v₀'vᵢ'}，0≤i≤n

标号方案：

α(vᵢ) = {  1,  i ≡ 1 (mod 2)
         -1,  i ≡ 0 (mod 2)  }  对于1≤i≤n

α(vᵢ') = -α(vᵢ)
α(v₀) = 1
α(v₀') = -1

验证结果（表1）：

  • 当n≡0(mod 2)时：vα(1)=n+1, vα(-1)=n+1, |vα(-1)-vα(1)|=0
    • eα*(1)=3n/2, eα*(-1)=3n/2, |eα*(-1)-eα*(1)|=0
  • 当n≡1(mod 2)时：vα(1)=n+1, vα(-1)=n+1, |vα(-1)-vα(1)|=0
    • eα*(1)=(3n+1)/2, eα*(-1)=(3n-1)/2, |eα*(-1)-eα*(1)|=1

定理2.2：Bull图的分裂图

标号方案：

α(v₁) = -1
α(vᵢ) = {  1,  i ≡ 0 (mod 2)
         -1,  i ≡ 0 (mod 3)
          1,  i ≡ 2 (mod 3)  }
α(vᵢ') = -α(vᵢ)

验证结果：

  • vα(1) = 5, vα(-1) = 5, |vα(1) - vα(-1)| = 0
  • eα*(1) = 8, eα*(-1) = 7, |eα*(1) - eα*(-1)| = 1

定理2.3：路径图的平方Pₙ²

标号方案：

α(vᵢ) = {  1,  i是奇数
         -1,  i是偶数  }

诱导边标号：

  • α*(vᵢvᵢ₊₁)：相邻顶点标号不同，故为-1
  • α*(vᵢvᵢ₊₂)：距离为2的顶点标号相同，故为1

验证结果：

  • n为偶数：vα(1)=n/2, vα(-1)=n/2, eα*(1)=n-2, eα*(-1)=n-1
  • n为奇数：vα(1)=(n+1)/2, vα(-1)=(n-1)/2, eα*(1)=n-2, eα*(-1)=n-1
  • 两种情况下都满足条件

定理2.4：冠图Cₙ ⊙ 3k₁

标号方案：

ux = 1,   1≤x≤n
vx = -1,  1≤x≤n
wx = 1,   1≤x≤n
tx = -1,  1≤x≤n

诱导边标号：

α*(uxux+1) = 1
α*(uxvx) = -1
α*(uxwx) = 1
α*(uxtx) = -1
α*(uun) = 1

验证结果：

  • vα(1) = n/2, vα(-1) = n/2
  • eα*(1) = n/2, eα*(-1) = n/2

定理2.5：两个H₄通过路径连接

标号策略：

  1. 第一个H₄的内部顶点标号为1，外部悬挂顶点标号为-1
  2. 第二个H₄的内部顶点标号为-1，外部悬挂顶点标号为1
  3. 路径Pₖ的顶点标号交替分配：
    • u₁ = uₙ = 1（两端点）
    • α(uᵢ) = 1 (i为偶数)
    • α(uᵢ) = -1 (i为奇数)

技术创新点

  1. 系统的标号构造方法：针对不同图结构的特点，设计了相应的标号策略，体现了对图结构性质的深刻理解
  2. 分类讨论的完整性：对于Pₙ²等图，分别讨论了n为奇数和偶数的情况，确保证明的完整性
  3. 模块化设计思想：对于复合图结构（如两个Helm图通过路径连接），采用模块化标号策略，先标号各个模块，再处理连接部分
  4. 边标号的巧妙利用：通过乘积规则α*(uv) = α(u)·α(v)，利用1和-1的乘法性质（同号为1，异号为-1）来控制边标号的分布

实验设置

图论证明的特点

本文是纯数学理论研究，采用严格的数学证明方法，而非实验验证。每个定理的证明包括：

  1. 图结构的明确定义：精确描述顶点集和边集
  2. 标号方案的构造：给出具体的标号函数
  3. 条件验证：通过计数证明满足符号积调和标号的两个条件
  4. 图示说明：提供具体例子的图形展示

验证方法

定量分析：

  • 精确计算vα(1)、vα(-1)、eα*(1)、eα*(-1)的值
  • 验证|vα(-1) - vα(1)| ≤ 1和|eα*(-1) - eα*(1)| ≤ 1

分类讨论：

  • 根据参数的奇偶性进行分类（如n为奇数/偶数）
  • 确保所有情况都被覆盖

图示验证

论文提供了以下图示：

  • 图1：Spltg(K₁,₈)的符号积调和标号
  • 图2：Spltg(BG)的符号积调和标号
  • 图3：P₈²的符号积调和标号
  • 图4：Cₙ ⊙ 3k₁的符号积调和标号
  • 图5：两个H₄通过P₅连接的符号积调和标号

这些图示直观地展示了标号方案的有效性。

实验结果

主要结果

本文成功证明了以下5类图结构允许符号积调和标号：

  1. 星图的分裂图Spltg(K₁,ₙ)
    • 适用于任意n
    • 顶点条件：总是满足|vα(-1) - vα(1)| = 0
    • 边条件：n为偶数时差值为0，n为奇数时差值为1
  2. Bull图的分裂图Spltg(BG)
    • 固定的5顶点图结构
    • |vα(1) - vα(-1)| = 0
    • |eα*(1) - eα*(-1)| = 1
  3. 路径图的平方Pₙ²（n≥3）
    • 适用于所有n≥3
    • 顶点条件：n为偶数时差值为0，n为奇数时差值为1
    • 边条件：总是|eα*(-1) - eα*(1)| = 1
  4. 冠图Cₙ ⊙ 3k₁
    • 适用于任意n
    • 完美平衡：顶点和边的标号数量完全相等
  5. 两个H₄通过任意长度路径连接
    • 适用于任意路径长度
    • 展示了方法的灵活性和可扩展性

结果分析

理论完备性：

  • 所有证明都是构造性的，给出了明确的标号方案
  • 证明过程严谨，涵盖了所有可能的参数情况

标号效率：

  • 大多数情况下实现了顶点或边标号的完美平衡（差值为0）
  • 即使不平衡，差值也严格控制在1以内

方法的普适性：

  • 从简单图（星图、Bull图）到复杂图（冠图、复合图）都适用
  • 证明了符号积调和标号的广泛适用性

案例展示

以**Spltg(K₁,₈)**为例（图1）：

  • 原星图K₁,₈有9个顶点（1个中心+8个叶子）
  • 分裂图有18个顶点，24条边
  • 标号结果：vα(1) = 9, vα(-1) = 9（完美平衡）
  • 边标号：eα*(1) = 12, eα*(-1) = 12（完美平衡）

以P₈²为例（图3）：

  • 8个顶点，13条边
  • 标号结果：vα(1) = 4, vα(-1) = 4
  • 边标号：eα*(1) = 6, eα*(-1) = 7

相关工作

图标号理论发展

  1. 优美标号和调和标号（Graceful and Harmonious Labeling）
    • 图标号理论的早期研究
    • Cahit (1987)在此基础上提出调和标号
  2. 调和标号（Cordial Labeling）
    • Cahit (1987)提出
    • 是优美标号和调和标号的弱化版本
    • 使用{0, 1}标号，要求顶点和边标号的平衡性
  3. 符号积调和标号（Signed Product Cordial Labeling）
    • Babujee和Loganathan (2011)引入
    • 使用{1, -1}标号替代{0, 1}
    • 边标号通过乘积定义：α*(uv) = α(u)·α(v)
    • 已证明路径图、树和圈图允许此类标号

本文的定位

与前人工作的关系：

  • 直接继承Babujee和Loganathan (2011)的符号积调和标号定义
  • 扩展了已知结果，研究更复杂的图结构

研究的进展：

  • 从基础图（路径、树、圈）扩展到派生图（分裂图、平方图）
  • 从单一图扩展到复合图（冠图、连接图）
  • 提供了系统的构造方法而非仅仅存在性证明

应用背景

论文引用了图标号的实际应用（Hale, 1980）：

  • 频率分配问题
  • 雷达脉冲编码
  • 通信网络寻址
  • 神经网络

以及游戏和谜题应用（Tuza, 2017）。

结论与讨论

主要结论

  1. 理论扩展：本文成功将符号积调和标号理论扩展到5类新的图结构，显著丰富了该领域的研究成果
  2. 构造性证明：所有证明都是构造性的，不仅证明了存在性，还给出了明确的标号算法
  3. 方法论贡献：展示了如何针对不同图结构设计标号策略，为后续研究提供了方法论指导
  4. 完整性：通过分类讨论（如n的奇偶性），确保了证明的完整性和严谨性

局限性

  1. 研究范围有限：
    • 仅研究了特定的几类图结构
    • 对于更一般的图类（如任意分裂图、任意冠图）没有给出统一结论
  2. 缺乏充要条件：
    • 论文证明了某些图允许符号积调和标号（充分性）
    • 但没有讨论哪些图不允许此类标号（必要性）
    • 缺乏图允许符号积调和标号的充要条件刻画
  3. 算法复杂度未讨论：
    • 没有分析找到符号积调和标号的算法复杂度
    • 对于一般图，判定是否允许此类标号的计算复杂性未知
  4. 实际应用未展开：
    • 虽然提到了应用领域，但没有具体展示如何应用这些结果
    • 缺乏实际问题到图标号的建模过程
  5. 理论深度：
    • 主要是构造性证明，缺乏深层次的理论分析
    • 没有探讨不同图结构之间的内在联系
    • 缺乏统一的理论框架

未来方向

基于本文研究，可能的未来研究方向包括：

  1. 更一般的图类：
    • 研究任意图的分裂图是否允许符号积调和标号
    • 探索其他图运算（如笛卡尔积、张量积）下的标号性质
  2. 充要条件：
    • 寻找图允许符号积调和标号的充要条件
    • 刻画不允许此类标号的图的特征
  3. 算法研究：
    • 设计高效算法判定图是否允许符号积调和标号
    • 研究问题的计算复杂度（NP完全性等）
  4. 变体研究：
    • 研究其他标号集合（如{-1, 0, 1}）
    • 探索不同的边标号规则
  5. 应用研究：
    • 将理论结果应用到具体问题（频率分配、网络设计等）
    • 建立实际问题与图标号的联系

深度评价

优点

  1. 研究的系统性：
    • 研究了多种不同类型的图结构，展现了全面性
    • 每个定理都配有详细的证明和图示，便于理解
    • 分类讨论完整，考虑了参数的不同取值情况
  2. 证明的构造性：
    • 所有证明都给出了明确的标号方案
    • 不仅证明存在性，还提供了具体构造方法
    • 便于实际应用和进一步研究
  3. 方法的创新性：
    • 针对不同图结构设计了相应的标号策略
    • 展示了如何利用图的对称性和结构特点
    • 模块化思想在复合图标号中的应用很巧妙
  4. 图示的清晰性：
    • 每个定理都配有具体例子的图示
    • 直观展示了标号方案的有效性
    • 有助于读者理解抽象的标号概念
  5. 理论的扩展性：
    • 从简单图到复杂图的渐进研究
    • 为后续研究提供了良好的基础
    • 方法具有一定的可推广性

不足

  1. 理论深度不足：
    • 主要是个案研究，缺乏统一的理论框架
    • 没有探讨不同图结构之间的内在联系
    • 缺乏对符号积调和标号本质的深入分析
  2. 结果的局限性：
    • 仅研究了特定的几类图，普适性有限
    • 没有给出图允许符号积调和标号的一般性判据
    • 对于为什么这些图允许标号缺乏深层次解释
  3. 证明技巧单一：
    • 所有证明都是直接构造+验证
    • 缺乏更高级的证明技巧（如归纳、反证等）
    • 没有利用图论的深刻结果
  4. 实验验证缺失：
    • 虽然是理论研究，但可以通过计算机验证更多例子
    • 缺乏对大规模图的标号实验
    • 没有讨论标号方案的唯一性或多样性
  5. 写作问题：
    • 定理2.4出现两次（Corona和Helm图），编号错误
    • 某些定义不够精确（如Bull图的定义较模糊）
    • 缺乏对研究动机的深入阐述
  6. 应用讨论不足：
    • 虽然提到了应用领域，但没有具体展开
    • 缺乏从实际问题到图标号的建模过程
    • 没有说明这些结果如何解决实际问题

影响力评估

对领域的贡献：

  • 增量贡献：扩展了已知的符号积调和标号图类
  • 方法论价值：提供了研究新图类的标号方法
  • 理论完善：丰富了图标号理论的内容

实用价值：

  • 理论研究价值高：为图论研究者提供了新的研究对象
  • 实际应用价值待验证：缺乏具体应用案例
  • 教学价值：可作为图标号理论的教学案例

可复现性：

  • 证明可验证：所有证明都是构造性的，易于验证
  • 图示清晰：提供了具体例子，便于理解
  • 方法可推广：标号策略可应用于类似图结构

学术影响：

  • 发表在跨学科期刊（心理学期刊发表数学论文较罕见）
  • 引用了该领域的经典文献
  • 为后续研究提供了基础

适用场景

  1. 理论研究：
    • 图标号理论的研究者可以借鉴本文方法
    • 可作为研究更复杂图结构的起点
    • 适合作为图论课程的补充材料
  2. 组合优化：
    • 可能应用于图着色、图分解等问题
    • 与图的对称性、平衡性相关的问题
  3. 网络设计：
    • 如果能建立实际网络与这些图结构的对应关系
    • 可能用于网络资源分配、频率规划等
  4. 算法设计：
    • 可作为设计图标号算法的测试用例
    • 验证启发式算法的有效性

参考文献

论文引用的关键文献：

  1. Babujee, J. B., & Loganathan, S. (2011). On signed product cordial labeling. Applied Mathematics, 2(12), 1525-1530.
    • 提出符号积调和标号的原始论文
  2. Cahit, I. (1987). Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs. Ars combinatoria, 23, 201-207.
    • 调和标号的开创性工作
  3. Beineke, L. W., & Hegde, S. M. (2001). Strongly multiplicative graphs. Discussiones Mathematicae Graph Theory, 21(1), 63-75.
    • 图标号理论的综述
  4. Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12), 1497-1514.
    • 图标号在频率分配中的应用
  5. Tuza, Z. (2017). Graph labeling games. Electronic Notes in Discrete Mathematics, 60, 61-68.
    • 图标号在游戏中的应用

总结

本文是符号积调和标号理论的一篇扎实的扩展性研究工作。作者系统地研究了5类图结构的符号积调和标号问题，通过构造性证明给出了明确的标号方案。论文的主要价值在于扩展了已知的允许符号积调和标号的图类，并提供了研究新图类的方法论指导。

然而，论文也存在明显的局限性：缺乏统一的理论框架，仅限于个案研究，没有深入探讨图允许此类标号的本质原因，也没有给出充要条件。未来的研究可以在以下方向深入：建立更一般的理论框架、研究算法复杂度、探索实际应用等。

总体而言，这是一篇合格的数学理论研究论文，对图标号理论做出了增量贡献，但在理论深度和应用价值方面还有较大的提升空间。