A **magic graph** is a graph whose edges are labelled by the first *q* positive integers, where *q* is the number of edges, so that the sum over the edges incident with any vertex is the same, independent of the choice of vertex; or it is a graph that has such a labelling. The name "magic" sometimes means that the integers are any positive integers; then the graph and the labelling using the first *q* positive integers are called **supermagic**.

A graph is **vertex-magic** if its vertices can be labelled so that the sum on any edge is the same. It is **total magic** if its edges and vertices can be labelled so that the vertex label plus the sum of labels on edges incident with that vertex is a constant.

There are a great many variations on the concept of magic labelling of a graph. There is much variation in terminology as well. The definitions here are perhaps the most common.

Comprehensive references for magic labellings and magic graphs are Gallian (1998), Wallis (2001), and Marr and Wallis (2013).

A **semimagic square** is an *n* × *n* square with the numbers 1 to *n*^{2} in its cells, in which the sum of each row and column is the same. A semimagic square is equivalent to a magic labelling of the complete bipartite graph *K _{n,n}*. The two vertex sets of

The definition of semimagic squares differs from the definition of magic squares in the treatment of the diagonals of the square. Magic squares are required to have diagonals with the same sum as the row and column sums, but for semimagic squares this is not required. Thus, every magic square is semimagic, but not vice versa.

In combinatorial mathematics, **Ramsey's theorem**, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling of a sufficiently large complete graph. To demonstrate the theorem for two colours, let *r* and *s* be any two positive integers. Ramsey's theorem states that there exists a least positive integer *R*(*r*, *s*) for which every blue-red edge colouring of the complete graph on *R*(*r*, *s*) vertices contains a blue clique on *r* vertices or a red clique on *s* vertices.

In graph theory and computer science, an **adjacency matrix** is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

In graph theory, an **isomorphism of graphs***G* and *H* is a bijection between the vertex sets of *G* and *H*

In mathematics, an **incidence matrix** is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is *X* and the second is *Y*, the matrix has one row for each element of *X* and one column for each element of *Y*. The entry in row *x* and column *y* is 1 if *x* and *y* are related and 0 if they are not. There are variations; see below.

In a computer science, a **graph** is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within a math.

An **antimagic square** of order *n* is an arrangement of the numbers 1 to *n*^{2} in a square, such that the sums of the *n* rows, the *n* columns and the two diagonals form a sequence of 2*n* + 2 consecutive integers. The smallest antimagic squares have order 4. Antimagic squares contrast with magic squares, where each row, column, and diagonal sum must have the same value.

In the mathematical field of graph theory, **Kirchhoff's theorem** or **Kirchhoff's matrix tree theorem** named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of the Laplacian matrix of the graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

In the mathematical field of graph theory, the **Laplacian matrix**, also called the **graph Laplacian**, **admittance matrix**, **Kirchhoff matrix** or **discrete Laplacian**, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.

In the mathematical discipline of graph theory, a **graph labelling** is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.

In the area of graph theory in mathematics, a **signed graph** is a graph in which each edge has a positive or negative sign.

In graph theory, a **rook's graph** is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs or as the line graphs of complete bipartite graphs.

In mathematics, a **conference matrix** is a square matrix *C* with 0 on the diagonal and +1 and −1 off the diagonal, such that *C*^{T}*C* is a multiple of the identity matrix *I*. Thus, if the matrix has order *n*, *C*^{T}*C* = (*n*−1)*I*. Some authors use a more general definition, which requires there to be a single 0 in each row and column but not necessarily on the diagonal.

**Polyhedral combinatorics** is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In mathematics, an **associahedron***K*_{n} is an (*n* − 2)-dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of *n* letters and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with *n* + 1 sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal. Associahedra are also called **Stasheff polytopes** after the work of Jim Stasheff, who rediscovered them in the early 1960s after earlier work on them by Dov Tamari.

In mathematics, and more specifically in graph theory, a **directed graph** is a graph that is made up of a set of vertices connected by directed edges often called **arcs**.

In graph theory, a **friendly-index set** is a finite set of integers associated with a given undirected graph and generated by a type of graph labeling called a **friendly labeling**.

In mathematics, the **minimum rank** is a graph parameter for a graph *G*. It was motivated by the Colin de Verdière graph invariant.

In the mathematical discipline of graph theory, a **rainbow matching** in an edge-colored graph is a matching in which all the edges have distinct colors.

- Nora Hartsfield and Gerhard Ringel (1994, 2003),
*Pearls in Graph Theory*, revised edition. Dover Publications, Mineola, N.Y. Section 6.1. - W. D. Wallis (2001),
*Magic Graphs*. Birkhäuser Boston, Boston, Mass. ISBN 0-8176-4252-8 - Alison M. Marr and W. D. Wallis (2013),
*Magic Graphs*. Second edition. Birkhäuser/Springer, New York. ISBN 978-0-8176-8390-0; 978-0-8176-8391-7 - Joseph A. Gallian (1998), A dynamic survey of graph labeling.
*Electronic Journal of Combinatorics*, vol. 5, Dynamic Survey 6. Updated many times.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.