MAGIC GRAPHS

Author(s): 
ALISON M. MARR, W.D. WALLIS
Publisher: 
SPRINGER SCIENCE + BUSINESS MEDIA.BIRKHÄUSER. NEW YORK.2013. Second Edition, XVI, 186 p. 34 Illus., Hardcover.
Year: 
2013
ISBN: 
978-0-8176-8390-0; 978-0-8176-8391-7 (eBook); DOI 10.1007/978-0-8176-8391-7.
Price (tentative): 
From 41.84$ (eBook) to 51.95$ (Hardcover).
Short description: 

The book begins with a survey of the main topics. Magic properties are introduced by a discussion of magic squares, also the related Latin squares and on Latin rectangles, and the basics of graph theory.

This concise, self-contained text-book is the only book of its kind in the area of magic graphs/labeling, it contains numerous exercises, and their solutions, and includes updates on new research in the field. A labeling is a mapping whose domain is some set of graph elements—the set of vertices, for example, or the set of all vertices and edges—and whose range was a set of positive integers. Various restrictions can be placed on the mapping.

Recently there has been a resurgence of interest to magic labeling due to a number of results that have applications to the problem of decomposing graphs into trees.

In this second edition includes: a new chapter on magic labeling of directed graphs, applications of theorems from graph theory and interesting counting arguments, this is why a new edition seemed appropriate, a good collection of new research problems and exercises covering a range of difficulties, and a fully updated bibliography and index. The book is a beautiful collection of recent results on the topic of magic labeling.

Some knowledge of groups and fields is assumed in the preliminary chapter, in the discussion of magic squares and Latin squares, and the basics of graph theory. Subsequent chapters explore the three main types of magic labeling—edge-magic, vertex-magic, and totally magic—in turn. Finally, magic labeling of directed graphs are discussed.

This book is a good guide for graduate students beginning research in graph labeling. They can see how new mathematics comes into existence. It may serve as a graduate or advanced undergraduate text for courses in mathematics or computer science, and as reference for the researcher.

URL for publisher, author, or book: 
www.birkhauser-science.com
MSC main category: 
05 Combinatorics
MSC category: 
05C78, 68R10, 05C30.
Other MSC categories: 
05B15, 68RXX, 90B15, 90B18, 90C35.
Review: 

The book begins with a survey of the main topics. Magic properties are introduced by a discussion of magic squares, also the related Latin squares and on Latin rectangles, and the basics of graph theory.

The book Magic Graphs, is self-contained, good, admirably clear, and a stimulating and very well written. This concise text-book is the only book of its kind in the area of magic graphs/labeling, it contains numerous exercises, and their solutions, and includes updates on new research in the field.

A labeling is a mapping whose domain is some set of graph elements—the set of vertices, for example, or the set of all vertices and edges—and whose range was a set of positive integers. Various restrictions can be placed on the mapping.

The introductory chapter covers briefly the basics of graph theory and introduces various kinds of magic labeling of graphs. The main three chapters that follow are devoted to the three main types of magic labeling: edge magic, vertex-magic, and totally magic labeling, respectively. Each main topic is treated in depth. Not many mathematical prerequisites are needed to read this book although the reader should have some mathematical maturity. The mathematical material is sufficiently closed.

The aim of the present book is to describe the main concepts of magic graphs and labeling, together with full proofs that would be both accessible to beginners and useful for graduate and advanced undergraduate in mathematics or computer science, or recreational mathematical, and as reference for the researcher. The chapter five, added to the second edition, is devoted to rapidly developing areas of magic graphs, as newly magic type labeling of digraphs.

It goes from the basics to the frontiers of research in magic labeling of digraphs, with newly ideas emergent, in mathematics or computer science. For the reader is suitable solving some of the many exercises and research problems. ¡Good experience for share seriously the problems!

I feel sure that it will be of great use both to students of graph theory, magic graphs, Latin squares and Latin rectangles, design of experiments, graceful graphs, and mathematics, in general, and captivate to students, instructors, puzzle devotees, and to those intervening in recreational mathematics.

The book contains preface, table of contents, list de figures (pp. i-xvi), and five chapters, comments on the research problems, references, answers to selected exercises, and an index, in 186 pp.

The first chapter, preliminaries, (pp. 1-14), introduces the basic, definitions and notions, devoted to present the main topics in the subject. The book begins with a survey of main items. Magic properties with a discussion of magic squares, related Latin squares and on Latin rectangles are presented. The basics of graph theory are covered. A labeling (or valuation) of a graph is a map that carries graph elements to numbers. The most common choices of domain are the set of all vertices and edges (named total-labeling), the vertex-set alone (vertex-labeling), or the edge-set alone (edge-labeling).

Then define graph labeling, in general and magic labeling, in particular. In many cases, it is interesting to consider the sum of all labels associated with a graph label. It is conceivable that the same labeling could be both vertex-magic and edge-magic for a given graph, in this case the labeling, and the graph are called totally magic. There are also a number of interesting types of magic labeling of digraphs. The chapter also includes some applications of magic labeling to efficient addressing systems and to ruler models.

This preliminary chapter considered three theorems, and one lemma, and one corollary. Also ten exercises, very quite easy. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions.

In the chapter two, (pp. 15-70), on define an edge-magic total labeling on a graph G as a one-to-one map λ form V(G) U E(G) onto the integers 1,2, …, v+e, where v=card(V(G)) and e=card(E(G)), with the property that, given any edge xy, λ(x) + λ(xy) + λ(y) = k, for some constant k, that is, wt(xy) =k for any choice of edge xy. Then k is called the magic sum of G.

Any graph with an edge-magic total labeling will be called edge magic. Examples of edge magic total labeling are given.

The remainder is full dedicated to Edge-Magic Total Labeling: Basic ideas, definitions, some elementary counting, and duality; then Graphs with no edge magic total labeling, main theorem, forest, regular graphs; Cliques and complete graphs, the Sidon sequences and labeling, complete graphs, all edge-magic total labeling of complete graphs, complete and split sub-graphs and graphs; Cycles, small and generalizations; Complete Bipartite Graphs, small cases and stars; Wheels, the constructions for n, distinct of ≡2 (mod.4), and n≡ 2 (mod.4); Trees; Disconnected Graphs, some easy cases, union of complete graphs, union of stars, tri-chromatic graphs; Super edge-magic total labeling; A cycle with a chord, odd and even cycles, and some general constructions; to end edge magic injections.

This chapter considered 37 theorems, and ten lemmas, and seven corollaries. For stimulating to reader and the beginner researcher on proposed 24 exercises, and 21 research problems. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Respect the research problems are given hints for their statement that are solved in the Notes on Research Problems, pages 159 to 162, because the most requires very little work.

In the chapter 3, (pp.71-109), on define a vertex-magic total labeling on a graph G as a one-to-one map λ form V(G) U E(G) onto the integers {1,2, …, v+e}, where v=card(V(G)) and e=card(E(G)), if there is a constant h so that for every vertex x, λ(x) + ∑ λ(xy) = h, where the sum is over all vertices y adjacent to x. So the magic requirement is wt(x) =h for all x. The constant h is called the magic constant for λ. Again, a graph with a vertex-magic total labeling will be called vertex-magic. It is not hard to find examples of vertex-magic total labeling for some graphs.

The chapter is totally devoted to vertex-magic total labeling, and analyze basic ideas, definitions and basic counting; the case of regular graphs, cycles and paths; the interesting case of vertex-magic total labeling of wheels and its generalizations, because the large wheels cannot be labeled, and the small wheels can have many labeling; the vertex-magic total labeling of complete bipartite graphs, construction for Km,n, the spectrum, joins, unions of stars; the vertex-magic total labeling of complete tripartite graphs; graphs with vertices of degree one; complete graphs; disconnected graphs, multiples of regular graphs; super vertex-magic total labeling, and vertex-magic injections.

This chapter considered 30 theorems, and two lemmas, and eight corollaries. Fifteen exercises, and five research problems, are proposed. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Respect the research problems are given hints for their statement.

In this chapter 4, investigate the question: for a graph G does there exist, a total labeling λ, that is, both edge-magic and vertex-magic? λ is called a totally magic labeling and G is a totally graph. The constants h and k are the magic constant and magic sum, respectively. Not require that h=k. Because the totally magic graphs are very rare, is adequate, to study totally magic injections. If a graph posses such a mapping, is called total magic injections (TMI) graph.

The chapter is completely devoted to totally magic labeling (pp. 111-134), and study basic ideas, definitions and examples. Then isolates and stars; forbidden configurations; unions of triangles; small graphs; totally magic injections; totally magic equation matrix, and the survivors on seven vertices.

This chapter considered 18 theorems, and four lemmas, and eleven exercises. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Moreover, eight exercises and five interesting research problems are proposed.

The chapter 5, (pp. 135-157), new in this second edition, respect to the original book of Wallis, in this case, in collaboration with Alison Marr, deals with magic type labeling of digraphs. Early labeling results were all on undirected graphs. However, in mid-1980s, in the literature appeared the graceful labeling on directed graphs, in general, this is very important due to a number of interesting results that have applications and are related to the problems of decomposing graphs into trees.

A magic labeling of a digraph D is a one-to-one map λ from V(D)UE(D) onto the set of integers {1,2,…,v+e}, in which all the sums mA= λ (x) + ∑x→y λ(x,y), and all sums mB= λ (x) + ∑z→x λ(z,y), are constant, independent of the choice of x. A digraph with a magic labeling is a magic digraph.

The chapter is completely devoted to magic type labeling of digraphs, and study magic labeling, with definitions, basic counting, small examples, complete digraphs, double cycles, and magic digraphs with two magic constants; locally magic labeling with digraphs such as no locally magic labeling, cycles, wheels, complete graphs, and complete bipartite digraphs; vertex-magic edge labeling; arc-magic labeling with definitions, paths and cycles, labeling for arc-magic digraphs, and to end, different items on in/out magic total labeling, basic ideas, small digraphs, forbidden configurations, and regular graphs.

This chapter considered 25 theorems, and two lemmas, and ten exercises. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Moreover, six interesting research problems are proposed.

Notes on Research Problems, (pp. 159-162). Different kinds on research problems are mentioned throughout the text. The most required very little work. An brief comment is included in the volume, related to research problems on the three main topics (about edge-magic labeling, 21 stated problems; on vertex magic labeling, 5 posed problems; on totally magic labeling, with five research problems) and the other topic, added in this second edition, on magic type labeling of digraphs, on considered six proposed problems. The last three problems, in this chapter about notes on research problems, all ask for more general results for some classes of digraphs or to find more infinite families of digraph with the given property.

References, (pp. 163-169). They are an extensive bibliography, 99 up-date references.

Answers to Selected exercises, (pp. 171-182). The exercises are designed to aid understanding. Some are quite easy, a few are quite difficult, and the others for works particular graph or labeling. There are worked solutions, to the majority of the exercises.

Index (pp. 183-186)

In this second edition includes: a new chapter on magic labeling of directed graphs, applications of theorems from graph theory and interesting counting arguments, a good collection of new research problems and exercises covering a range of difficulties, and a fully updated bibliography and index. The book is a beautiful collection of recent results on the topic of magic labeling.

Definitely the book is high recommended and is of much interest. This book is a good guide for graduate students beginning research in graph labeling. They can see how new mathematics comes into existence. It may serve as a graduate or advanced undergraduate text for courses in mathematics or computer science, and as reference for the researcher. I feel sure that it will be of great use both to students and researchers.

Reviewer: 
Francisco José Cano Sevilla.
Affiliation: 
Profesor Universidad Complutense

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Copy the characters (respecting upper/lower case) from the image.
satunnaisuus