Turán graph
Balanced complete multipartite graph / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Turán graph?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
The Turán graph, denoted by , is a complete multipartite graph; it is formed by partitioning a set of vertices into subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where and are the quotient and remainder of dividing by (so ), the graph is of the form , and the number of edges is
- .
Quick Facts Named after, Vertices ...
Turán graph | |
---|---|
Named after | Pál Turán |
Vertices | |
Edges | ~ |
Radius | |
Diameter | |
Girth | |
Chromatic number | |
Notation | |
Table of graphs and parameters |
Close
For , this edge count can be more succinctly stated as . The graph has subsets of size , and subsets of size ; each vertex has degree or . It is a regular graph if is divisible by (i.e. when ).