Leech Graphs

Document Type : Original paper

Authors

1 Department of Mathematics, Federal Institute of Science and Technology, Angamaly-683577, Ernakulam District, Kerala, India

2 Department of Mathematics, Cochin University of Science and Technology,Cochin-22, Kerala,India

3 National Centre for Advanced Research in Discrete Mathematics, Kalasalingam University Anand Nagar, Krishnankoil-626 126, Tamil Nadu, India

Abstract

Let $t_p(G)$ denote the number of paths in a graph $G$ and let $f:E\rightarrow \mathbb{Z}^+$ be an edge labeling of $G$. The weight of a path $P$ is the sum of the labels assigned to the edges of $P$. If the set of weights of the paths in $G$ is $\{1,2,3,\dots,t_p(G)\}$, then $f$ is called a Leech labeling of $G$ and a graph which admits a Leech labeling is called a Leech graph. In this paper, we prove that the complete bipartite graphs $K_{2,n}$ and $K_{3,n}$ are not Leech graphs and determine the maximum possible value that can be given to an edge in the Leech labeling of a cycle.

Keywords

Main Subjects

References

[1] B. Calhoun, K. Ferland, L. Lister, and J. Polhill, Minimal distinct distance trees, J. Combin. Math. Combin. Comput. 61 (2007), 33–57.
[2] G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, vol. 22, Chapman & Hall London, 1996.
[3] D. Leach, Modular Leech trees of order at most 8, Int. J. Combin. 2014 (2014), Article ID: 218086. https://doi.org/10.1155/2014/218086
[4] D. Leach and M. Walsh, Generalized leech trees, J. Combin. Math. Combin. Comput. 78 (2011), 15–22.
[5] J. Leech, Another tree labeling problem, Amer. Math. Monthly 82 (1975), no. 9, 923–925.
[6] M. Ozen, H. Wang, and D. Yalman, Note on Leech-type questions of tree, Integers 16 (2016), #A21.
[7] L.A. Szekely, H. Wang, and Y. Zhang, Some non-existence results on Leech trees, Bull. Inst. Combin. Appl. 44 (2005), 37–45.
[8] H. Taylor, Odd path sums in an edge-labeled tree, Math. Magazine 50 (1977), no. 5, 258–259. https://doi.org/10.1080/0025570X.1977.11976658
[9] H. Taylor, A distinct distance set of 9 nodes in a tree of diameter 36, Discrete Math. 93 (1991), no. 2-3, 167–168. https://doi.org/10.1016/0012-365X(91)90252-W
[10] S. Varghese, A. Lakshmanan S., and S. Arumugam, Two classes of non-Leech trees, Electron. J. Graph Theory Appl. 8 (2020), no. 1, 205–210. https://doi.org/10.5614/ejgta.2020.8.1.15
[11] S. Varghese, A. Lakshmanan S., and S. Arumugam, Leech index of a tree, J. Discrete Math. Sci. Crypt. 25 (2022), no. 8,
2237–2247. https://doi.org/10.1080/09720529.2020.1800217
[12] S. Varghese, A. Lakshmanan S., and S. Arumugam, Two extensions of Leech labeling to the class of all graphs, AKCE Int. J. Graphs Comb. 19 (2022), no. 2, 159–165. http://doi.org/10.1080/09728600.2022.2084354
[13] S. Varghese, A. Lakshmanan S., and S. Arumugam, Leech labeling problem on tristar, AIP Conf. Proc. 2649 (2023), no. 1, ID: 020007. https://doi.org/10.1063/5.0114834
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 205-215

Files

Share

How to cite

Statistics