Uneingeschränkter Zugang

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
Suche nach diesem Autor auf
Sciendo|Google Scholar
Brewster, R.C.
, 
C.M. Mynhardt

C.M. Mynhardt

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Orcid-Profil
Suche nach diesem Autor auf
Sciendo|Google Scholar
Mynhardt, C.M.
 und 
L.E. Teshima

L.E. Teshima

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Suche nach diesem Autor auf
Sciendo|Google Scholar
Teshima, L.E.
  
21. Feb. 2024
The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets's Cover Image
Über diesen Artikel
Vorheriger Artikel
Nächster Artikel
Zitieren
COVER HERUNTERLADEN
Online veröffentlicht: 21. Feb. 2024
Seitenbereich: 94 - 129
Eingereicht: 14. Apr. 2023
Akzeptiert: 17. Jan. 2024
DOI: https://doi.org/10.2478/amsil-2024-0002
Schlüsselwörter
© 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
Sprache:
Englisch
Zeitrahmen der Veröffentlichung:
2 Hefte pro Jahr
Fachgebiete der Zeitschrift:
Mathematik, Mathematik, Allgemeines
Zeitschrift RSS Feed