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

Basic Information

  • Paper ID: 2511.05607
  • Title: Further Results on Signed Product Cordial Labeling
  • Authors: S. Soundar Rajan, J. Baskar Babujee
  • Classification: math.CO (Combinatorics)
  • Published Journal: Revista Argentina de Clínica Psicológica, 2023, Vol. XXXII, N°1, 01-04
  • Author Affiliation: Department of Mathematics, Anna University, MIT Campus, Chennai-44, India
  • Paper Link: https://arxiv.org/abs/2511.05607
  • DOI: 10.24205/03276716.2023.7001

Abstract

This paper investigates the signed product cordial labeling problem for various graph structures, specifically including: the split graph of bull graphs, the split graph of star graphs K₁,ₙ, the square of path graphs Pₙ², the corona graph Cₙ ⊙ 3k₁, and graph structures formed by connecting two helm graphs H₄ through paths of arbitrary length. The authors prove that all these graph structures admit signed product cordial labelings.

Research Background and Motivation

Research Problem

This paper addresses the signed product cordial labeling problem for graphs, which represents an important branch of graph labeling theory in graph theory. Specifically, it seeks to determine whether particular graph structures admit signed product cordial labelings—that is, whether vertices can be assigned labels from {1, -1} such that the distribution of vertex and edge labels satisfies specific balance conditions.

Significance of the Problem

  1. Theoretical Significance: Graph labeling represents a fusion of graph theory and number theory, possessing profound mathematical theoretical value
  2. Practical Applications: Graph labeling has applications in multiple practical domains, including:
    • Radar pulse code design
    • Neural networks
    • Communication network addressing systems
    • Frequency allocation problems
    • Graph decomposition problems
    • Game and puzzle design

Current Research Status

  • Cahit (1987) developed the concept of cordial labeling from graceful and harmonious labelings
  • Babujee and Loganathan (2011) introduced signed product cordial labeling and proved that path graphs, trees, and cycle graphs admit such labelings
  • This paper represents a further extension of this theory, investigating more complex graph structures

Research Motivation

Existing research has primarily focused on basic graph structures, with limited investigation of more complex constructions such as split graphs, square graphs, and corona graphs. This paper aims to fill this gap and extend the applicability of signed product cordial labeling.

Core Contributions

The main contributions of this paper include:

  1. Proved that the split graph of star graphs Spltg(K₁,ₙ) admits signed product cordial labeling, providing explicit labeling schemes and complete analysis of vertex/edge conditions
  2. Proved that the split graph of bull graphs Spltg(BG) admits signed product cordial labeling, representing the first such investigation for split graphs of bull graphs
  3. Proved that the square of path graphs Pₙ² (n≥3) admits signed product cordial labeling, discussing separately the cases where n is odd and even
  4. Proved that the corona graph Cₙ ⊙ 3k₁ admits signed product cordial labeling, providing systematic labeling construction methods
  5. Proved that graph structures formed by connecting two helm graphs H₄ through paths of arbitrary length admit signed product cordial labeling, demonstrating the flexibility of this labeling method
  6. Provided detailed diagrams that intuitively display signed product cordial labeling schemes for various graph structures

Detailed Methodology

Task Definition

Definition of Signed Product Cordial Labeling:

For a graph G, define a vertex labeling function α: V(G) → {1, -1} and an induced edge labeling function α*: E(G) → {1, -1}, where:

  • α*(uv) = α(u) · α(v) (the edge label equals the product of its two endpoint labels)

A labeling is called a signed product cordial labeling if the following conditions are satisfied:

  1. |vα(-1) - vα(1)| ≤ 1 (the difference between the number of vertices labeled -1 and 1 does not exceed 1)
  2. |eα*(-1) - eα*(1)| ≤ 1 (the difference between the number of edges labeled -1 and 1 does not exceed 1)

Where:

  • vα(1): the number of vertices labeled 1
  • vα(-1): the number of vertices labeled -1
  • eα*(1): the number of edges labeled 1
  • eα*(-1): the number of edges labeled -1

Key Graph Structure Definitions

  1. Split Graph Spltg(G): For each vertex v in graph G, add a new vertex v' such that Nbhd(v) = Nbhd(v') (the new vertex has the same neighborhood as the original vertex)
  2. Bull Graph: An undirected planar triangular graph with 5 vertices
  3. Square of Path Graph Pₙ²: Obtained from path Pₙ by connecting pairs of vertices at distance 2
  4. Corona Graph G₁ ⊙ G₂: Take one copy of G₁ and n₁ copies of G₂, connecting the i-th vertex of G₁ to all vertices of the i-th copy of G₂
  5. Helm Graph Hₙ: Obtained from wheel graph Wₙ by adding a pendant edge at each vertex of the wheel rim

Labeling Construction Methods

Theorem 2.1: Split Graph of Star Graphs Spltg(K₁,ₙ)

Graph Structure:

  • The original star graph K₁,ₙ has vertex set {v₀, v₁, ..., vₙ}, where v₀ is the central vertex
  • The split graph has vertex set: {vᵢ: 0≤i≤n} ∪ {vᵢ': 0≤i≤n}
  • Edge set: {v₀vᵢ} ∪ {v₀vᵢ'} ∪ {v₀'vᵢ'}, 0≤i≤n

Labeling Scheme:

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

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

Verification Results (Table 1):

  • When 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
  • When 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

Theorem 2.2: Split Graph of Bull Graphs

Labeling Scheme:

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

Verification Results:

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

Theorem 2.3: Square of Path Graphs Pₙ²

Labeling Scheme:

α(vᵢ) = {  1,  i is odd
         -1,  i is even  }

Induced Edge Labeling:

  • α*(vᵢvᵢ₊₁): adjacent vertices have different labels, thus -1
  • α*(vᵢvᵢ₊₂): vertices at distance 2 have the same label, thus 1

Verification Results:

  • n is even: vα(1)=n/2, vα(-1)=n/2, eα*(1)=n-2, eα*(-1)=n-1
  • n is odd: vα(1)=(n+1)/2, vα(-1)=(n-1)/2, eα*(1)=n-2, eα*(-1)=n-1
  • Both cases satisfy the conditions

Theorem 2.4: Corona Graph Cₙ ⊙ 3k₁

Labeling Scheme:

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

Induced Edge Labeling:

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

Verification Results:

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

Theorem 2.5: Two H₄ Connected Through a Path

Labeling Strategy:

  1. Interior vertices of the first H₄ are labeled 1, exterior pendant vertices are labeled -1
  2. Interior vertices of the second H₄ are labeled -1, exterior pendant vertices are labeled 1
  3. Vertices of path Pₖ are assigned alternating labels:
    • u₁ = uₙ = 1 (endpoints)
    • α(uᵢ) = 1 (i is even)
    • α(uᵢ) = -1 (i is odd)

Technical Innovation Points

  1. Systematic Labeling Construction Methods: Designed corresponding labeling strategies for different graph structures, reflecting deep understanding of graph structural properties
  2. Completeness of Case Analysis: For graphs like Pₙ², separately discussed cases where n is odd and even, ensuring proof completeness
  3. Modular Design Philosophy: For composite graph structures (such as two helm graphs connected through a path), employed modular labeling strategies, first labeling each module, then handling connection parts
  4. Clever Utilization of Edge Labeling: Through the product rule α*(uv) = α(u)·α(v), exploited the multiplicative properties of 1 and -1 (same sign yields 1, different signs yield -1) to control edge label distribution

Experimental Setup

Characteristics of Graph-Theoretic Proofs

This paper is pure mathematical theoretical research, employing rigorous mathematical proof methods rather than experimental verification. Each theorem's proof includes:

  1. Explicit Definition of Graph Structure: Precisely describing vertex and edge sets
  2. Construction of Labeling Scheme: Providing concrete labeling functions
  3. Condition Verification: Proving satisfaction of the two signed product cordial labeling conditions through counting
  4. Graphical Illustration: Providing graphical displays of concrete examples

Verification Methods

Quantitative Analysis:

  • Precisely calculating values of vα(1), vα(-1), eα*(1), eα*(-1)
  • Verifying |vα(-1) - vα(1)| ≤ 1 and |eα*(-1) - eα*(1)| ≤ 1

Case Analysis:

  • Classifying based on parameter parity (e.g., n odd/even)
  • Ensuring all cases are covered

Graphical Verification

The paper provides the following diagrams:

  • Figure 1: Signed product cordial labeling of Spltg(K₁,₈)
  • Figure 2: Signed product cordial labeling of Spltg(BG)
  • Figure 3: Signed product cordial labeling of P₈²
  • Figure 4: Signed product cordial labeling of Cₙ ⊙ 3k₁
  • Figure 5: Signed product cordial labeling of two H₄ connected through P₅

These diagrams intuitively demonstrate the validity of the labeling schemes.

Experimental Results

Main Results

The paper successfully proves that the following 5 classes of graph structures admit signed product cordial labeling:

  1. Split Graph of Star Graphs Spltg(K₁,ₙ)
    • Applicable for arbitrary n
    • Vertex condition: always satisfies |vα(-1) - vα(1)| = 0
    • Edge condition: difference is 0 when n is even, 1 when n is odd
  2. Split Graph of Bull Graphs Spltg(BG)
    • Fixed 5-vertex graph structure
    • |vα(1) - vα(-1)| = 0
    • |eα*(1) - eα*(-1)| = 1
  3. Square of Path Graphs Pₙ² (n≥3)
    • Applicable for all n≥3
    • Vertex condition: difference is 0 when n is even, 1 when n is odd
    • Edge condition: always |eα*(-1) - eα*(1)| = 1
  4. Corona Graph Cₙ ⊙ 3k₁
    • Applicable for arbitrary n
    • Perfect balance: vertex and edge label quantities are completely equal
  5. Two H₄ Connected Through Paths of Arbitrary Length
    • Applicable for arbitrary path lengths
    • Demonstrates method flexibility and extensibility

Results Analysis

Theoretical Completeness:

  • All proofs are constructive, providing explicit labeling schemes
  • Proof processes are rigorous, covering all possible parameter cases

Labeling Efficiency:

  • Most cases achieve perfect balance in vertex or edge labeling (difference of 0)
  • Even when imbalanced, differences are strictly controlled within 1

Method Universality:

  • Applicable from simple graphs (star graphs, bull graphs) to complex graphs (corona graphs, composite graphs)
  • Demonstrates the broad applicability of signed product cordial labeling

Case Studies

Taking Spltg(K₁,₈) as an example (Figure 1):

  • Original star graph K₁,₈ has 9 vertices (1 center + 8 leaves)
  • Split graph has 18 vertices, 24 edges
  • Labeling result: vα(1) = 9, vα(-1) = 9 (perfect balance)
  • Edge labeling: eα*(1) = 12, eα*(-1) = 12 (perfect balance)

Taking P₈² as an example (Figure 3):

  • 8 vertices, 13 edges
  • Labeling result: vα(1) = 4, vα(-1) = 4
  • Edge labeling: eα*(1) = 6, eα*(-1) = 7

Related Work

Development of Graph Labeling Theory

  1. Graceful and Harmonious Labeling
    • Early research in graph labeling theory
    • Cahit (1987) proposed cordial labeling based on this foundation
  2. Cordial Labeling
    • Proposed by Cahit (1987)
    • A weakened version of graceful and harmonious labeling
    • Uses {0, 1} labels, requiring balance in vertex and edge labeling
  3. Signed Product Cordial Labeling
    • Introduced by Babujee and Loganathan (2011)
    • Uses {1, -1} labels instead of {0, 1}
    • Edge labels defined through products: α*(uv) = α(u)·α(v)
    • Already proven for path graphs, trees, and cycle graphs

Positioning of This Paper

Relationship to Prior Work:

  • Directly inherits the signed product cordial labeling definition from Babujee and Loganathan (2011)
  • Extends known results by investigating more complex graph structures

Research Progress:

  • Extends from basic graphs (paths, trees, cycles) to derived graphs (split graphs, square graphs)
  • Extends from single graphs to composite graphs (corona graphs, connected graphs)
  • Provides systematic construction methods rather than merely existence proofs

Application Background

The paper cites practical applications of graph labeling (Hale, 1980):

  • Frequency allocation problems
  • Radar pulse encoding
  • Communication network addressing
  • Neural networks

As well as game and puzzle applications (Tuza, 2017).

Conclusions and Discussion

Main Conclusions

  1. Theoretical Extension: This paper successfully extends signed product cordial labeling theory to 5 new classes of graph structures, significantly enriching research results in this field
  2. Constructive Proofs: All proofs are constructive, not only proving existence but also providing explicit labeling algorithms
  3. Methodological Contribution: Demonstrates how to design labeling strategies for different graph structures, providing methodological guidance for subsequent research
  4. Completeness: Through case analysis (e.g., n's parity), ensures proof completeness and rigor

Limitations

  1. Limited Research Scope:
    • Only investigates specific graph structure classes
    • Does not provide unified conclusions for more general graph classes (e.g., arbitrary split graphs, arbitrary corona graphs)
  2. Lack of Necessary and Sufficient Conditions:
    • Paper proves that certain graphs admit signed product cordial labeling (sufficiency)
    • Does not discuss which graphs do not admit such labeling (necessity)
    • Lacks characterization of necessary and sufficient conditions for graphs admitting signed product cordial labeling
  3. Algorithm Complexity Not Discussed:
    • Does not analyze algorithm complexity for finding signed product cordial labelings
    • Computational complexity of determining whether arbitrary graphs admit such labelings remains unknown
  4. Practical Applications Not Developed:
    • Although application domains are mentioned, specific applications are not demonstrated
    • Lacks modeling processes from practical problems to graph labeling
  5. Limited Theoretical Depth:
    • Primarily constructive proofs, lacking deeper theoretical analysis
    • Does not explore intrinsic connections between different graph structures
    • Lacks unified theoretical framework

Future Directions

Based on this research, possible future research directions include:

  1. More General Graph Classes:
    • Investigate whether split graphs of arbitrary graphs admit signed product cordial labeling
    • Explore labeling properties under other graph operations (Cartesian products, tensor products)
  2. Necessary and Sufficient Conditions:
    • Seek necessary and sufficient conditions for graphs admitting signed product cordial labeling
    • Characterize properties of graphs not admitting such labeling
  3. Algorithm Research:
    • Design efficient algorithms determining whether graphs admit signed product cordial labeling
    • Study problem computational complexity (NP-completeness, etc.)
  4. Variant Research:
    • Investigate other label sets (e.g., {-1, 0, 1})
    • Explore different edge labeling rules
  5. Application Research:
    • Apply theoretical results to concrete problems (frequency allocation, network design, etc.)
    • Establish connections between practical problems and graph labeling

In-Depth Evaluation

Strengths

  1. Systematic Research:
    • Investigates multiple different types of graph structures, demonstrating comprehensiveness
    • Each theorem includes detailed proofs and diagrams, facilitating understanding
    • Case analysis is complete, considering different parameter values
  2. Constructive Proofs:
    • All proofs provide explicit labeling schemes
    • Proves not only existence but also provides concrete construction methods
    • Facilitates practical application and further research
  3. Method Innovation:
    • Designed corresponding labeling strategies for different graph structures
    • Demonstrates how to exploit graph symmetry and structural properties
    • Clever application of modular thinking in composite graph labeling
  4. Diagram Clarity:
    • Each theorem includes diagrams of concrete examples
    • Intuitively demonstrates validity of labeling schemes
    • Helps readers understand abstract labeling concepts
  5. Theory Extensibility:
    • Progressive research from simple to complex graphs
    • Provides good foundation for subsequent research
    • Methods possess certain generalizability

Weaknesses

  1. Insufficient Theoretical Depth:
    • Primarily case studies, lacking unified theoretical framework
    • Does not explore intrinsic connections between different graph structures
    • Lacks deep analysis of the essence of signed product cordial labeling
  2. Limited Result Scope:
    • Only investigates specific graph classes, limited universality
    • Does not provide general criteria for graphs admitting signed product cordial labeling
    • Lacks deep explanation for why these graphs admit labeling
  3. Single Proof Technique:
    • All proofs use direct construction + verification
    • Lacks more advanced proof techniques (induction, proof by contradiction, etc.)
    • Does not leverage deep results from graph theory
  4. Missing Experimental Verification:
    • Although theoretical research, could verify more examples computationally
    • Lacks labeling experiments on large-scale graphs
    • Does not discuss uniqueness or diversity of labeling schemes
  5. Writing Issues:
    • Theorem 2.4 appears twice (Corona and Helm graphs), numbering error
    • Some definitions lack precision (e.g., bull graph definition is vague)
    • Lacks deep exposition of research motivation
  6. Insufficient Application Discussion:
    • Although application domains are mentioned, lacks concrete development
    • Lacks modeling processes from practical problems to graph labeling
    • Does not explain how these results solve practical problems

Impact Assessment

Contribution to the Field:

  • Incremental Contribution: Extends known classes of graphs admitting signed product cordial labeling
  • Methodological Value: Provides methods for studying labeling of new graph classes
  • Theory Refinement: Enriches content of graph labeling theory

Practical Value:

  • High Theoretical Research Value: Provides graph theorists with new research objects
  • Practical Application Value Pending Verification: Lacks concrete application cases
  • Teaching Value: Can serve as teaching case for graph labeling theory

Reproducibility:

  • Proofs Verifiable: All proofs are constructive, easily verifiable
  • Clear Diagrams: Provides concrete examples, facilitating understanding
  • Methods Generalizable: Labeling strategies applicable to similar graph structures

Academic Impact:

  • Published in interdisciplinary journal (mathematics paper in psychology journal is relatively rare)
  • Cites classical literature in the field
  • Provides foundation for subsequent research

Applicable Scenarios

  1. Theoretical Research:
    • Researchers in graph labeling theory can learn from this paper's methods
    • Can serve as starting point for investigating more complex graph structures
    • Suitable as supplementary material for graph theory courses
  2. Combinatorial Optimization:
    • May apply to graph coloring, graph decomposition problems
    • Related to problems involving graph symmetry and balance
  3. Network Design:
    • If correspondence between practical networks and these graph structures can be established
    • May apply to network resource allocation, frequency planning, etc.
  4. Algorithm Design:
    • Can serve as test cases for graph labeling algorithms
    • Verify effectiveness of heuristic algorithms

References

Key literature cited in the paper:

  1. Babujee, J. B., & Loganathan, S. (2011). On signed product cordial labeling. Applied Mathematics, 2(12), 1525-1530.
    • Original paper introducing signed product cordial labeling
  2. Cahit, I. (1987). Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs. Ars combinatoria, 23, 201-207.
    • Foundational work on cordial labeling
  3. Beineke, L. W., & Hegde, S. M. (2001). Strongly multiplicative graphs. Discussiones Mathematicae Graph Theory, 21(1), 63-75.
    • Survey of graph labeling theory
  4. Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12), 1497-1514.
    • Applications of graph labeling in frequency allocation
  5. Tuza, Z. (2017). Graph labeling games. Electronic Notes in Discrete Mathematics, 60, 61-68.
    • Applications of graph labeling in games

Summary

This paper represents solid extension research in signed product cordial labeling theory. The authors systematically investigate signed product cordial labeling for 5 classes of graph structures, providing explicit labeling schemes through constructive proofs. The paper's main value lies in extending known classes of graphs admitting signed product cordial labeling and providing methodological guidance for investigating new graph classes.

However, the paper has obvious limitations: it lacks a unified theoretical framework, is limited to case studies, does not deeply explore the essential reasons why graphs admit such labeling, and does not provide necessary and sufficient conditions. Future research could deepen in the following directions: establishing more general theoretical frameworks, investigating algorithm complexity, exploring practical applications, etc.

Overall, this is a qualified mathematical theoretical research paper that makes incremental contributions to graph labeling theory, though it has considerable room for improvement in theoretical depth and practical value.