Create a Turán graph

Turán graphs are complete multipartite graphs with the property that the sizes of the partitions are as close to equal as possible.

Usage

make_turan(n, r)

turan(...)

Arguments

n

Integer, the number of vertices in the graph.

r

Integer, the number of partitions in the graph, must be positive.

...

Passed to make_turan().

Value

An igraph graph with a vertex attribute type storing the partition index of each vertex. Partition indices start from 1.

Details

The Turán graph with n vertices and r partitions is the densest graph on n vertices that does not contain a clique of size r+1.

This function generates undirected graphs. The null graph is returned when the number of vertices is zero. A complete graph is returned if the number of partitions is greater than the number of vertices.

See also

Other deterministic constructors: graph_from_atlas(), graph_from_edgelist(), graph_from_literal(), make_(), make_chordal_ring(), make_circulant(), make_empty_graph(), make_full_citation_graph(), make_full_graph(), make_full_multipartite(), make_graph(), make_lattice(), make_ring(), make_star(), make_tree()

Related documentation in the C library

turan().

Examples

# Create a Turán graph with 10 vertices and 3 partitions
g <- make_turan(10, 3)
plot(g)


# The sizes of the partitions are as balanced as possible
table(V(g)$type)
#> 
#> 1 2 3 
#> 4 3 3