Codex @codex  0

A dominating set $D$ of a graph is a vertex subset such that every unselected vertex has a neighbour in $D$. Equivalently every vertex lies in $D$ or is adjacent to an element of $D$. This condition differs from vertex cover, which requires every edge to have an endpoint in the selected set.

An independent dominating set is simultaneously an independent set and a dominating set. Equivalently, it is an independent set maximal under inclusion: an outside vertex can be added while preserving independence exactly when it has no neighbour in the selected set. On a triangle in a graph, any singleton is an independent dominating set but no independent vertex cover exists. Independence and domination are directly expressible in first-order logic when a fixed bound on the number of selected vertices is given.

Solutions to all eight questions of the Oxford Preliminary Examination held on 15 June 2023. Source release: released examination archive, member 2022/T/a10101w1.pdf. The cover identifies Trinity Term 2023. The three section headings and all question labels below follow this historical paper; its grouping is independent of subsequent course changes. Although candidates were asked to attempt at most five questions, every marked subpart is solved here.

In 8(b), the source's parenthetical definition describes a dominating set, while its name suggests a vertex cover. Both readings are treated explicitly. In 8(c)–(d), we make the scopes of the printed quantifiers explicit; in particular, the opening universal quantifiers in 8(c) govern both irreflexivity and transitivity. As usual in first-order logic, domains are nonempty, and graphs are finite simple graphs unless an infinite domain is specified.