Kneser graph

noun

A graph K(n, k) (alternatively KG_(n,k)), whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent iff the two corresponding sets are disjoint.

Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

nounKneser graph (plural Kneser graphs)

plural Kneser graphs

  1. graph theoryA graph K(n, k) (alternatively KG_(n,k)), whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent iff the two corresponding sets are disjoint.

Origin

Named after Martin Kneser, who first investigated them in 1956.

Full word history & related roots →
Cite this entry
APA

Kneser graph. (n.d.). In WatkinsX Dictionary. Retrieved November 3, 2026, from https://dictionary.watkinsx.com/word/Kneser%20graph

MLA

“Kneser graph.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/Kneser%20graph. Accessed November 3, 2026.

Chicago

WatkinsX Dictionary, s.v. “Kneser graph,” accessed November 3, 2026, https://dictionary.watkinsx.com/word/Kneser%20graph.

Source: Kneser graph on Wiktionary, CC BY-SA 4.0.