Acceso abierto

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
Buscar este autor en
Sciendo|Google Scholar
Brewster, R.C.
, 
C.M. Mynhardt

C.M. Mynhardt

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Perfil de Orcid
Buscar este autor en
Sciendo|Google Scholar
Mynhardt, C.M.
 y 
L.E. Teshima

L.E. Teshima

Department of Mathematics and Statistics, University of VictoriaVictoria, Canada
Buscar este autor en
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
Acerca de este artículo
Artículo anterior
Artículo siguiente
Cite
Descargar portada
Publicado en línea: 21 feb 2024
Páginas: 94 - 129
Recibido: 14 abr 2023
Aceptado: 17 ene 2024
DOI: https://doi.org/10.2478/amsil-2024-0002
Palabras clave
© 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
Idioma:
Inglés
Calendario de la edición:
2 veces al año
Temas de la revista:
Matemáticas, Matemáticas generales
RSS Feed de revista