Open Access

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

R.C. Brewster

R.C. Brewster

Department of Mathematics and Statistics, Thompson Rivers UniversityKamloops, Canada
Search for this author on
Sciendo|Google Scholar
Brewster, R.C.
, 
C.M. Mynhardt

C.M. Mynhardt

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Orcid profile
Search for this author on
Sciendo|Google Scholar
Mynhardt, C.M.
 and 
L.E. Teshima

L.E. Teshima

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Search for this author on
Sciendo|Google Scholar
Teshima, L.E.
  
Feb 21, 2024
The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets's Cover Image
About this article
Previous Article
Next Article
Cite
Download Cover
Published Online: Feb 21, 2024
Page range: 94 - 129
Received: Apr 14, 2023
Accepted: Jan 17, 2024
DOI: https://doi.org/10.2478/amsil-2024-0002
Keywords
© 2024 R.C. Brewster et al., published by Sciendo
This work is licensed under the Creative Commons Attribution 4.0 International License.

Figure 1.

Reconfiguration structure of an induced C4 subgraph from Proposition 3.6
Reconfiguration structure of an induced C4 subgraph from Proposition 3.6

Figure 2.

The graph G for Proposition 3.8 with ℐ (G) = ℋ
The graph G for Proposition 3.8 with ℐ (G) = ℋ

Figure 3.

The complement and line graphs complement of the well-covered house graph ℋ
The complement and line graphs complement of the well-covered house graph ℋ

Figure 4.

The “paw” H with L(H) ≅ 𝔇
The “paw” H with L(H) ≅ 𝔇

Figure 5.

A graph G̅ (left) such that ℐ (G) = Θ 〈1, 4, 5〉 (right)
A graph G̅ (left) such that ℐ (G) = Θ 〈1, 4, 5〉 (right)

Figure 6.

The graph G̅ from Construction 5.5 such that ℐ (G) = Θ 〈1, k, ℓ〉 for 3 ≤ k ≤ ℓ
The graph G̅ from Construction 5.5 such that ℐ (G) = Θ 〈1, k, ℓ〉 for 3 ≤ k ≤ ℓ

Figure 7.

The wheel Hk = Wk+1, with the i-graph of its complement, ℐHk¯≅𝒜Hk¯≅Ck {\cal {I}}\left( {\overline {{H_k}} } \right) \cong {\cal {A}}\left( {\overline {{H_k}} } \right) \cong {C_k} , embedded in red
The wheel Hk = Wk+1, with the i-graph of its complement, ℐHk¯≅𝒜Hk¯≅Ck {\cal {I}}\left( {\overline {{H_k}} } \right) \cong {\cal {A}}\left( {\overline {{H_k}} } \right) \cong {C_k} , embedded in red

Figure 8.

The fan Hk = K1 ∨ Pk, with the i-graph of its complement, ℐHk¯≅𝒜Hk¯≅Pk−1 {\cal {I}}\left( {\overline {{H_k}} } \right) \cong {\cal {A}}\left( {\overline {{H_k}} } \right) \cong {P_{k - 1}} , embedded in red
The fan Hk = K1 ∨ Pk, with the i-graph of its complement, ℐHk¯≅𝒜Hk¯≅Pk−1 {\cal {I}}\left( {\overline {{H_k}} } \right) \cong {\cal {A}}\left( {\overline {{H_k}} } \right) \cong {P_{k - 1}} , embedded in red

Figure 9.

The graph G̅ from Construction 5.9 such that ℐ (G) = Θ 〈2, 2, ℓ〉 for ℓ ≥ 6
The graph G̅ from Construction 5.9 such that ℐ (G) = Θ 〈2, 2, ℓ〉 for ℓ ≥ 6

Figure 10.

The graph G̅ from Construction 5.9 such that ℐ (G) = Θ 〈2, 2, 5〉, with Θ 〈2, 2, 5〉 overlaid in red
The graph G̅ from Construction 5.9 such that ℐ (G) = Θ 〈2, 2, 5〉, with Θ 〈2, 2, 5〉 overlaid in red

Figure 11.

The graph G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} from Construction 5.11 (a) such that ℐ (G2,3, ℓ) = 𝒜 (G2,3, ℓ) = Θ 〈2, 3, ℓ〉 for ℓ ≥ 6
The graph G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} from Construction 5.11 (a) such that ℐ (G2,3, ℓ) = 𝒜 (G2,3, ℓ) = Θ 〈2, 3, ℓ〉 for ℓ ≥ 6

Figure 12.

The graph G2,3,5¯ \overline {{G_{2,3,5}}} from Construction 5.11 (b) such that ℐ (G2,3,5) = Θ 〈2, 3, 5〉, with ℐ (G2,3,5) over-laid in red
The graph G2,3,5¯ \overline {{G_{2,3,5}}} from Construction 5.11 (b) such that ℐ (G2,3,5) = Θ 〈2, 3, 5〉, with ℐ (G2,3,5) over-laid in red

Figure 13.

A graph G̅ such that ℐ (G) = Θ 〈2, 4, 4〉
A graph G̅ such that ℐ (G) = Θ 〈2, 4, 4〉

Figure 14.

The graph G2,5,5¯ \overline {{G_{2,5,5}}} from Construction 5.15 such that ℐ (G) = Θ 〈2, 5, 5〉, with ℐ (G) overlaid in red.
The graph G2,5,5¯ \overline {{G_{2,5,5}}} from Construction 5.15 such that ℐ (G) = Θ 〈2, 5, 5〉, with ℐ (G) overlaid in red.

Figure 15.

The graph G2,k,ℓ¯ \overline {{G_{2,k,\ell }}} from Construction 5.17 such that ℐG2,k,ℓ¯=Θ2,k,ℓ {\cal {I}}\left( {\overline {{G_{2,k,\ell }}} } \right) = \Theta \left\langle {2,k,\ell } \right\rangle for ℓ ≥ k ≥ 4 and ℓ ≥ 6
The graph G2,k,ℓ¯ \overline {{G_{2,k,\ell }}} from Construction 5.17 such that ℐG2,k,ℓ¯=Θ2,k,ℓ {\cal {I}}\left( {\overline {{G_{2,k,\ell }}} } \right) = \Theta \left\langle {2,k,\ell } \right\rangle for ℓ ≥ k ≥ 4 and ℓ ≥ 6

Figure 16.

A graph G̅ such that ℐ (G) = Θ 〈3, 3, 4〉
A graph G̅ such that ℐ (G) = Θ 〈3, 3, 4〉

Figure 17.

A graph G3,3,5¯ \overline {{G_{3,3,5}}} from Construction 5.20 such that ℐ (G3,3,5) = Θ 〈3, 3, 5〉.
A graph G3,3,5¯ \overline {{G_{3,3,5}}} from Construction 5.20 such that ℐ (G3,3,5) = Θ 〈3, 3, 5〉.

Figure 18.

The graph G3,3,6¯ \overline {{G_{3,3,6}}} from Construction 5.22 such that ℐ (G3,3,6) = 𝒜 (G3,3,6) = Θ 〈3, 3, 6〉
The graph G3,3,6¯ \overline {{G_{3,3,6}}} from Construction 5.22 such that ℐ (G3,3,6) = 𝒜 (G3,3,6) = Θ 〈3, 3, 6〉

Figure 19.

The graph G3,3,ℓ¯ \overline {{G_{3,3,\ell }}} from Construction 5.22 such that ℐ (G) = 𝒜 (G) = Θ 〈3, 3, ℓ〉 for ℓ ≥ 6
The graph G3,3,ℓ¯ \overline {{G_{3,3,\ell }}} from Construction 5.22 such that ℐ (G) = 𝒜 (G) = Θ 〈3, 3, ℓ〉 for ℓ ≥ 6

Figure 20.

The graph G3,4,4¯ \overline {{G_{3,4,4}}} from Construction 5.24 such that ℐ (G3,4,4) = Θ 〈3, 4, 4〉
The graph G3,4,4¯ \overline {{G_{3,4,4}}} from Construction 5.24 such that ℐ (G3,4,4) = Θ 〈3, 4, 4〉

Figure 21.

A graph G3,5,5¯ \overline {{G_{3,5,5}}} from Construction 5.28 such that ℐ (G3,5,5) = Θ 〈3, 5, 5〉.
A graph G3,5,5¯ \overline {{G_{3,5,5}}} from Construction 5.28 such that ℐ (G3,5,5) = Θ 〈3, 5, 5〉.

Figure 22.

The graph G4,4,4¯ \overline {{G_{4,4,4}}} from Construction 5.30 such that ℐ (G4,4,4) = Θ 〈4, 4, 4〉
The graph G4,4,4¯ \overline {{G_{4,4,4}}} from Construction 5.30 such that ℐ (G4,4,4) = Θ 〈4, 4, 4〉

Figure 23.

A graph G5,5,5¯ \overline {{G_{5,5,5}}} from Construction 5.28 such that ℐ (G5,5,5) = Θ 〈5, 5, 5〉
A graph G5,5,5¯ \overline {{G_{5,5,5}}} from Construction 5.28 such that ℐ (G5,5,5) = Θ 〈5, 5, 5〉

Figure 24.

The graph Gj,k,ℓ¯ \overline {{G_{j,k,\ell }}} from Construction 5.34 such that ℐ (Gj, k, ℓ) = Θ 〈j, k, ℓ〉 for 3 ≤ j ≤ k ≤ ℓ and ℓ ≥ 6
The graph Gj,k,ℓ¯ \overline {{G_{j,k,\ell }}} from Construction 5.34 such that ℐ (Gj, k, ℓ) = Θ 〈j, k, ℓ〉 for 3 ≤ j ≤ k ≤ ℓ and ℓ ≥ 6

Figure 25.

H = Θ 〈2, 2, 4〉 non-construction
H = Θ 〈2, 2, 4〉 non-construction

Figure 26.

H = Θ 〈2, 3, 3〉 non-construction
H = Θ 〈2, 3, 3〉 non-construction

Figure 27.

H = Θ 〈2, 3, 4〉 non-construction
H = Θ 〈2, 3, 4〉 non-construction

Figure 28.

H = Θ 〈3, 3, 3〉 non-construction
H = Θ 〈3, 3, 3〉 non-construction

Figure 29.

A non-theta non-i-graph 𝒯.
A non-theta non-i-graph 𝒯.

i-graph realizability of theta graphs

Θ 〈j, k, ℓ〉 Realizability Result
Θ 〈1, 2, 2〉 non-i-graph 𝔇. Proposition 3.7
Θ 〈1, 2, ℓ〉, ℓ ≥ 3 i-graph Lemma 5.4
Θ 〈1, k, ℓ〉, 3 ≤ k ≤ ℓ i-graph Lemma 5.6
Θ 〈2, 2, 2〉 non-i-graph K2,3. Proposition 3.7
Θ 〈2, 2, 3〉 non-i-graph κ. Proposition 3.7
Θ 〈2, 2, 4〉 non-i-graph Proposition 6.1
Θ 〈2, 2, ℓ〉, ℓ ≥ 5 i-graph Lemma 5.10
Θ 〈2, 3, 3〉 non-i-graph Proposition 6.2
Θ 〈2, 3, 4〉 non-i-graph Proposition 6.3
Θ 〈2, 3, ℓ〉, ℓ ≥ 5 i-graph Lemma 5.12
Θ 〈2, 4, 4〉 i-graph Lemma 5.14
Θ 〈2, k, 5〉, 4 ≤ k ≤ 5 i-graph Lemma 5.16
Θ 〈2, k, ℓ〉, k ≥ 4, ℓ ≥ 6, ℓ ≥ k i-graph Lemma 5.18
Θ 〈3, 3, 3〉 non-i-graph Proposition 6.4
Θ 〈3, 3, 4〉 i-graph Lemma 5.19
Θ 〈3, 3, 5〉 i-graph Lemma 5.21
Θ 〈3, 3, ℓ〉, ℓ ≥ 6 i-graph Lemma 5.23
Θ 〈3, 4, 4〉 i-graph Lemma 5.25
Θ 〈3, 4, ℓ〉, ℓ ≥ 5 i-graph Lemma 5.27
Θ 〈3, 5, 5〉 i-graph Lemma 5.29
Θ 〈4, 4, 4〉 i-graph Lemma 5.31
Θ 〈j, k, 5〉, 4 ≤ j ≤ k ≤ 5. i-graph Lemma 5.33
Θ 〈j, k, ℓ〉, 3 ≤ j ≤ k ≤ ℓ, and ℓ ≥ 6. i-graph Lemma 5.35
Language:
English
Publication timeframe:
2 times per year
Journal Subjects:
Mathematics, General Mathematics
Journal RSS Feed