The space complexity of sum labelling. (English) Zbl 1533.05233
This very interesting paper discusses the sum graph which is a graph that can be labelled by distinct positive integers so that there is an edge between two vertices if and only if the sum of the two vertices of the edge is a label of another vertex in the graph. Obviously, the graph always has at least one isolated vertex. The minimal number of isolated vertices that are needed is called the sum number. The paper uses a different approach compared with other papers on sum graphs for several families of graphs. The authors obtain an algorithm to label the graph so that it is a sum graph in polynomial time. They also discuss the use of the sum graph concept to store the graph efficiently. In this paper, they also provide the bounds on how big is the graph storage needed. They also study the possibility of storing graphs using sum graphs in databases. They close the paper by giving some open problems.
Reviewer: Kiki Ariyanti Sugeng (Depok)
MSC:
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C75 | Structural characterization of families of graphs |
Software:
OEISOnline Encyclopedia of Integer Sequences:
Ulam numbers: a(1) = 1; a(2) = 2; for n>2, a(n) = least number > a(n-1) which is a unique sum of two distinct earlier terms.References:
| [1] | Angles, R.; Gutierrez, C., Survey of graph database models, ACM Computing Surveys (CSUR), 40, 1, 1-39 (2008) · doi:10.1145/1322432.1322433 |
| [2] | Angles, R.: A comparison of current graph database models. In: 2012 IEEE 28th International Conference on Data Engineering Workshops, pp. 171-177. IEEE (2012) |
| [3] | Bonichon, N.; Gavoille, C.; Hanusse, N.; Poulalhon, D.; Schaeffer, G., Planar graphs, via well-orderly maps and trees, Graphs and Combinatorics, 22, 2, 185-202 (2006) · Zbl 1099.05024 · doi:10.1007/s00373-006-0647-2 |
| [4] | Bonamy, M., Gavoille, C., Pilipczuk, M.: Shorter labeling schemes for planar graphs. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 446-462. SIAM (2020) · Zbl 07304050 |
| [5] | Bergstrand, D.; Hodges, K.; Jennings, G.; Kuklinski, L.; Wiener, J.; Harary, F., Product graphs are sum graphs, Mathematics Magazine, 65, 4, 262-264 (1992) · Zbl 0785.05075 · doi:10.1080/0025570X.1992.11996034 |
| [6] | Dujmovic, V., Esperet, L., Gavoille, C., Joret, G., Micek, P., Morin, P.: Adjacency labelling for planar graphs (and beyond). In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 577-588. IEEE (2020) · Zbl 1499.05165 |
| [7] | Dominguez-Sal, D., Urbón-Bayes, P., Giménez-Vanó, A., Gómez-Villamor, S., Martínez-Bazan, N., Larriba-Pey, J.-L.: Survey of graph database performance on the HPC scalable graph analysis benchmark. In: International Conference on Web-Age Information Management, pp. 37-48. Springer. http://graphanalysis.org/index.html (2010) |
| [8] | Dutka, J., The early history of the factorial function, Archive for History of Exact Sciences, 43, 3, 225-249 (1991) · Zbl 0766.01009 · doi:10.1007/BF00389433 |
| [9] | Elias, P., Universal codeword sets and representations of the integers, IEEE Transactions on Information Theory, 21, 2, 194-203 (1975) · Zbl 0298.94011 · doi:10.1109/TIT.1975.1055349 |
| [10] | Ellingham, MN, Sum graphs from trees, Ars Combinatoria, 35, 335-349 (1993) · Zbl 0779.05042 |
| [11] | Fernau, H., Gajjar, K.: The space complexity of sum labelling. In: Bampis, E., Pagourtzis, A. (eds.) Fundamentals of Computation Theory - 23rd International Symposium, FCT, vol. 12867 of LNCS, pp. 230-244. Springer. https://link.springer.com/chapter/10.1007/978-3-030-86593-1_16/ (2021) · Zbl 07530236 |
| [12] | Fernau, H.; Ryan, JF; Sugeng, KA, A sum labelling for the generalised friendship graph, Discrete Mathematics, 308, 734-740 (2008) · Zbl 1131.05079 · doi:10.1016/j.disc.2007.07.059 |
| [13] | Gallian, J. A.: A dynamic survey of graph labeling, version 23. The Electronic Journal of Combinatorics, DS, 6. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6/pdf (2020) · Zbl 0953.05067 |
| [14] | Ga̧sieniec, L., Klasing, R., Radzik, T.: Combinatorial Algorithms: 31st International Workshop, IWOCA, Proceedings, vol. 12126 of LNCS. Springer (2020) · Zbl 1496.68019 |
| [15] | Gavoille, C., Labourel, A.: Shorter implicit representation for planar graphs and bounded treewidth graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) Algorithms - ESA 2007, 15th Annual European Symposium, vol. 4698 of LNCS, pp. 582-593. Springer (2007) · Zbl 1151.68565 |
| [16] | Gould, R.J., Rödl, V.: Bounds on the number of isolated vertices in sum graphs. In: Alavi, Y., Chartrand, G., Ollermann, O.R., Schwenk, A.J. (eds.) Graph Theory, Combinatorics, and Applications, 1988. Two Volume Set, pp. 553-562. Wiley (1991) · Zbl 0840.05042 |
| [17] | Harary, F., Sum graphs and difference graphs, Congressus Numerantium, 72, 101-108 (1990) · Zbl 0691.05038 |
| [18] | Harary, F., Sum graphs over all the integers, Discrete Mathematics, 124, 1-3, 99-105 (1994) · Zbl 0797.05069 · doi:10.1016/0012-365X(92)00054-U |
| [19] | Hartsfield, N.; Smyth, WF, A family of sparse graphs of large sum number, Discrete Mathematics, 141, 1-3, 163-171 (1995) · Zbl 0827.05048 · doi:10.1016/0012-365X(93)E0196-B |
| [20] | Jouili, S., Vansteenberghe, V.: An empirical comparison of graph databases. In: 2013 International Conference on Social Computing, pp. 708-715. IEEE (2013) |
| [21] | Kumar Kaliyar, R.: Graph databases: A survey. In: International Conference on Computing, Communication & Automation, pp. 785-790. IEEE (2015) |
| [22] | Konečnỳ, M.; Kučera, S.; Novotnà, J.; Pekáirek, J.; Šimsa, Š.; Töpfer, M., Minimal sum labeling of graphs, Journal of Discrete Algorithms, 52-53, 29-37 (2018) · Zbl 1403.05127 · doi:10.1016/j.jda.2018.11.003 |
| [23] | Kratochvíl, J., Miller, M., Nguyen, H.M.: Sum graph labels – an upper bound and related problems. In: 12th Australasian Workshop on Combinatorial Algorithms, AWOCA, pp. 126-131. Institut Teknologi Bandung, Indonesia (2001) |
| [24] | Kannan, S.; Naor, M.; Rudich, S., Implicit representation of graphs, SIAM Journal on Discrete Mathematics, 5, 4, 596-603 (1992) · Zbl 0768.05082 · doi:10.1137/0405049 |
| [25] | Korman, A., Peleg, D., Rodeh, Y.: Constructing labeling schemes through universal matrices. In: Asano, T. (ed.) Algorithms and Computation, 17th International Symposium, ISAAC, vol. 4288 of LNCS, pp. 409-418. Springer (2006) · Zbl 1135.68521 |
| [26] | Keeler, K.; Westbrook, JR, Short encodings of planar graphs and maps, Discrete Applied Mathematics, 58, 3, 239-252 (1995) · Zbl 0833.05025 · doi:10.1016/0166-218X(93)E0150-W |
| [27] | Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Physical Review E, 78, 4, 046110 (2008) · doi:10.1103/PhysRevE.78.046110 |
| [28] | Lick, DR; White, AT, \(k\)-degenerate graphs, Canadian Journal of Mathematics, 22, 5, 1082-1096 (1970) · Zbl 0202.23502 · doi:10.4153/CJM-1970-125-1 |
| [29] | Miller, M., Patel, D., Ryan, J., Sugeng, K.A., Slamin, Tuga, M, Journal of Combinatorial Mathematics and Combinatorial Computing, 55, 137-148 (2005) · Zbl 1103.05076 |
| [30] | Munro, JI; Raman, V., Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing, 31, 3, 762-776 (2001) · Zbl 1017.68037 · doi:10.1137/S0097539799364092 |
| [31] | Miller, M.; Ryan, JF; Ryjácek, Z., Characterisation of graphs with exclusive sum labelling, Electronic Notes on Discrete Mathematics, 60, 83-90 (2017) · Zbl 1377.05175 · doi:10.1016/j.endm.2017.06.012 |
| [32] | Miller, M.; Ryan, J.; Smith, WF, The sum number of the cocktail party graph, Bulletin of the Institute of Combinatorics and its Applications, 22, 79-90 (1998) · Zbl 0894.05048 |
| [33] | Nagamochi, H.; Miller, M., Slamin: On the number of isolates in graph labeling, Discrete Mathematics, 243, 175-185 (2001) · Zbl 0987.05084 · doi:10.1016/S0012-365X(00)00390-3 |
| [34] | Peleg, D., Proximity-preserving labeling schemes, Journal of Graph Theory, 33, 3, 167-176 (2000) · Zbl 0945.05052 · doi:10.1002/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5 |
| [35] | Pyatkin, AV, New formula for the sum number for the complete bipartite graphs, Discrete Mathematics, 239, 1-3, 155-160 (2001) · Zbl 0993.05130 · doi:10.1016/S0012-365X(01)00188-1 |
| [36] | Ryan, J., Exclusive sum labeling of graphs: A survey, AKCE International Journal of Graphs and Combinatorics, 6, 1, 113-136 (2009) · Zbl 1210.05152 |
| [37] | Schnyder, W., Planar graphs and poset dimension, Order, 5, 323-343 (1989) · Zbl 0675.06001 · doi:10.1007/BF00353652 |
| [38] | Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.) Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 138-148. SIAM (1990) · Zbl 0786.05029 |
| [39] | Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. OEIS Foundation Inc. (2021). https://oeis.org/A002858 (1973) · Zbl 1044.11108 |
| [40] | Sutton, M.; Miller, M., Mod sum graph labelling of \(H_{m, n}\) and \(K_n\), Australasian Journal of Combinatorics, 20, 233-240 (1999) · Zbl 0933.05140 |
| [41] | Sutton, M.; Miller, M., On the sum number of wheels, Discrete Mathematics, 232, 185-188 (2001) · Zbl 0982.05090 · doi:10.1016/S0012-365X(00)00347-2 |
| [42] | Sutton, M.; Miller, M.; Ryan, J., Slamin: Connected graphs which are not mod sum graphs, Discrete Mathematics, 195, 1, 287-293 (1999) · Zbl 0931.05074 · doi:10.1016/S0012-365X(98)00184-8 |
| [43] | Smyth, WF, Sum graphs of small sum number, Colloquia Mathematica Societatis Jãnos Bolyai, 60, 669-678 (1991) · Zbl 0792.05120 |
| [44] | Slamet, S.; Sugeng, KA; Miller, M., Sum graph based access structure in a secret sharing scheme, Journal of Prime Research in Mathematics, 2, 113-119 (2006) · Zbl 1131.94021 |
| [45] | Singla, S.; Tiwari, A.; Tripathi, A., Some results on the spum and the integral spum of graphs, Discrete Mathematics, 344, 5, 112311 (2021) · Zbl 1460.05166 · doi:10.1016/j.disc.2021.112311 |
| [46] | Sutton, M.: Summable Graph Labellings and Their Applications. PhD thesis, Department of Computer Science, University of Newcastle, Australia (2000) |
| [47] | Tuga, M., Miller, M.: Delta-optimum exclusive sum labeling of certain graphs with radius one. In: Akiyama, J., Baskoro, E.T., Kano, M. (eds.) Combinatorial Geometry and Graph Theory, Indonesia-Japan Joint Conference, IJCCGGT, vol. 3330 of LNCS, pp. 216-225. Springer (2003) · Zbl 1117.05097 |
| [48] | Wang, Y.; Liu, B., The sum number and integral sum number of complete bipartite graphs, Discrete Mathematics, 239, 1-3, 69-82 (2001) · Zbl 0993.05131 · doi:10.1016/S0012-365X(01)00195-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
