Accès libre

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
Recherchez cet auteur sur
Sciendo|Google Scholar
Brewster, R.C.
, 
C.M. Mynhardt

C.M. Mynhardt

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Profil Orcid
Recherchez cet auteur sur
Sciendo|Google Scholar
Mynhardt, C.M.
 et 
L.E. Teshima

L.E. Teshima

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Recherchez cet auteur sur
Sciendo|Google Scholar
Teshima, L.E.
  
21 févr. 2024
The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets's Cover Image
À propos de cet article
Article précédent
Article suivant
Citez
Télécharger la couverture
Publié en ligne: 21 févr. 2024
Pages: 94 - 129
Reçu: 14 avr. 2023
Accepté: 17 janv. 2024
DOI: https://doi.org/10.2478/amsil-2024-0002
Mots clés
© 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
Langue:
Anglais
Périodicité:
2 fois par an
Sujets de la revue:
Mathématiques, Mathématiques générales
RSS Feed de la revue