Have a personal or library account? Click to login
The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets Cover

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

Annales Mathematicae Silesianae
Volume 39 (2025): Issue 1 (March 2025)
By: R.C. Brewster,  C.M. Mynhardt and  L.E. Teshima  
Open Access
|Feb 2024

Figures & Tables

Figure 1.

Reconfiguration structure of an induced C4 subgraph from Proposition 3.6

Figure 2.

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

Figure 3.

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

Figure 4.

The “paw” H with L(H) ≅ 𝔇

Figure 5.

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 ≤ ℓ

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

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

Figure 9.

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

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

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

Figure 13.

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.

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

Figure 16.

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

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〉

Figure 19.

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〉

Figure 21.

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〉

Figure 23.

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

Figure 25.

H = Θ 〈2, 2, 4〉 non-construction

Figure 26.

H = Θ 〈2, 3, 3〉 non-construction

Figure 27.

H = Θ 〈2, 3, 4〉 non-construction

Figure 28.

H = Θ 〈3, 3, 3〉 non-construction

Figure 29.

A non-theta non-i-graph 𝒯.

i-graph realizability of theta graphs

Θ 〈j, k, ℓ〉RealizabilityResult
Θ 〈1, 2, 2〉non-i-graph𝔇. Proposition 3.7
Θ 〈1, 2, ℓ〉, ℓ ≥ 3i-graphLemma 5.4
Θ 〈1, k, ℓ〉, 3 ≤ k ≤ ℓi-graphLemma 5.6
Θ 〈2, 2, 2〉non-i-graphK2,3. Proposition 3.7
Θ 〈2, 2, 3〉non-i-graphκ. Proposition 3.7
Θ 〈2, 2, 4〉non-i-graphProposition 6.1
Θ 〈2, 2, ℓ〉, ℓ ≥ 5i-graphLemma 5.10
Θ 〈2, 3, 3〉non-i-graphProposition 6.2
Θ 〈2, 3, 4〉non-i-graphProposition 6.3
Θ 〈2, 3, ℓ〉, ℓ ≥ 5i-graphLemma 5.12
Θ 〈2, 4, 4〉i-graphLemma 5.14
Θ 〈2, k, 5〉, 4 ≤ k ≤ 5i-graphLemma 5.16
Θ 〈2, k, ℓ〉, k ≥ 4, ℓ ≥ 6, ℓ ≥ ki-graphLemma 5.18
Θ 〈3, 3, 3〉non-i-graphProposition 6.4
Θ 〈3, 3, 4〉i-graphLemma 5.19
Θ 〈3, 3, 5〉i-graphLemma 5.21
Θ 〈3, 3, ℓ〉, ℓ ≥ 6i-graphLemma 5.23
Θ 〈3, 4, 4〉i-graphLemma 5.25
Θ 〈3, 4, ℓ〉, ℓ ≥ 5i-graphLemma 5.27
Θ 〈3, 5, 5〉i-graphLemma 5.29
Θ 〈4, 4, 4〉i-graphLemma 5.31
Θ 〈j, k, 5〉, 4 ≤ j ≤ k ≤ 5.i-graphLemma 5.33
Θ 〈j, k, ℓ〉, 3 ≤ j ≤ k ≤ ℓ, and ℓ ≥ 6.i-graphLemma 5.35
DOI: https://doi.org/10.2478/amsil-2024-0002 | Journal eISSN: 2391-4238 | Journal ISSN: 0860-2107
Journal RSS Feed
Language: English
Page range: 94 - 129
Submitted on: Apr 14, 2023
|
Accepted on: Jan 17, 2024
|
Published on: Feb 21, 2024
Published by: University of Silesia in Katowice, Institute of Mathematics
In partnership with: Paradigm Publishing Services
Publication frequency: 2 issues per year
Keywords:
05C69
Related subjects:
Mathematics,
General mathematics

© 2024 R.C. Brewster, C.M. Mynhardt, L.E. Teshima, published by University of Silesia in Katowice, Institute of Mathematics
This work is licensed under the Creative Commons Attribution 4.0 License.

Previous articleVolume 39 (2025): Issue 1 (March 2025)Next article