Magic Graphs pp 135-157

# Magic Type Labelings of Digraphs

• Alison M. Marr
• W. D. Wallis
Chapter

## Abstract

Early labeling results were all on undirected graphs. However, in the mid-1980s Bloom and Hsu defined graceful labelings on directed graphs [16]. Not much work was done with directed graph labeling until the early 2000s when Marr worked with directed graph labelings in her dissertation [65]. As part of that work, Bloom et al. defined magic labelings on directed graphs [17]. The results in this chapter are from [17] unless otherwise noted.

### References

1. 1.
J. M. Aldous and R. J. Wilson, Graphs and Applications: An Introductory Approach. Springer-Verlag, New York (2000).
2. 2.
W. S. Andrews, Magic Squares and Cubes. Dover (1960).Google Scholar
3. 3.
A. Armstrong and D. McQuillan, Vertex-magic total labelings of even complete graphs. Discrete Math. 311 (2011), 676–683.Google Scholar
4. 4.
S. Arumugam, G. S. Bloom, M. Miller and J. Ryan, Some open problems on graph labelings, AKCE Internat. J. Graphs Combin. 6 (2009), 229–236.Google Scholar
5. 5.
S. Avadayappan, R. Vasuki and P. Jeyanthi, Magic strength of a graph. Indian J. Pure Appl. Math. 31 (2000), 873–883.Google Scholar
6. 6.
M. Bača, On magic labelings of grid graphs. Ars Combin. 33 (1992), 295–299.Google Scholar
7. 7.
M. Bača, Labelings of two classes of plane graphs. Acta Math. Appl. Sinica (English Ser.) 9 (1993), 82–87.Google Scholar
8. 8.
M. Bača and M. Miller, Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions. Brown Walker, Boca Raton (2007).Google Scholar
9. 9.
M. Balakrishnan and G. Marimuthu, E–super vertex magic labelings of graphs. Discrete Appl. Math. 160 (2012), 1766–1774.Google Scholar
10. 10.
D. W. Bange, A. E. Barkauskas, and P. J. Slater, Conservative graphs. J. Graph Theory 4 (1980), 81–91.Google Scholar
11. 11.
C. A. Barone. Magic Labelings of Directed Graphs, Masters Thesis, University of Victoria, 2008, 55 pages.Google Scholar
12. 12.
S. S. Block and S. A. Tavares, Before Sudoku: The World of Magic Squares. Oxford University Press (2009).Google Scholar
13. 13.
G. S. Bloom, Private communication.Google Scholar
14. 14.
G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs. Proc. IEEE 65 (1977) 562–570.Google Scholar
15. 15.
G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications. In Theory and Applications of Graphs, Lecture Notes in Math. 642. Springer-Verlag (1978), 53–65.Google Scholar
16. 16.
G. S. Bloom and D. F. Hsu, On graceful directed graphs. SIAM J. Alg. Disc. Math. 6 (1985), 519–536.Google Scholar
17. 17.
G. S. Bloom, A. Marr, and W. D. Wallis, Magic digraphs. J. Combin. Math. Combin. Comput. 65 (2008), 205–212.Google Scholar
18. 18.
T. Bohman, A construction for sets of integers with distinct subset sums. Electronic J. Combinatorics 5 (1998), #R3.Google Scholar
19. 19.
R. A. Brualdi, Introductory Combinatorics. (3rd ed.) Prentice-Hall (1999).Google Scholar
20. 20.
B. Calhoun, K. Ferland, L. Lister, and J. Polhill, Totally magic labelings of graphs. Austral. J. Combin. 32 (2005), 47–59.Google Scholar
21. 21.
R. Cattell, Vertex-magic total labelings of complete multipartite graphs. J. Combin. Math. Combin. Comput. 55 (2005), 187–197.Google Scholar
22. 22.
D. Craft and E. H. Tesar, On a question by Erdös about edge-magic graphs. Discrete Math. 207 (1999), 271–276.Google Scholar
23. 23.
J. Dénes and A. D. Keedwell, Latin Squares and their Applications. Academic Press (1974).Google Scholar
24. 24.
T. J. Dickson and D. G. Rogers, Problems in graph theory. V. Magic valuations. Southeast Asian Bull. Math. 3 (1979), 40–43.Google Scholar
25. 25.
H. Enomoto, A. S. Llado, T. Nakamigawa and G. Ringel, Super edge-magic graphs. SUT J. Math. 34 (1998), 105–109.Google Scholar
26. 26.
P. Erdös, Problems and results from additive number theory. Colloq. Théorie des Nombres, Bruxelles (1955), 127–137.Google Scholar
27. 27.
P. Erdös and P. Turán, On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. 16 (1941), 212–215; Addendum, 19 (1944), 242.Google Scholar
28. 28.
G. Exoo, A. C. H. Ling, J. P. McSorley, N. C. K. Phillips and W. D. Wallis, Totally magic graphs. Discrete Math. 254 (2), 103–113.Google Scholar
29. 29.
R. M. Figueroa-Centeno, R. Ichishima and F. A. Muntaner-Batle, The place of super edge magic labelings among other classes of labelings. Discrete Math. 231 (2001), 153–168.Google Scholar
30. 30.
Y. Fukuchi, Edge-magic labelings of wheel graphs. Tokyo J. Math. 24 (2001), 153–167.Google Scholar
31. 31.
J. A. Gallian, A dynamic survey of graph labeling. Electronic J. Combinatorics 18 (2011), Dynamic Survey #DS6.Google Scholar
32. 32.
F. Göbel and C. Hoede, Magic labelings of graphs. Ars Combin. 51 (1999), 3–19.Google Scholar
33. 33.
R. D. Godbold and P. J. Slater, All cycles are edge-magic. Bull. Inst. Combin. Appl. 22 (1998), 93–97.Google Scholar
34. 34.
J. Gómez, Solution of the conjecture: If $$n \equiv 0$$ (mod 4), n > 4, then K n has a super vertex-magic total labeling. Discrete Math. 307 (2007), 2525–2534.Google Scholar
35. 35.
J. Gómez, Two new methods to obtain super vertex-magic total labelings of graphs. Discrete Math. 308 (2008), 3361–3372Google Scholar
36. 36.
I. D. Gray, Vertex-magic total labelings of regular graphs, SIAM J. Discrete Math. 21 (2007), 170–177.Google Scholar
37. 37.
I. D. Gray, J. A. MacDougall, Sparse Semi-Magic Squares and Vertex Magic Labelings. Ars Comb. 80 (2006), 225–242.
38. 38.
I. D. Gray, J. A. MacDougall, J. P. McSorley and W D. Wallis, Vertex-magic labeling of trees and forests. Discrete Math. 261 (2), 285–298.Google Scholar
39. 39.
I. D. Gray, J. A. MacDougall, R. J. Simpson and W. D. Wallis, Vertex-magic total labelings of complete bipartite graphs. Ars Combin. 69 (2), 117–128.Google Scholar
40. 40.
I. D. Gray, J. A. MacDougall and W. D. Wallis, On vertex-magic labeling of complete graphs. Bull. Inst. Combin. Appl. 38 (2), 42–44.Google Scholar
41. 41.
R. K. Guy, Unsolved Problems in Number Theory. Second Edition. Springer, New York (1994).
42. 42.
T. R. Hagedorn, Magic rectangles revisited. Discrete Math. 207 (1999), 65–72.Google Scholar
43. 43.
T. Harmuth, Ueber magische Quadrate und ähnliche Zahlenfiguren. Arch. Math. Phys. 66 (1881), 286–313.Google Scholar
44. 44.
T. Harmuth, Ueber magische Rechtecke mit ungeraden Seitenzahlen. Arch. Math. Phys. 66 (1881), 413–447.Google Scholar
45. 45.
N. Hartsfield and G. Ringel, Pearls in Graph Theory. Academic Press (1990).Google Scholar
46. 46.
S. M. Hegde and S. Shetty, On magic graphs. Ars Combin. 27 (2), 277–284.Google Scholar
47. 47.
H. Ivančo and Lučkaničová, On edge-magic disconnected graphs. SUT J. Math. 38 (2), 175–184.Google Scholar
48. 48.
P. Jeyanthi and V. Swaminathan, Super vertex-magic labeling. Indian J. Pure Appl. Math. 34 (2), 935–939.Google Scholar
49. 49.
P. Jeyanthi and V. Swaminathan, On super vertex-magic labling. J. Discrete Math. Sci. Cryptography 8 (2005), 217–224.Google Scholar
50. 50.
S.-R. Kim and J. Y. Park, On super edge-magic graphs. Ars Combin. 81 (2006), 113–127.
51. 51.
A. Kotzig, On a class of graphs without magic valuations.Reports of the CRM CRM–136, 1971.Google Scholar
52. 52.
A. Kotzig, On magic valuations of trichromatic graphs.Reports of the CRM CRM–148, December 1971.Google Scholar
53. 53.
A. Kotzig, On well spread sets of integers.Reports of the CRM CRM–161 (1972).Google Scholar
54. 54.
A. Kotzig and A. Rosa, Magic valuations of finite graphs. Canad. Math. Bull. 13 (1970), 451–461.Google Scholar
55. 55.
A. Kotzig and A. Rosa, Magic valuations of complete graphs. Publ. CRM175 (1972).Google Scholar
56. 56.
S.-M. Lee, E. Seah and S.-K. Tan, On edge-magic graphs. Congressus Num. 86 (1992), 179–191.Google Scholar
57. 57.
K. W. Lih, On magic and consecutive labelings of plane graphs. Utilitas Math. 24 (1983), 165–197.Google Scholar
58. 58.
Y. Lin and M. Miller, Vertex-magic total labelings of complete graphs. Bull. Inst. Combin. Appl. 33 (2001),68–76.Google Scholar
59. 59.
S. C. Lopez, F. A. Muntaner-Batle and M. Rius-Font, Bimagic and other generalizations of super edge-magic labelings. Bull. Austral. Math. Soc. 84 (2011), 137–152.
60. 60.
J. MacDougall, Vertex-magic labeling of regular graph.Lecture, DIMACS Connect Institute (July 18, 2).Google Scholar
61. 61.
J. MacDougall, M. Miller, Slamin and W. D. Wallis, Vertex-magic total labelings. Utilitas Math. 61 (2), 3–21.Google Scholar
62. 62.
J. A. MacDougall, M. Miller and K. Sugeng, Super vertex-magic lotal labelings of graphs. Proc. 15th AWOCA (2004), 222–229.Google Scholar
63. 63.
J. MacDougall, M. Miller and W. D. Wallis, Vertex-magic total labelings of wheels and related graphs. Utilitas Math. 62 (2), 175–183.Google Scholar
64. 64.
J. MacDougall and W. D. Wallis, Strong edge-magic labeling of a cycle with a chord. Austral. J. Combin. 28 (2), 245–255.Google Scholar
65. 65.
A. Marr, Labelings of directed graphs, Ph.D. Thesis, Southern Illinois University at Carbondale, 2007, 63 pages.Google Scholar
66. 66.
A. Marr, Magic vertex labelings of digraphs. Int. J. Math. Comput. Sci. 4 (2009), no. 2, 91–96.
67. 67.
A. Marr and S. Stern, Magic labelings of directed graphs, preprint.Google Scholar
68. 68.
B. D. McKay, nauty User’s Guide (version 1.5). Technical Report TR-CS-87-03. Department of Computer Science, Australian National University (1990).Google Scholar
69. 69.
D. McQuillan, Edge-magic and vertex-magic total labelings of certain cycles. Ars Combin. 91(2009), 257–266.Google Scholar
70. 70.
D. McQuillan and J. M. McQuillan, Magic labelings of triangles. Discrete Math. 309(2009), 2755–2762.Google Scholar
71. 71.
D. McQuillan and K. Smith, Vertex-magic labeling of odd complete graphs. Discrete Math. 305(2005), 240–249.Google Scholar
72. 72.
J. P. McSorley, Totally magic injections of graphs. J. Combin. Math. Combin. Comput. 56 (2006), 65–81.Google Scholar
73. 73.
J. P. McSorley and J. A. Trono, On k-minimum and m-minimum edge-magic injections of graphs. Discrete Math. 310 (2001), 56–69.Google Scholar
74. 74.
J. P. McSorley and W. D. Wallis, On the spectra of totally magic labelings. Bull. Inst. Combin. Appl. 37 (2), 58–62.Google Scholar
75. 75.
J.  Milhalisin, Vertex magic unions of stars. Congressus Num. 177 (2005), 101–107.Google Scholar
76. 76.
M. Miller, J. A. MacDougall, Slamin and W. D. Wallis, Problems in total graph labelings, Proc. Australasian Workshop on Combinatorial Algorithms, Perth (1999).Google Scholar
77. 77.
J. Moran, The Wonders of Magic Squares. Vintage Books, Random House (1982).Google Scholar
78. 78.
F. A. Muntaner-Batle, Special super edge magic labelings of bipartite graphs. J. Combin. Math. Combin. Comput. 39 (2001), 107–120.Google Scholar
79. 79.
J. Y. Park, J. H. Choi and J. H. Bae, On super edge-magic labeling of some graphs. Bull. Korean Math. Soc. 45 (2008), 11–21.Google Scholar
80. 80.
N. C. K. Phillips, R. S. Rees and W. D. Wallis, Edge-magic total labelings of wheels. Bull. Inst. Combin. Appl. 31 (2001), 21–30.Google Scholar
81. 81.
N. C. K. Phillips and W. D. Wallis, Well-spread sequences. J. Combin. Math. Combin. Comput. 31 (1999), 91–96.Google Scholar
82. 82.
G. Ringel and A. S. Llado, Another tree conjecture. Bull. Inst. Combin. Appl. 18 (1996), 83–85.Google Scholar
83. 83.
J. Sedláček, Problem 27. Theory of graphs and its applications. (Smolenice, 1963), 163–164 Publ. House Czechoslovak Acad. Sci., Prague (1964).Google Scholar
84. 84.
S. Sidon, Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen. Math. Ann. 106 (1932), 536–539.Google Scholar
85. 85.
Slamin, M. Bača, Y. Lin, M. Miller and R. Simanjuntak, Edge-magic total labelings of wheels, fans and friendship graphs. Bull. Inst. Combin. Appl. 35 (2), 89–98.Google Scholar
86. 86.
B. M. Stewart, Magic graphs. Canad. J. Math. 18 (1966), 1031–1059.Google Scholar
87. 87.
A. P. Street and W. D. Wallis, Combinatorial Theory: An Introduction. Charles Babbage Research Centre (1977).Google Scholar
88. 88.
K. A. Sugeng and M. Miller, On consecutive edge magic total labeling of graph. J. Discrete Algorithms 6 (2008), 59–65.Google Scholar
89. 89.
University of Sydney, Mathematics Enrichment Groups, Exercises for March 26, 1999.Google Scholar
90. 90.
L. Valdés, Edge-magic K p. Paper delivered at Thirty-Second South-Eastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, 2001).Google Scholar
91. 91.
V. G. Vizing, On an estimate of the chromatic class of a p-graph [Russian]. Discret. Anal. 3 (1964), 25–30.Google Scholar
92. 92.
W. D. Wallis, Combinatorial Designs. Marcel Dekker, New York (1988).
93. 93.
W. D. Wallis A Beginner’s Guide to Graph Theory. Birkhauser, Boston (2000).Google Scholar
94. 94.
W. D. Wallis, Two results of Kotzig on magic labelings. Bull. Inst. Combin. Appl. 36 (2), 23–28.Google Scholar
95. 95.
W. D. Wallis, Vertex magic labelings of multiple graphs. Congressus Num. 152 (2001), 81–83.Google Scholar
96. 96.
W. D. Wallis, E. T. Baskoro, M. Miller and Slamin, Edge-magic total labelings. Austral. J. Combin. 22 (2000), 177–190.Google Scholar
97. 97.
W. D. Wallis and R. A. Yates, On Totally Magic Injections. Austral. J. Combin. 32 (2005), 339–348.Google Scholar
98. 98.
D. B. West, An Introduction to Graph Theory. Prentice-Hall (1996).Google Scholar
99. 99.
K. Wijaya and E. T. Baskoro, Edge-magic total labeling on disconnected graphs, Proc. Eleventh Australasian Workshop on Combinatorial Algorithms, University of Newcastle (2000), 139–144.Google Scholar
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9500752687454224, "perplexity": 22323.099555431625}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-09/segments/1518891813622.87/warc/CC-MAIN-20180221123439-20180221143439-00670.warc.gz"}