Ch. 13: Domination
From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 13.1. The Domination Number of a Graph 13.2. Exploration: Stratification 13.3. Exploration: Lights Out 13.4. Excursion: And Still It Grows More Colorful
60 flashcards · Mathematics · by lakesare
Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses
What is the closed neighborhood N[v]N[v]N[v] of a vertex vvv , and how does it differ from the (open) neighborhood N(v)N(v)N(v) ?
N[v]=N(v)∪{v}\boldsymbol{N[v] = N(v) \cup \{v\}}N[v]=N(v)∪{v} : the neighbors of vvv together with vvv itself. N(v)N(v)N(v) is the set of neighbors of vvv only.
Which vertices does a vertex vvv dominate, and how many are there?
vvv itself and each of its neighbors, i.e. the vertices of N[v]N[v]N[v] : that is 1+degv\boldsymbol{1 + \deg v}1+degv vertices.
What is a dominating set of a graph GGG ?
A set S⊆V(G)S \subseteq V(G)S⊆V(G) such that every vertex of GGG is dominated by some vertex of SSS . Equivalently: every vertex of V(G)−SV(G) - SV(G)−S is adjacent to some vertex of SSS . Two dominating sets (solid vertices) in the same graph.
What is the domination number γ(G)\gamma(G)γ(G) of a graph GGG ?
The minimum cardinality of a dominating set of GGG . A dominating set of that size is a minimum dominating set. The same symbol γ(G)\gamma(G)γ(G) is used for the genus, but the two never occur in the same discussion.
Who started the study of domination in graphs, and when did it become an area of study by many?
Claude Berge (1958) and Oystein Ore (1962), with Ore using the term; it took off after a 1977 article by Ernie Cockayne and Stephen Hedetniemi. In 1998 Teresa Haynes, Hedetniemi and Peter Slater wrote a book devoted to domination; well over 2000 articles have been written on it.
GGG is a graph of order nnn . Between which bounds does γ(G)\gamma(G)γ(G) lie, and why is it always defined?
1≤γ(G)≤n\boldsymbol{1 \le \gamma(G) \le n}1≤γ(G)≤n V(G)V(G)V(G) itself is always a dominating set.
When does a graph GGG of order nnn have domination number γ(G)=1\gamma(G) = 1γ(G)=1 ?
If and only if GGG has a vertex vvv of degree n−1n - 1n−1 , and then {v}\{v\}{v} is a minimum dominating set. So all complete graphs and all stars have domination number 1.
When does a graph GGG of order nnn have domination number γ(G)=n\gamma(G) = nγ(G)=n ?
If and only if G=Kn‾G = \overline{K_n}G=Kn (no edges at all). Then V(G)V(G)V(G) is the unique (minimum) dominating set.
To show that γ(G)=k\gamma(G) = kγ(G)=k for a graph GGG , what two things must you do?
Find a dominating set with kkk vertices ( γ(G)≤k\gamma(G) \le kγ(G)≤k ), and show that every dominating set has at least kkk vertices ( γ(G)≥k\gamma(G) \ge kγ(G)≥k ).
This graph GGG has order 11, maximum degree 4, and {u,v,w}\{u, v, w\}{u,v,w} is a dominating set. Why is γ(G)=3\gamma(G) = 3γ(G)=3 ?
Each vertex dominates at most 1+4=51 + 4 = 51+4=5 vertices, so two vertices dominate at most 10<1110 < 1110<11 . So γ(G)>2\gamma(G) > 2γ(G)>2 , and {u,v,w}\{u, v, w\}{u,v,w} gives γ(G)≤3\gamma(G) \le 3γ(G)≤3 .
A city has 3 horizontal and 4 vertical streets (12 intersections). A guard at an intersection watches it and every intersection one block away along a street. Which graph parameter is the smallest number of guards that watch all intersections, and what is its value?
The domination number of the grid P3×P4P_3 \times P_4P3×P4 , which is 4. Intersections are vertices, joined when they are the two ends of one block. Solid: four guards that suffice.
The grid P3×P4P_3 \times P_4P3×P4 has 12 vertices: two of degree 4, six of degree 3 and four of degree 2. It is bipartite, with 6 red and 6 blue vertices.Why can't 3 vertices dominate it?
Count by color: among vertices of its own color, a vertex dominates only itself. This forces S={x,y,z}S = \{x, y, z\}S={x,y,z} below, which misses uuu and vvv . Three vertices of one color dominate only 3 of the 6 vertices of that color, so (say) SSS has two red and one blue vertex. The blue one must dominate the other 4 red vertices, so it is the degree-4 blue vertex xxx , and the red vertices xxx misses are yyy and zzz .
What is the domination number γ(Cn)\gamma(C_n)γ(Cn) of the cycle CnC_nCn , n≥3n \ge 3n≥3 ?
γ(Cn)=⌈n/3⌉\boldsymbol{\gamma(C_n) = \lceil n/3 \rceil}γ(Cn)=⌈n/3⌉ Minimum dominating sets of C6C_6C6 , C7C_7C7 , C8C_8C8 .
γ(Cn)=⌈n/3⌉\gamma(C_n) = \lceil n/3 \rceilγ(Cn)=⌈n/3⌉ for n≥3n \ge 3n≥3 .How does the proof get the lower bound and the upper bound?
Lower: CnC_nCn is 2-regular, so each vertex dominates exactly 3 vertices. Upper: take every third vertex going around the cycle. With n=3q+rn = 3q + rn=3q+r : qqq vertices dominate at most 3q3q3q vertices, so if r≠0r \ne 0r=0 you need q+1q + 1q+1 . Every third vertex, stopping after ⌈n/3⌉\lceil n/3 \rceil⌈n/3⌉ of them, dominates everything.
Theorem 13.3 For a graph GGG of order nnn with maximum degree Δ(G)\Delta(G)Δ(G) : ?≤γ(G)≤ ?\; ? \le \gamma(G) \le \; ??≤γ(G)≤?
n1+Δ(G)≤γ(G)≤n−Δ(G)\boldsymbol{\dfrac{n}{1 + \Delta(G)} \le \gamma(G) \le n - \Delta(G)}1+Δ(G)n≤γ(G)≤n−Δ(G)
Why is γ(G)≤n−Δ(G)\gamma(G) \le n - \Delta(G)γ(G)≤n−Δ(G) for a graph GGG of order nnn ?
Take a vertex vvv of degree Δ(G)\Delta(G)Δ(G) together with the n−(1+Δ(G))n - (1 + \Delta(G))n−(1+Δ(G)) vertices that vvv doesn't dominate. Each of those dominates itself, so this is a dominating set of n−(1+Δ(G))+1=n−Δ(G)n - (1 + \Delta(G)) + 1 = n - \Delta(G)n−(1+Δ(G))+1=n−Δ(G) vertices.
Why is γ(G)≥n1+Δ(G)\gamma(G) \ge \dfrac{n}{1 + \Delta(G)}γ(G)≥1+Δ(G)n for a graph GGG of order nnn ?
kkk vertices dominate at most k(1+Δ(G))k(1 + \Delta(G))k(1+Δ(G)) vertices, and a dominating set must dominate all nnn . For a minimum dominating set {v1,…,vk}\{v_1, \dots, v_k\}{v1,…,vk} : n≤∑(1+degvi)≤k(1+Δ(G))n \le \sum (1 + \deg v_i) \le k(1 + \Delta(G))n≤∑(1+degvi)≤k(1+Δ(G)) .
For a graph GGG of order nnn : γ(G)≤n−Δ(G)\gamma(G) \le n - \Delta(G)γ(G)≤n−Δ(G) .Which graph shows that this bound is sharp for every Δ(G)=r≤n−2\Delta(G) = r \le n - 2Δ(G)=r≤n−2 ?
K1,r∪(n−r−1)K1K_{1,r} \cup (n - r - 1)K_1K1,r∪(n−r−1)K1 : a star plus isolated vertices. The center dominates the star, and each isolated vertex can only be dominated by itself: γ=1+(n−r−1)=n−r\gamma = 1 + (n - r - 1) = n - rγ=1+(n−r−1)=n−r .
For a graph GGG of order nnn : γ(G)≥n1+Δ(G)\gamma(G) \ge \dfrac{n}{1 + \Delta(G)}γ(G)≥1+Δ(G)n .Name 0-regular, 1-regular and 2-regular graphs for which equality holds.
Kn‾\boldsymbol{\overline{K_n}}Kn , kK2\boldsymbol{kK_2}kK2 and C3k\boldsymbol{C_{3k}}C3k . γ(Kn‾)=n=n1\gamma(\overline{K_n}) = n = \frac{n}{1}γ(Kn)=n=1n , γ(kK2)=k=n2\ \gamma(kK_2) = k = \frac{n}{2} γ(kK2)=k=2n , γ(C3k)=k=n3\ \gamma(C_{3k}) = k = \frac{n}{3} γ(C3k)=k=3n .
For a graph GGG of order nnn : γ(G)≥n1+Δ(G)\gamma(G) \ge \dfrac{n}{1 + \Delta(G)}γ(G)≥1+Δ(G)n .Does equality hold for every regular graph?
No: this 3-regular graph of order 20 has γ(G)=6>20/4=5\gamma(G) = 6 > 20/4 = 5γ(G)=6>20/4=5 . Dominating each 5-vertex set {u1,…,u5}\{u_1, \dots, u_5\}{u1,…,u5} (each vertex dominates 4) takes 2 vertices from {u0,…,u5}\{u_0, \dots, u_5\}{u0,…,u5} , and likewise for the vvv 's and www 's.
What is a minimal dominating set of a graph GGG ?
A dominating set SSS of GGG such that no proper subset of SSS is a dominating set. From any dominating set you get one by repeatedly deleting a vertex whose dominated vertices are all dominated by others in the set.
Every minimum dominating set is minimal. Is every minimal dominating set minimum?
No. {v1,v2,v5,v6}\{v_1, v_2, v_5, v_6\}{v1,v2,v5,v6} is minimal in C8C_8C8 (deleting any vertex leaves a vertex undominated), but γ(C8)=⌈8/3⌉=3\gamma(C_8) = \lceil 8/3 \rceil = 3γ(C8)=⌈8/3⌉=3 .
Which vertices of a graph GGG belong to every dominating set of GGG ?
The isolated vertices. An isolated vertex can only be dominated by itself.
Theorem 13.4 Let GGG be a graph without isolated vertices. If SSS is a minimal dominating set of GGG , then … ?
V(G)−SV(G) - SV(G)−S is also a dominating set of GGG . So a graph without isolated vertices has two disjoint dominating sets.
If GGG has no isolated vertices and SSS is a minimal dominating set of GGG , then V(G)−SV(G) - SV(G)−S is a dominating set.What is the key idea of the proof?
If some v∈Sv \in Sv∈S had no neighbor outside SSS , then S−{v}S - \{v\}S−{v} would still dominate, contradicting minimality. vvv is not isolated, so vvv has a neighbor in S−{v}S - \{v\}S−{v} ; and every vertex outside SSS is adjacent to a vertex of SSS other than vvv .
Corollary 13.5 If GGG is a graph of order nnn without isolated vertices, then γ(G)≤ ?\gamma(G) \le \; ?γ(G)≤?
n2\boldsymbol{\dfrac{n}{2}}2n For a minimum dominating set SSS , V(G)−SV(G) - SV(G)−S is also dominating (as SSS is minimal), so ∣S∣≤∣V(G)−S∣|S| \le |V(G) - S|∣S∣≤∣V(G)−S∣ and ∣S∣+∣V(G)−S∣=n|S| + |V(G) - S| = n∣S∣+∣V(G)−S∣=n .
What is a total dominating set of a graph GGG ?
A set S⊆V(G)S \subseteq V(G)S⊆V(G) such that every vertex of GGG is adjacent to at least one vertex of SSS . In total domination, uuu dominates vvv only if vvv is a neighbor of uuu : a vertex doesn't dominate itself, so vertices of SSS also need a neighbor in SSS .
Which graphs have a total dominating set, and what can you say about the subgraph G[S]G[S]G[S] induced by a total dominating set SSS ?
Exactly the graphs with no isolated vertices, and G[S]G[S]G[S] has no isolated vertices.
What is the total domination number γt(G)\gamma_t(G)γt(G) ?
The minimum cardinality of a total dominating set of GGG . A total dominating set of size γt(G)\gamma_t(G)γt(G) is a minimum total dominating set. A graph with γ(G)=3\gamma(G) = 3γ(G)=3 but γt(G)=4\gamma_t(G) = 4γt(G)=4 .
What is the total domination number γt(Cn)\gamma_t(C_n)γt(Cn) of the cycle CnC_nCn , n≥3n \ge 3n≥3 ?
γt(Cn)=⌈n/2⌉\boldsymbol{\gamma_t(C_n) = \lceil n/2 \rceil}γt(Cn)=⌈n/2⌉ if n≢2(mod4)n \not\equiv 2 \pmod 4n≡2(mod4) , and n+22\boldsymbol{\frac{n+2}{2}}2n+2 if n≡2(mod4)n \equiv 2 \pmod 4n≡2(mod4) . C6C_6C6 needs 4, not 3.
Cn=(v1,v2,…,vn,v1)C_n = (v_1, v_2, \dots, v_n, v_1)Cn=(v1,v2,…,vn,v1) .Why is γt(Cn)≥⌈n/2⌉\gamma_t(C_n) \ge \lceil n/2 \rceilγt(Cn)≥⌈n/2⌉ , and which set shows γt(Cn)≤⌈n/2⌉\gamma_t(C_n) \le \lceil n/2 \rceilγt(Cn)≤⌈n/2⌉ when n≢2(mod4)n \not\equiv 2 \pmod 4n≡2(mod4) ?
Each vertex totally dominates only its 2 neighbors; take adjacent pairs with gaps of two: {v1,v2,v5,v6,v9,v10,… }\{v_1, v_2, v_5, v_6, v_9, v_{10}, \dots\}{v1,v2,v5,v6,v9,v10,…} . For n=4kn = 4kn=4k : {v1,v2,…,v4k−3,v4k−2}\{v_1, v_2, \dots, v_{4k-3}, v_{4k-2}\}{v1,v2,…,v4k−3,v4k−2} ; for n=4k+1n = 4k + 1n=4k+1 add v4k+1v_{4k+1}v4k+1 ; for n=4k+3n = 4k + 3n=4k+3 the pairs run up to v4k+1,v4k+2v_{4k+1}, v_{4k+2}v4k+1,v4k+2 .
Cn=(v1,…,vn,v1)C_n = (v_1, \dots, v_n, v_1)Cn=(v1,…,vn,v1) with n=4k+2n = 4k + 2n=4k+2 , and γt(Cn)≥n/2=2k+1\gamma_t(C_n) \ge n/2 = 2k + 1γt(Cn)≥n/2=2k+1 .Why can't a total dominating set SSS have exactly 2k+12k + 12k+1 vertices?
Every 4 consecutive vertices contain at least 2 vertices of SSS , and some two consecutive vj,vj+1v_j, v_{j+1}vj,vj+1 are missing from SSS , which forces vj−2,vj−1,vj+2,vj+3∈Sv_{j-2}, v_{j-1}, v_{j+2}, v_{j+3} \in Svj−2,vj−1,vj+2,vj+3∈S . ( vi+1v_{i+1}vi+1 needs viv_ivi or vi+2v_{i+2}vi+2 , and vi+2v_{i+2}vi+2 needs vi+1v_{i+1}vi+1 or vi+3v_{i+3}vi+3 .) The remaining 4(k−1)4(k-1)4(k−1) vertices form k−1k - 1k−1 blocks of 4, so ∣S∣≥2(k−1)+4=2k+2|S| \ge 2(k - 1) + 4 = 2k + 2∣S∣≥2(k−1)…
GGG has order nnn and no isolated vertices. Between which bounds does γt(G)\gamma_t(G)γt(G) lie, and which graphs attain them?
2≤γt(G)≤n\boldsymbol{2 \le \gamma_t(G) \le n}2≤γt(G)≤n : stars and double stars attain 2, kK2kK_2kK2 attains nnn . A total dominating set contains at least two vertices, since its vertices need neighbors in it.
Theorem 13.7 For every graph GGG with no isolated vertices: ?≤γt(G)≤ ?\; ? \le \gamma_t(G) \le \; ??≤γt(G)≤? (in terms of the domination number γ(G)\gamma(G)γ(G) )
γ(G)≤γt(G)≤2γ(G)\boldsymbol{\gamma(G) \le \gamma_t(G) \le 2\gamma(G)}γ(G)≤γt(G)≤2γ(G) The lower bound holds since every total dominating set is a dominating set.
GGG has no isolated vertices. Why is γt(G)≤2γ(G)\gamma_t(G) \le 2\gamma(G)γt(G)≤2γ(G) ?
Take a minimum dominating set S={v1,…,vk}S = \{v_1, \dots, v_k\}S={v1,…,vk} and add one neighbor uiu_iui of each viv_ivi . The vertices outside SSS are adjacent to SSS , and the vertices of SSS are adjacent to the uiu_iui , so S∪{u1,…,uk}S \cup \{u_1, \dots, u_k\}S∪{u1,…,uk} is a total dominating set of at most 2k2k2k vertices.
For a graph GGG with no isolated vertices: γ(G)≤γt(G)≤2γ(G)\gamma(G) \le \gamma_t(G) \le 2\gamma(G)γ(G)≤γt(G)≤2γ(G) .Which graphs show that both bounds are sharp?
Double stars ( γ=γt=2\gamma = \gamma_t = 2γ=γt=2 ) and a path w1⋯w5w_1 \cdots w_5w1⋯w5 with a pendant path wiviuiw_iv_iu_iwiviui at each wiw_iwi ( γ=5\gamma = 5γ=5 , γt=10\gamma_t = 10γt=10 ). {v1,…,v5}\{v_1, \dots, v_5\}{v1,…,v5} is a minimum dominating set; adding u1,…,u5u_1, \dots, u_5u1,…,u5 gives a minimum total dominating set.
Theorem 13.8 (Cockayne, Dawes, Hedetniemi) If GGG is a connected graph of order n≥3n \ge 3n≥3 , then γt(G)≤ ?\gamma_t(G) \le \; ?γt(G)≤?
2n3\boldsymbol{\dfrac{2n}{3}}32n Compare γ(G)≤n/2\gamma(G) \le n/2γ(G)≤n/2 . Sharp: a path w1⋯w5w_1 \cdots w_5w1⋯w5 with a pendant path wiviuiw_iv_iu_iwiviui at each wiw_iwi has n=15n = 15n=15 and γt=10\gamma_t = 10γt=10 .
What is a kkk -stratified graph?
A graph whose vertex set is partitioned into kkk subsets V1,…,VkV_1, \dots, V_kV1,…,Vk . Unlike in a vertex coloring, no condition is placed on the subsets. Such a partition is a stratification (or kkk -stratification) of GGG . Two 2-stratifications of GGG (solid = red, open = blue).
The subsets V1,…,VkV_1, \dots, V_kV1,…,Vk of a kkk -stratified graph are called its strata, or its color classes.
When are two kkk -stratified graphs GGG and HHH isomorphic?
When some bijection ϕ:V(G)→V(H)\phi: V(G) \to V(H)ϕ:V(G)→V(H) preserves adjacency and colors: uv∈E(G)⇔ϕ(u)ϕ(v)∈E(H)uv \in E(G) \Leftrightarrow \phi(u)\phi(v) \in E(H)uv∈E(G)⇔ϕ(u)ϕ(v)∈E(H) , and xxx , ϕ(x)\phi(x)ϕ(x) have the same color. Such a ϕ\phiϕ is a color-preserving isomorphism.
What is a red-blue coloring of a graph, and when is it a 2-stratification?
Any assignment of red or blue to each vertex; it is a 2-stratification when both colors are used. All vertices red, or all blue, is allowed in a red-blue coloring.
Who initiated the study of stratified graphs, and what motivated it?
Reza Rashidi and Naveed Sherwani in the 1990s, for multilayer routing problems in VLSI circuit chips.
What is the root of a 2-stratified rooted graph FFF ?
A selected blue vertex vvv of FFF . G3G_3G3 has two nonsimilar blue vertices, so it gives two different rooted graphs F′F'F′ and F′′F''F′′ .
FFF is a 2-stratified graph rooted at a blue vertex vvv . What is an FFF -coloring of a graph GGG ?
A red-blue coloring of GGG in which every blue vertex www is the root of a copy of FFF : a subgraph of GGG containing www , with a color-preserving isomorphism from FFF sending vvv to www . Right: the copy of F′F'F′ at the blue vertex u2u_2u2 .
FFF is a 2-stratified rooted graph. What are an FFF -dominating set and the FFF -domination number γF(G)\gamma_F(G)γF(G) of a graph GGG ?
The set of red vertices of an FFF -coloring of GGG ; γF(G)\gamma_F(G)γF(G) is the minimum size of an FFF -dominating set. γF(G)\gamma_F(G)γF(G) is defined for every graph: coloring every vertex red is vacuously an FFF -coloring. An FFF -coloring with γF(G)\gamma_F(G)γF(G) red vertices is a minimum FFF -coloring.
Theorem 13.9. FFF is the 2-stratified K2K_2K2 : one red vertex and one blue root. What is γF(G)\gamma_F(G)γF(G) for every graph GGG ?
γF(G)=γ(G)\boldsymbol{\gamma_F(G) = \gamma(G)}γF(G)=γ(G) , the domination number. An FFF -coloring says exactly that every blue vertex is adjacent to a red vertex, i.e. the red vertices dominate GGG .
How many 2-stratified rooted graphs have the path P3P_3P3 as underlying graph, and why?
Five. Root (blue) at an end: the middle and other end are RR, RB or BR (not BB, as some vertex is red). Root in the middle: the ends are RR or RB. Solid = red, vvv = root.
Theorem 13.10. F1F_1F1 is the path v x yv\,x\,yvxy with blue root vvv at one end and xxx , yyy red. For a graph GGG without isolated vertices, what is γF1(G)\gamma_{F_1}(G)γF1(G) ?
γF1(G)=γt(G)\boldsymbol{\gamma_{F_1}(G) = \gamma_t(G)}γF1(G)=γt(G) , the total domination number. γF1\gamma_{F_1}γF1 is also defined for graphs with isolated vertices, γt\gamma_tγt is not.
F1F_1F1 is the path v x yv\,x\,yvxy with blue root vvv and xxx , yyy red. An F1F_1F1 -coloring: every blue vertex is adjacent to a red vertex that has another red neighbor.For GGG without isolated vertices, how does the proof show γF1(G)=γt(G)\gamma_{F_1}(G) = \gamma_t(G)γF1(G)=γt(G) ?
γF1≤γt\gamma_{F_1} \le \gamma_tγF1≤γt : color a minimum total dominating set red. γt≤γF1\ \gamma_t \le \gamma_{F_1} γt≤γF1 : take a minimum F1F_1F1 -coloring whose red vertices induce the fewest isolated vertices; then every red vertex has a red neighbor, so the red set is total dominating. A red uuu with only blue neighbors could swap colors with a blue neighbor vvv (which has a red neighbor with a red neighbor), giving fewer isolated red vertices.
Theorem 13.11. F2F_2F2 is the path v x yv\,x\,yvxy with blue root vvv at one end, xxx red and yyy blue. For a connected graph GGG of order at least 3, what is γF2(G)\gamma_{F_2}(G)γF2(G) ?
γF2(G)=γ(G)\boldsymbol{\gamma_{F_2}(G) = \gamma(G)}γF2(G)=γ(G) , the domination number. The book does not include the proof.
FFF is a 2-stratified rooted graph and GGG a graph of order nnn . If GGG has no subgraph isomorphic to (uncolored) FFF , then γF(G)=n\gamma_F(G) = nγF(G)=n . Does the converse hold? (Hint: F3F_3F3 is the path v x yv\,x\,yvxy with blue root vvv at one end, xxx blue and yyy red.)
No: γF3(K1,n−1)=n\boldsymbol{\gamma_{F_3}(K_{1,n-1}) = n}γF3(K1,n−1)=n , although the star contains (n−12)\binom{n-1}{2}(2n−1) copies of P3P_3P3 . A blue leaf would need the center blue with another red neighbor; a blue center would need a blue leaf with a red neighbor other than the center. Neither is possible, so no vertex can be blue.
Three offices A, B, C in a row: pressing an office's button reverses the light there and in each adjacent office. All lights are off. What does pressing B do?
All three lights go on ( 000→111000 \to 111000→111 ). Pressing A gives 110110110 , pressing C gives 011011011 .
Light arrangements abc∈{0,1}3abc \in \{0,1\}^3abc∈{0,1}3 of the three offices are the vertices, joined when one button press changes one into the other. Which graph is this?
The 3-cube Q3Q_3Q3 . So from all lights out, any pattern can be reached, with up to three presses.
What is the Lights Out Puzzle on a graph GGG ?
With all lights on: is there a set of buttons whose pressing turns all lights out, and what is the smallest such set? Each vertex has a light and a button; pressing the button at a vertex reverses the light at that vertex and at all its neighbors. On P3P_3P3 , pressing the middle vertex turns all three lights out.
In terms of domination, what is a set SSS of vertices that solves Lights Out (all lights on to all lights out) on a graph GGG ?
A dominating set SSS such that every vertex is dominated by an odd number of vertices of SSS , i.e. ∣N[v]∩S∣|N[v] \cap S|∣N[v]∩S∣ is odd for every vvv . A light ends up out exactly when it is reversed an odd number of times.
Theorem 13.12 (Klaus Sutner) If GGG is a connected graph all of whose vertex lights are on, is there always a set of buttons that turns all the lights out?
Yes, always. The book calls this result possibly unexpected.
Which commercial game gave rise to the Lights Out puzzle on graphs?
Lights Out, an electronic game by Tiger Electronics (Hasbro). Earlier made as a cube; now played on a grid of LEDs.
Which conference series on graph theory did Yousef Alavi play a leading role in organizing, and when did it start?
The Kalamazoo (Michigan) Graph Theory Conferences, from 1968 at Western Michigan University. Nine conferences, every fourth year. In 1963 there was the Czechoslovak Symposium on Graph Theory at Smolenice; in 1969 the Southeastern International Conferences and the British Combinatorial Conferences began.
When did graph theory get its own journal, and who founded it?
1977: the Journal of Graph Theory, founded by Frank Harary. It won the Association of American Publishers award for the best new journal of 1977 in the scientific, medical and technical category.
In the first volume of the Bulletin of the Institute of Combinatorics and Its Applications (1991), what did its president William Tutte argue?
That graph theory (indeed any area of mathematics) is not separate: mathematics is a single unified subject. The Institute was founded in 1990, with Ralph G. Stanton playing the central role.