Optimal maximal graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Valencia College, Orlando, FL 32832, U. S. A.

2 Department of Mathematics & Statistics, College of Sciences, Imam Mohammad Ibn Saud Islamic University, Riyadh 11623, Saudi Arabia

Abstract

An optimal labeling of a graph with $n$ vertices and $m$ edges is an injective assignment of the first $n$ nonnegative integers to the vertices‎, ‎that induces‎, ‎for each edge‎, ‎a weight given by the sum of the labels of its end-vertices with the property that the set of all induced weights consists of the first $m$ positive integers‎. ‎We explore the connection of this labeling with other well-known functions such as super edge-magic and $\alpha$-labelings‎. ‎A graph with $n$ vertices is maximal when the number of edges is $2n-3$; all the results included in this work are about maximal graphs‎. ‎We determine the number of optimally labeled graphs using the adjacency matrix‎. ‎Several techniques to construct maximal graphs that admit an optimal labeling are introduced as well as a family of outerplanar graphs that can be labeled in this form.

Keywords

Main Subjects

References

[1] B. D. Acharya and S. M. Hegde, Arithmetic graphs, J. Graph Theory, 14 (1990) 275–299.
[2] B. D. Acharya and K. A. Germina, Maximal strongly indexable graphs, J. Combin. Math. Combin. Comput., 76 (2011)
75–99.
[3] S. Arumugam and K. Germina, On indexable graphs, Discrete Math., 161 (1996) 285–289.
[4] C. Barrientos, On additive vertex labelings, Indonesian J. Combin., 4(1) (2020) 34–52.
[5] H. Enomoto, A. S. Llado, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math., 34 (1998) 105–109.
[6] R. Figueroa-Centeno, R. Ichishima and F. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231 (2001) 153–168.
[7] Joseph A. Gallian, A dynamic survey of graph labeling, Electronic J. Combin., 23 (2020).
[8] K. A. Germina, More on classes of strongly indexable graphs, Eur. J. Pure Appl. Math., 3 (2010) 269–281.
[9] R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods, 1
(1980) 382–404.
[10] S. M. Hegde, On indexable graphs, J. Combin. Inf. Sci. Sys., 17 (1992) 316–331.
[11] S. M. Hegde and S. Shetty, Strongly k-indexable and super edge magic labelings are equivalent, unpublished.
[12] D. Jungreis and M. Reid, Labeling grids, Ars Combin., 34 (1992) 167–182.
[13] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull., 13 (1970) 451–461.
[14] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966),
Gordon and Breach, New York; Dunod, Paris, (1967) 349–355.
[15] M. Abdel-Azim Seoud, G. M. Abdel-Hamid and M. S. Abo Shady, Indexable and strongly indexable graphs, Proc.
Pakistan Acad. Sci., 49 (2012) 139–144.

Files

History

  • Receive Date: 01 June 2021
  • Revise Date: 05 October 2021
  • Accept Date: 09 October 2021
  • Published Online: 01 June 2022

Share

How to cite

Statistics