In combinatorial mathematics, **Toida's conjecture**, due to Shunichi Toida in 1977,^{ [1] } is a refinement of the disproven Ádám's conjecture from 1967.

Both conjectures concern circulant graphs. These are graphs defined from a positive integer and a set of positive integers. Their vertices can be identified with the numbers from 0 to , and two vertices and are connected by an edge whenever their difference modulo belongs to set . Every symmetry of the cyclic group of addition modulo gives rise to a symmetry of the -vertex circulant graphs, and Ádám conjectured (incorrectly) that these are the only symmetries of the circulant graphs.

However, the known counterexamples to Ádám's conjecture involve sets in which some elements share non-trivial divisors with . Toida's conjecture states that, when every member of is relatively prime to , then the only symmetries of the circulant graph for and are symmetries coming from the underlying cyclic group.

The conjecture was proven in the special case where *n* is a prime power by Klin and Poschel in 1978,^{ [2] } and by Golfand, Najmark, and Poschel in 1984.^{ [3] }

The conjecture was then fully proven by Muzychuk, Klin, and Poschel in 2001 by using Schur algebra,^{ [4] } and simultaneously by Dobson and Morris in 2002 by using the classification of finite simple groups.^{ [5] }

- ↑ S. Toida: "A note on Adam's conjecture", Journal of Combinatorial Theory (B), pp. 239–246, October–December 1977
- ↑ Klin, M.H. and R. Poschel: The Konig problem, the isomorphism problem for cyclic graphs and the method of Schur rings, Algebraic methods in graph theory, Vol. I, II., Szeged, 1978, pp. 405–434.
- ↑ Golfand, J.J., N.L. Najmark and R. Poschel: The structure of S-rings over Z2m, preprint (1984).
- ↑ Klin, M.H., M. Muzychuk and R. Poschel: The isomorphism problem for circulant graphs via Schur ring theory, Codes and Association Schemes, American Math. Society, 2001.
- ↑ Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true",
*Electronic Journal of Combinatorics*,**9**(1): R35:1–R35:14, MR 1928787

In mathematics, when the elements of some set have a notion of equivalence, then one may naturally split the set into **equivalence classes**. These equivalence classes are constructed so that elements and belong to the same **equivalence class** if, and only if, they are equivalent.

In mathematics, an **isomorphism** is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are **isomorphic** if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσος*isos* "equal", and μορφή*morphe* "form" or "shape".

In mathematics, a **group** is a non-empty set with an operation that satisfies the following constraints: the operation is associative, has an identity element, and every element of the set has an inverse element.

In mathematics, **modular arithmetic** is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the **modulus**. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book *Disquisitiones Arithmeticae*, published in 1801.

In mathematics, the **Klein four-group** is an abelian group with four elements, in which each element is self-inverse (composing it with itself produces the identity) and in which composing any two of the three non-identity elements produces the third one. It can be described as the symmetry group of a non-square rectangle (with the three non-identity elements being horizontal and vertical reflection and 180-degree rotation), as the group of bitwise exclusive or operations on two-bit binary values, or more abstractly as Z_{2} × Z_{2}, the direct product of two copies of the cyclic group of order 2. It was named * Vierergruppe* (meaning four-group) by Felix Klein in 1884. It is also called the

In group theory, a branch of abstract algebra in pure mathematics, a **cyclic group** or **monogenous group** is a group, denoted C_{n}, that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element *g* such that every other element of the group may be obtained by repeatedly applying the group operation to *g* or its inverse. Each element can be written as an integer power of *g* in multiplicative notation, or as an integer multiple of *g* in additive notation. This element *g* is called a *generator* of the group.

In the mathematical field of graph theory, the **Petersen graph** is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In the mathematical field of graph theory, a **cubic graph** is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called **trivalent graphs**.

In graph theory, a **circulant graph** is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a **cyclic graph**, but this term has other meanings.

In mathematics, **Paley graphs** are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally.

In the mathematical field of graph theory, the **Rado graph**, **Erdős–Rényi graph**, or **random graph** is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

**Frucht's theorem** is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group *G* there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to *G*.

In geometry, the **moment curve** is an algebraic curve in *d*-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

**Italo Jose Dejter** is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In mathematics, and more specifically in combinatorial commutative algebra, a **zero-divisor graph** is an undirected graph representing the zero divisors of a commutative ring. It has elements of the ring as its vertices, and pairs of elements whose product is zero as its edges.

**Sergei Alekseevich Evdokimov** was a Russian mathematician who contributed to the theory of modular forms, computational complexity theory, algebraic combinatorics and p-adic analysis.

**Joy Morris** is a Canadian mathematician whose research involves group theory, graph theory, and the connections between the two through Cayley graphs. She is also interested in mathematics education, is the author of two open-access undergraduate mathematics textbooks, and oversees a program in which university mathematics education students provide a drop-in mathematics tutoring service for parents of middle school students. She is a professor of mathematics at the University of Lethbridge.

**Hunter Snevily** (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

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.