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

Brewster, R.C.; Mynhardt, C.M.; Teshima, L.E.

Accesso libero

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

,

e

21 feb 2024

Annales Mathematicae Silesianae

Volume 39 (2025): Numero 1 (Marzo 2025)

INFORMAZIONI SU QUESTO ARTICOLO

Articolo precedente

Articolo Successivo

Cita

Scarica la copertina

Pubblicato online: 21 feb 2024

Pagine: 94 - 129

Ricevuto: 14 apr 2023

Accettato: 17 gen 2024

DOI: https://doi.org/10.2478/amsil-2024-0002

Parole chiave
05C69

© 2024 R.C. Brewster et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Reconfiguration structure of an induced C4 subgraph from Proposition 3.6

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

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

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

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

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

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

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, 5〉, with Θ 〈2, 2, 5〉 overlaid in red

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

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

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

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.

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

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

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〉.

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〉

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

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〉

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〉.

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〉

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〉

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

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	K_2,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

Lingua:: Inglese

Frequenza di pubblicazione:: 2 volte all'anno
Argomenti della rivista:: Matematica, Matematica generale

Feed RSS della rivista

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

Pubblicato online: 21 feb 2024

Pagine: 94 - 129

Ricevuto: 14 apr 2023

Accettato: 17 gen 2024

DOI: https://doi.org/10.2478/amsil-2024-0002

Parole chiave
05C69

© 2024 R.C. Brewster et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

Figure 13.

Figure 14.

Figure 15.

Figure 16.

Figure 17.

Figure 18.

Figure 19.

Figure 20.

Figure 21.

Figure 22.

Figure 23.

Figure 24.

Figure 25.

Figure 26.

Figure 27.

Figure 28.

Figure 29.

i-graph realizability of theta graphs

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

R.C. Brewster

C.M. Mynhardt

L.E. Teshima

Pubblicato online: 21 feb 2024

Pagine: 94 - 129

Ricevuto: 14 apr 2023

Accettato: 17 gen 2024

DOI: https://doi.org/10.2478/amsil-2024-0002

Parole chiave05C69

© 2024 R.C. Brewster et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

Figure 13.

Figure 14.

Figure 15.

Figure 16.

Figure 17.

Figure 18.

Figure 19.

Figure 20.

Figure 21.

Figure 22.

Figure 23.

Figure 24.

Figure 25.

Figure 26.

Figure 27.

Figure 28.

Figure 29.

i-graph realizability of theta graphs

Parole chiave
05C69