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

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

Otwarty dostęp

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

,

oraz

21 lut 2024

Annales Mathematicae Silesianae

Tom 39 (2025): Zeszyt 1 (Marzec 2025)

O artykule

Poprzedni artykuł

Następny artykuł

Zacytuj

Udostępnij

Pobierz okładkę

Data publikacji: 21 lut 2024

Zakres stron: 94 - 129

Otrzymano: 14 kwi 2023

Przyjęty: 17 sty 2024

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

Słowa kluczowe
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

Język:: Angielski

Częstotliwość wydawania:: 2 razy w roku
Dziedziny czasopisma:: Matematyka, Matematyka ogólna

Kanał RSS czasopisma

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

Data publikacji: 21 lut 2024

Zakres stron: 94 - 129

Otrzymano: 14 kwi 2023

Przyjęty: 17 sty 2024

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

Słowa kluczowe
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

Data publikacji: 21 lut 2024

Zakres stron: 94 - 129

Otrzymano: 14 kwi 2023

Przyjęty: 17 sty 2024

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

Słowa kluczowe05C69

© 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

Słowa kluczowe
05C69