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 n2 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 Kn,n. The two vertex sets of Kn,n correspond to the rows and the columns of the square, respectively, and the label on an edge risj is the value in row i, column j of the semimagic square.
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 graphsG 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 n2 in a square, such that the sums of the n rows, the n columns and the two diagonals form a sequence of 2n + 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 CTC is a multiple of the identity matrix I. Thus, if the matrix has order n, CTC = (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 associahedronKn 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.