51视频

Mathematics and Statistics Vol. 13(5), pp. 269 - 278
DOI: 10.13189/ms.2025.130502
Reprint (PDF) (1184Kb)

Some Path and Star Related Discrete Graphs

Lekha Bijukumar(n茅e Lekha S) ^*
Department of Science and Humanities, Malla Reddy College of Engineering and Technology, India

ABSTRACT

This study investigates the existence of discrete and strong discrete labeling for several classes of path and star-related graphs, contributing to the broader field of graph labeling theory. A graph is said to admit a discrete labeling if its vertices can be assigned binary labels (0 and 1), such that each edge receives a label determined by the exclusive OR (XOR) of the labels of its incident vertices, subject to specified constraints. We first establish that the super subdivision of a path by the complete bipartite graph is discrete, demonstrating that replacing each edge of with preserves the discrete labeling property. Additionally, we prove that the square of a path , obtained by connecting vertices at a distance of at most two, also admits a discrete labeling. Further, we examine the shadow graph , constructed by duplicating and connecting each vertex to its copy's neighbors, and show that it is also discrete. Another variant, the graph formed by switching one pendant vertex in , is similarly proven to support discrete labeling. Beyond paths, we explore star-related graphs, confirming that the shadow graph of a star and the shadow graph of a bi-star both permit discrete labeling. Extending the concept, we introduce strong discrete labeling, which imposes the stricter requirement by adding one more constraint to discrete labeling. Under this stronger condition, we prove that the star graph admits a strong discrete labeling if and only if m is even, highlighting a parity-based constraint absent in standard discrete labeling. These findings expand the known families of graphs with discrete and strong discrete labeling, offering new insights into structural properties that facilitate such labeling. Potential applications include coding theory, network design, and algorithm optimization, while open questions remain regarding the extensibility of these results to other graph operations and more complex graph classes.

KEYWORDS
Discrete Labeling, Strong Discrete Labeling, Super Subdivision of a Graph, Square of a Graph, Shadow Graphs, Bistar

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Lekha Bijukumar(n茅e Lekha S) , "Some Path and Star Related Discrete Graphs," Mathematics and Statistics, Vol. 13, No. 5, pp. 269 - 278, 2025. DOI: 10.13189/ms.2025.130502.

(b). APA Format:
Lekha Bijukumar(n茅e Lekha S) (2025). Some Path and Star Related Discrete Graphs. Mathematics and Statistics, 13(5), 269 - 278. DOI: 10.13189/ms.2025.130502.