تعداد نشریات | 43 |
تعداد شمارهها | 1,673 |
تعداد مقالات | 13,654 |
تعداد مشاهده مقاله | 31,570,151 |
تعداد دریافت فایل اصل مقاله | 12,472,309 |
Optimal maximal graphs | ||
Transactions on Combinatorics | ||
دوره 11، شماره 2، شهریور 2022، صفحه 85-97 اصل مقاله (261.82 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2021.128956.1860 | ||
نویسندگان | ||
Christian Barrientos* 1؛ Maged Youssef2 | ||
1Department of Mathematics, Valencia College, Orlando, FL 32832, U. S. A. | ||
2Department of Mathematics & Statistics, College of Sciences, Imam Mohammad Ibn Saud Islamic University, Riyadh 11623, Saudi Arabia | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
Optimal labeling؛ maximal graph؛ additive labeling | ||
مراجع | ||
[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) [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 [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), [15] M. Abdel-Azim Seoud, G. M. Abdel-Hamid and M. S. Abo Shady, Indexable and strongly indexable graphs, Proc. | ||
آمار تعداد مشاهده مقاله: 1,060 تعداد دریافت فایل اصل مقاله: 977 |