×

It is all labeling. (English) Zbl 1358.05251

Gera, Ralucca (ed.) et al., Graph theory. Favorite conjectures and open problems – 1. Cham: Springer (ISBN 978-3-319-31938-4/hbk; 978-3-319-31940-7/ebook). Problem Books in Mathematics, 231-252 (2016).
The author presents and discusses several problems that are related to graph labeling. A historical context and the current state of knoweldge in the field are presented in the paper. Many of the considered problems are related to former works of the author, they are quite natural and easy to state, yet several of them are open for a long time. The list of the problems also includes some well-known problems such as the graceful tree conjecture of Ringle, Kotzig, and Rosa, which states that all trees are graceful. Other problems in the paper are about so-called \(k\)-graceful, \(k\)-sequential, and edge-magic graphs. Near the end of the paper, the author also discusses a connection between the theory of domination for graphs and between labeling problems.
For the entire collection see [Zbl 1357.05001].

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstee, R., Ferguson, R., Griggs, J.: Permutations with low discrepancy consecutive k-sums. J. Comb. Theory A 100, 302–321 (2002) · Zbl 1013.05003 · doi:10.1006/jcta.2002.3304
[2] Arumugam, S., Froncek, D., Kamitchi, N.: Distance magic graphs–a survey. International Workshop on Graph Labelings 2010, October 22–23, 2010, University of Wisconsin - Superior
[3] Bange, D.W., Barkauskas, A.E., Slater, P.J.: Simply sequential and graceful graphs. Cong. Num. 23, 155–162 (1979) · Zbl 0427.05056
[4] Bange, D.W., Barkauskas, A.E., Slater, P.J.: Sequentially additive graphs. Discrete Math. 44, 235–241 (1983) · Zbl 0508.05057 · doi:10.1016/0012-365X(83)90187-5
[5] Beena, S.: On and ’ labeled graphs. Discrete Math. 309, 1783–1787 (2009) · Zbl 1188.05108 · doi:10.1016/j.disc.2008.02.038
[6] Bascunan, M.E., Ruiz, S., Slater, P.J.: The additive bandwidth of grids and complete bipartite graphs. Cong. Num. 88, 245–254 (1992) · Zbl 0790.05072
[7] Bascunan, M.E., Brigham, R.C., Caron, R.M., Ruiz, S., Slater, P.J., Vitray, R.P.: On the additive bandwidth of graphs. J. Comb. Math. Comb. Comput. 18, 129–144 (1995) · Zbl 0833.05066
[8] Bermond, J.C., Brouwer, A.E., Germa, A.: Systemes de triples et differences associees. In: Colloque CNRS, Problemes Combinatoires et Theorie des Graphes, Orsay, 1976, CNRS, pp. 35–38 (1978) · Zbl 0412.05012
[9] Bermond, J.C., Kotzig, A., Turgeon, J.: On a combinatorial problem of antennas in radio-astronomy. In: Colloq. Math. Soc. Janos Bolyai 18, Combinatorics, Keszthely, Hungary, 1976, pp. 135–149. North Holland, Amsterdam (1978)
[10] Biraud, F., Blum, E.J., Ribes, J.C.: On optimum synthetic linear arrays. IEEE Trans. Antennas Propag. AP22, 108–109 (1974) · doi:10.1109/TAP.1974.1140732
[11] Biraud, F., Blum, E.J., Ribes, J.C.: Some new possibilities of optimum synthetic linear arrays for radio-astronomy. Astron. Astrophys. 41, 409–413 (1975)
[12] Bloom, G.S.: A chronology of the Ringel-Kotzig conjecture and the continuing quest to call all trees graceful. In: Harary, F. (ed.) Topics in Graph Theory (Scientist in Residence Program, New York), pp. 32–51. Academy of Science, Washington (1977)
[13] Browkin, J.: Solution of a certain problem of A. Schinzel. Prace Mat. 3, 205–207 (1959) · Zbl 0095.26401
[14] Farber, M.: Domination, independent domination and duality in strongly chordal graphs. Discret. Appl. Math. 7, 115–130 (1984) · Zbl 0531.05045 · doi:10.1016/0166-218X(84)90061-1
[15] Frucht, R.: Graceful numberings of wheels and related graphs. In: Gerwitz, A., Quintas, L. (eds.) Second International Conference on Combinatorial Mathematics, pp. 219–229. The New York Academy of Sciences, New York (1979) · Zbl 0485.05059
[16] Gallian, J.: A dynamic survey of graph labeling. Electron. J. Comb. (2015), #DS6 · Zbl 0953.05067
[17] Gibbs, R.A., Slater, P.J.: Distinct distance sets in graphs. Discret. Math. 93, 155–165 (1991) · Zbl 0755.05085 · doi:10.1016/0012-365X(91)90251-V
[18] Godbold, R., Slater, P.J.: All cycles are edge-magic. Bull. Inst. Combin. Appl. 22, 93–97 (1998) · Zbl 0892.05042
[19] Golomb, S.W.: How to number a graph. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 23–37. Academic Press, New York (1972) · Zbl 0293.05150 · doi:10.1016/B978-1-4832-3187-7.50008-8
[20] Grace, T.: New proof techniques for gracefully labeling graphs. Congr. Numer. 39, 433–439 (1983)
[21] Hoede, C., Kuiper, H.: All wheels are graceful. Utilitas Math. 14, 311, (1978) · Zbl 0397.05048
[22] Kotzig, A., Rosa, A.: Magic valuations of finite graphs. Can. Math. Bull. 13, 451–461 (1970) · Zbl 0213.26203 · doi:10.4153/CMB-1970-084-1
[23] Maheo, M., Thuillier, H.: On d-graceful graphs. Ars Combin. 13, 181–192 (1982) · Zbl 0507.05057
[24] Miller, M., Rodger, C., Simanjutak, R.: Distance magic labelings of graphs. Australas. J. Math. 28, 305–315 (2003) · Zbl 1031.05117
[25] O’Neal, F.A.: Neighborhood sum parameters on graphs. Ph. D. Dissertation, The University of Alabama in Huntsville (2011)
[26] O’Neal, F.A., Slater, P.J.: The minimax, maximin and spread values for open neighborhood sums for 2-regular graphs. Cong. Num. 208, 19–32 (2011) · Zbl 1247.05211
[27] O’Neal, F. A., Slater, P.J.: An introduction to distance D magic graphs. J. Indones. Math. Soc., Special edition, 91–107 (2011) · Zbl 1288.05227
[28] O’Neal, F.A., Slater, P.J.: An introduction to closed/open neighborhood sums: minimax, maximin and spread. Math. Comput. Sci. 5, 69–80 (2011) · Zbl 1254.05176 · doi:10.1007/s11786-011-0075-4
[29] O’Neal, F.A., Slater, P.J.: Uniqueness of vertex magic constants. SIAM J. Discret. Math. 27, 708–716 (2013) · Zbl 1272.05174 · doi:10.1137/110834421
[30] Ringel, G.: Problem 25. In: Theory of Graphs and Its Applications, Proceeding of the Symposium Smolenice 1963, Prague, p. 162 (1964)
[31] Ringel, G., Llado, A.S.: Another tree conjecture. Bull. Inst. Combin. Appl. 18, 83–85 (1996) · Zbl 0869.05057
[32] Rosa, A.: On certain valuations of the vertices of a graph. In: Rosentiehl, P. (ed.) Theory of Graphs, Proceeding of an International Symposium, Rome, 1966, pp. 349–355. Dunod, Paris (1968)
[33] Schneider, A., Slater, P.J.: Minimax neighborhood sums. Cong. Num. 188, 183–190 (2007) · Zbl 1141.05072
[34] Schneider, A., Slater, P.J.: Minimax open and closed neighborhood sums. AKCE Int. J. Graphs Comb. 6, 183–190 (2009) · Zbl 1210.05153
[35] Sierpinski, W.: Elementary theory of numbers. Warsaw, 411–412 (1964)
[36] Simanjutak, R.: Distance magic labelings and antimagic coverings of graphs, International Workshop on Graph Labelings 2010, October 22–23, 2010, University of Wisconsin - Superior
[37] Slater, P.J.: On k-sequential and other numbered graphs. Discret. Math. 34, 185–193 (1981) · Zbl 0461.05053 · doi:10.1016/0012-365X(81)90066-2
[38] Slater, P.J.: On k-graceful graphs. Cong. Num. 36, 53–57 (1982) · Zbl 0519.05057
[39] Slater, P.J.: On repeated difference sequences of a permutation of N. J. Number Theory 16, 1–5 (1983) · Zbl 0509.05015 · doi:10.1016/0022-314X(83)90026-4
[40] Slater, P.J.: On k-graceful, locally finite graphs. J. Comb. Theory B 35, 319–322 (1983) · Zbl 0534.05057 · doi:10.1016/0095-8956(83)90058-8
[41] Slater, P.J.: Graceful and sequential numberings of infinite graphs. S.E. Asian Bull. Math. 9, 15–22 (1985) · Zbl 0589.05057
[42] Slater, P.J.: On k-graceful countably infinite graphs. Discret. Math. 61, 293–303 (1986) · Zbl 0597.05052 · doi:10.1016/0012-365X(86)90100-7
[43] Slater, P.J.: LP-duality, complementarity and generality of graphical subset problems. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.) Domination in Graphs Advanced Topics, pp. 1–30. Marcel Dekker, New York (1998) · Zbl 0891.05046
[44] Slater, P. J.: How provably graceful are the trees? J. Indones. Math. Soc. 2011, Special edition, 133–135 · Zbl 1288.05233
[45] Slater, P.J., Velez, W.Y.: Permutations of the positive integers with restrictions on the sequence of differences. Pac. J. Math. 71, 193–196 (1977) · Zbl 0333.05002 · doi:10.2140/pjm.1977.71.193
[46] Slater, P.J., Velez, W.Y.: Permutations of the positive integers with restrictions on the sequence of differences II. Pac. J. Math. 82, 527–531 (1979) · Zbl 0386.10009 · doi:10.2140/pjm.1979.82.527
[47] Sugeng, K.A., Froncek, D., Miller, M., Ryan, J., Walker, J.: On distance magic labelings of graphs. J. Comb. Math. Comb. Comp. 7, 39–48 (2009) · Zbl 1197.05133
[48] Vilfred, V.: Sigma labeled graphs and circulant graphs. Ph. D. Dissertation, University of Kerala, India (1994)
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.