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 tp(G) denote the number of paths in a graph G and let f:E→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,…,tp(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 K2,n and K3,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