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

Our main topic is the characterization of theta graphs that are obtainable as reconfiguration graphs with respect to the minimum independent dominating sets of some graph.

In graph theory, reconfiguration problems are often concerned with solutions to a specific problem that are vertex subsets of a graph. When this is the case, the reconfiguration problem can be viewed as a token manipulation problem, where a solution subset is represented by placing a token at each vertex of the subset. Each solution is represented as a vertex of a new graph, referred to as a reconfiguration graph, where adjacency between vertices corresponds to a predefined token manipulation rule called the reconfiguration step. The reconfiguration step we consider here consists of sliding a single token along an edge between adjacent vertices belonging to different solutions.

More formally, given a graph G, the slide graph of G is the graph H such that each vertex of H represents a solution of some problem on G, and two vertices u and v of H are adjacent if and only if the solution in G corresponding to u can be transformed into the solution corresponding to v by sliding a single token along the edge uv ∈ E(G). See [7] for a survey on reconfiguration of colourings and dominating sets in graphs.

We use the standard notation of α(G) for the independence number of a graph G. The independent domination number i(G) of G is the minimum cardinality of a maximal independent set of G, or, equivalently, the minimum cardinality of an independent domination set of G. An independent dominating set of G of cardinality i(G) is also called an i-set of G, or an i(G)-set. An α-set of G, or an α(G)-set, is defined similarly. When i(G) = α(G), we say that G is well-covered.

Given a graph G, we consider the slide graph ℐ (G) of G, formally defined in Section 2 below, with respect to its i-sets. Our main result, Theorem 5.3, concerns the class Θ of “theta graphs” for which we characterize, in Sections 5 and 6, those graphs H ∈ Θ for which there exists a graph G such that H ≅ ℐ (G). We state known results required here in Section 3. We introduce the technique we use for theta graphs in Section 4, where we apply it to the simpler problem of characterizing line graphs and claw-free graphs that are realizable as i-graphs. In Section 7.1 we exhibit a graph that is neither a theta graph nor an i-graph, and in Section 7.2 we show that certain planar graphs are i-graphs and α-graphs. We conclude with some open problems in Section 8.

In general, we follow the notation of [3]. For other domination principles and terminology, see [4, 5].

The i-graph of a graph G, denoted ℐ (G) = (V (ℐ (G)), E(ℐ (G))), is the graph with vertices representing the minimum independent dominating sets of G (that is, the i-sets of G), and where u, v ∈ V (ℐ (G)), corresponding to the i(G)-sets S_u and S_v, respectively, are adjacent in ℐ (G) if and only if there exists xy ∈ E(G) such that S_u = (S_v − x) ∪ {y}. Imagine that there is a token on each vertex of an i-set S of G. Then S is adjacent, in ℐ (G), to an i(G)-set S^′ if and only if a single token can slide along an edge of G to transform S into S^′. Similarly, the α-graph 𝒜 (G) of a graph G is the slide reconfiguration graph with vertices representing the α(G)-sets, and where adjacency is defined as for the i-graph. In Section 5 we present several constructions for i-graphs that are also constructions for α-graphs.

We say H is an i-graph, or is i-graph realizable, if there exists some graph G such that ℐ (G) ≅ H. Moreover, we refer to G as the seed graph of the i-graph H. Going forward, we mildly abuse notation to denote both the i-set X of G and its corresponding vertex in H as X, so that X ⊆ V (G) and X ∈ V (H).

In acknowledgment of the slide-action in i-graphs, given i-sets X = {x₁, x₂, . . . , x_k} and Y = {y₁, x₂, . . . x_k} of G with x₁y₁ ∈ E(G), we denote the adjacency of X and Y in ℐ (G) as X∼x1y1Y X\mathop \sim \limits^{{x_1}{y_1}} Y , where we imagine transforming the i-set X into Y by sliding the token at x₁ along an edge to y₁. When discussing several graphs, we use the notation X∼x1y1GY X\mathop \sim \limits^{x_1}{^{y_1}_G} Y to specify that the relationship is on G. More generally, we use x ∼ y to denote the adjacency of vertices x and y (and x ≁ y to denote non-adjacency); this is used in the context of both the seed graph and the target graph.

The study of i-graphs was initiated by Teshima in [9]. In [2], Brewster, Mynhardt and Teshima investigated i-graph realizability and proved some results concerning the adjacency of vertices in an i-graph and the structure of their associated i-sets in the seed graph. They presented the three smallest graphs that are not i-graphs: the diamond graph 𝔇 = K₄ − e, K_2,3 and the graph κ, which is K_2,3 with an edge subdivided. They showed that several graph classes, like trees and cycles, are i-graphs. They demonstrated that known i-graphs can be used to construct new i-graphs and applied these results to build other classes of i-graphs, such as block graphs, hypercubes, forests, cacti, and unicyclic graphs.

The diamond 𝔇, K_2,3, and κ are examples of theta graphs: graphs that are the union of three internally disjoint nontrivial paths with the same two distinct end vertices. The graph Θ 〈j, k, ℓ〉, where j ≤ k ≤ ℓ, is the theta graph with paths of lengths j, k, and ℓ. In this notation, the three non-i-graph realizable examples are 𝔇 ≅ Θ 〈1, 2, 2〉, K_2,3 ≅ Θ 〈2, 2, 2〉, and κ ≅ 〈2, 2, 3〉.

To begin, we state several useful observations and lemmas from [2, 9] about the structure of i-sets within given i-graphs. Given a set S ⊆ V (G) and a vertex v ∈ S, the private neighbourhood of v with respect to S is the set pn(v, S) = N[v] − N[S − {v}], and the external private neighbourhood of v with respect to S is the set epn(v, S) = pn(v, S) − {v}.

For some path X₁, X₂, . . . , X_k in H, at most one vertex of the i-set is changed at each step, and so X₁ and X_k differ on at most k − 1 vertices. This yields the following immediate observation.

Combining the results from Lemma 3.3 with Observation 3.2 yields the following observation for vertices of i-graphs at distance 2.

Lemma 3.3 and Observation 3.2 are also used to prove the next result.

Figure 1.

Reconfiguration structure of an induced C₄ subgraph from Proposition 3.6

We state the above-mentioned results regarding 𝔇, K_2,3, and κ here for referencing.

On the other hand, the house graph ℋ = Θ 〈1, 2, 3〉 in Figure 2(b) is a theta graph that is an i-graph, as illustrated by the seed graph G in Figure 2(a). The i-sets of G and their adjacencies are overlaid on ℋ in Figure 2(b).

Figure 2.

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

The next result shows that maximal cliques in i-graphs can be replaced by arbitrarily larger maximal cliques to form larger i-graphs.

The Deletion Lemma below shows that the class of i-graphs is closed under vertex deletion, that is, every induced subgraph of an i-graph is also an i-graph.

When visualizing the connections between the i-sets of a graph G, it is sometimes advantageous to consider its complement G̅ instead. From a human perspective, it is curiously easier see to which vertices a vertex v is adjacent, rather than to which vertices v is nonadjacent. This is especially true when i(G) = 2 or 3, when we may interpret the adjacency of i-sets of G as the adjacencies of edges and triangles (i.e. K₃), respectively, in G̅. In the following sections we examine how the use of graph complements can be exploited to construct the i-graph seeds for certain classes of line graphs, theta graphs, and maximal planar graphs.

Consider a graph G with i(G) = 2 and where X = {u, v} is an i-set of G. In G̅, u and v are adjacent, so X is represented as the edge uv. Moreover, no other vertex w is adjacent to both vertices of X in G̅; otherwise, {u, v, w} is independent in G, contrary to X being an i-set.

Now consider the line graph L(G̅) of G̅. If X = {u, v} is an i-set of G, then e = uv is an edge of G̅ and hence e is a vertex of L(G̅). Thus, the i-sets of G correspond to a subset of the vertices of L(G̅). In the case where G̅ is triangle-free (that is, G has no independent sets of cardinality 3), these i-sets of G are exactly the vertices of L(G̅). Now suppose Y is an i-set of G adjacent to X; say, X∼uwY X\mathop \sim \limits^{uw} Y , so that Y = {v, w}. Then, in G̅, f = vw is an edge, and so in L(G̅), f ∈ V (L(G̅)). Since e and f are both incident with v in G̅, ef ∈ E(L(G̅)). That is, for i-sets X and Y of a well-covered graph G with i(G) = α(G) = 2, X ∼ Y if and only if X and Y correspond to adjacent vertices in L(G̅). Thus ℐ (G) ≅ L(G̅).

In the example illustrated in Figure 3 below, ℋ is the house graph, where X = {a, c} and Y = {c, e} are i-sets with X∼aeY X\mathop \sim \limits^{ae} Y . In Lℋ¯ L({\overline {\cal {H}}} ) , the two vertices in each of these i-sets are likewise adjacent.

Figure 3.

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

The connection between graphs with i(G) = 2 and line graphs helps us not only understand the structure of ℐ (G), but also lends itself towards some interesting realizability results. We follow this thread for the remainder of this section, and build towards determining the i-graph realizability of line graphs and claw-free graphs. The straightforward proof of the following lemma can be found in [9] and is omitted here.

Figure 4.

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

Finally, if we examine Beineke’s forbidden subgraph characterization of line graphs (see [1] or [3, Theorem 6.26]), we note that eight of the nine minimal non-line graphs contain an induced 𝔇 and are therefore not i-graphs. The ninth minimal non-line graph is the claw, K_1,3. Thus, 𝔇-free claw-free graphs are 𝔇-free line graphs, hence i-graphs.

While Theorem 4.2 and Corollary 4.3 reveal the i-graph realizability of many famous graph families (including another construction for cycles, which are connected, claw-free, and 𝔇-free), the realizability problem for graphs containing claws remains unresolved. Moreover, among clawed graphs are the theta graphs which we first alluded to in Section 2 as containing three of the small known non-i-graphs. In the next section we apply similar techniques with graph complements to construct all theta graphs that are i-graphs.

Consider a graph G with i(G) = 3. Each i-set of G is represented as a triangle (a K₃) in G̅. If X and Y are two i-sets of G with X∼uvY X\mathop \sim \limits^{uv} Y , then G̅[X] and G̅[Y] are triangles in G̅, and have |X ∩ Y| = 2. Although it is technically the induced subgraphs G̅[X] and G̅[Y ] that are the triangles of G̅, for notational simplicity we refer to X and Y as triangles. In G̅, the triangle X can be transformed into the triangle Y by removing the vertex u and adding in the vertex v (where u≁G¯v u{ \nsim _{\bar G}}v ). Thus, we say that two triangles are adjacent if they share exactly one edge. Moreover, since two i-sets of a graph G with i(G) = 3 are adjacent if and only if their associated triangles in G̅ are adjacent, we use the same notation for i-set adjacency in G as triangle adjacency in G̅; that is, the notation X ∼ Y represents both i-sets X and Y of G being adjacent, and triangles X and Y of G̅ being adjacent.

In the following sections we use triangle adjacency to construct complement seed graphs for the i-graphs that are theta graphs; that is, a graph G̅ such that ℐ (G) is isomorphic to some desired theta graph. Before proceeding with these constructions, we note some observations which will help us with this process.

If G̅ has an edge uv that does not lie on a triangle, then {u, v} is independent and dominating in G, and so i(G) ≤ 2. When building our seed graphs G with i(G) = 3, it is therefore necessary to ensure that every edge of the complement G̅ belongs to a triangle.

Suppose that S = {u, v, w, x} is such a clique of G̅. Then, for example, x is undominated by {u, v, w} in G, and so {u, v, w} is not an i-set of G. Conversely, suppose that {u, v, w} is a triangle in a graph G̅ with i(G) = 3. By attaching a new vertex x to all of {u, v, w} in G̅, we remove {u, v, w} as an i-set of G, while keeping all other i-sets of G. This observation proves to be very useful in the constructions in the following section: we now have a technique to eliminate any unwanted triangles in G̅ (and hence i-sets of G) that may arise. Note that this technique is an application of the Deletion Lemma (Lemma 3.10) in G̅ instead of in G.

The use of triangle adjacency in a graph G̅ to determine i-set adjacency in G provides a key technique to resolve the question of which theta graphs are i-graphs. In our main result, Theorem 5.3, we show that all theta graphs except the seven listed exceptions are i-graphs. Using this method of complement triangles, the proofs of the lemmas for the affirmative cases make up most of the remainder of Section 5. The proofs of the lemmas for the seven negative cases are given in Section 6.

Table 1 summarizes the cases used to establish Theorem 5.3 and their associated results.

5.1.

Θ 〈1, k, ℓ〉

We have already seen that the house graph ℋ = Θ 〈1, 2, 3〉 is an i-graph (Proposition 3.8). We can further exploit previous results to see that all graphs Θ 〈1, 2, ℓ〉 for ℓ ≥ 3 are i-graphs by taking a cycle C_n with n ≥ 4, and replacing one of its maximal cliques (i.e. an edge) with a K₃. By the Max Clique Replacement Lemma (Lemma 3.9), the resultant Θ 〈1, 2, n − 1〉 is also an i-graph. For reference, we explicitly state this result as a lemma.

Lemma 5.4.

For ℓ ≥ 3, the theta graph Θ 〈1, 2, ℓ〉 is an i-graph.

5.1.1.

Construction of G̅ for Θ 〈1, k, ℓ〉, 3 ≤ k ≤ ℓ.

In Figure 5 below, we provide a first example of the technique we employ repeatedly throughout this section to construct our theta graphs. To the left is a graph G̅, where each of its nine triangles corresponds to an i-set of its complement G. The resultant i-graph of G, ℐ (G) = Θ 〈1, 4, 5〉, is presented on the right. For consistency, we use X and Y to denote the triangles corresponding to the degree 3 vertices in the theta graphs in this example, as well as all constructions to follow.

Figure 5.

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

We proceed now to the general construction of a graph G̅ with ℐ (G) = Θ 〈1, k, ℓ〉 for 3 ≤ k ≤ ℓ. As it is our first construction using this triangle technique, we provide the construction and proof for Lemma 5.6 with an abundance of detail.

Construction 5.5 (See Figure 6).

Let H̅ ≅ W_k+2 = C_k+1 ∨ K₁, where C_k+1 = (w₁, . . . , w_k+1, w₁) and w₀ is the central hub, i.e., the vertex with degree k + 1. Add a path P_ℓ−2 : (v₁, . . . , v_ℓ−2), joining each v_i, i = 1, ..., ℓ − 2, to w₂. Join v₁ to w₁ and v_ℓ−2 to w₃. (If ℓ = 3, then v₁ = v_ℓ−2, hence v₁ is adjacent to w₁, w₂ and w₃.) This is the (planar) graph G̅.

Figure 6.

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

Lemma 5.6.

If G̅ is the graph constructed by Construction 5.5, then ℐ (G) = 𝒜 (G) = Θ 〈1, k, ℓ〉, 3 ≤ k ≤ ℓ.

Proof

To begin, notice that since in G̅, the vertices 𝒲 = {w₀, w₁, . . . , w_k, w_k+1} form a wheel on at least five vertices, H̅ ≆ K₄. Likewise, the graph induced by {w₀, w₁, w₂, w₃, v₁, v₂, . . . , v_ℓ−2} in G̅ is also a wheel on ℓ + 2 vertices, where w₂ is the central hub, and so it too contains no K₄. Therefore, G̅ is K₄-free and the triangles of G̅ are precisely the maximal cliques of G̅, and so ω(G̅) = i(G) = α(G) = 3. Since the i-sets of G are identical to its α-sets, ℐ (G) = 𝒜 (G), and so for ease of notation, we will refer only to ℐ (G) throughout the remainder of this proof.

We label the triangles as in Figure 6 by dividing them into two collections. The first are the triangles composed only of the vertices from 𝒲 and each containing w₀: let X = {w₀, w₁, w₂}, Y = {w₀, w₂, w₃}, A₁ = {w₀, w_k+1, w₁}, A₂ = {w₀, w_k, w_k+1}, . . . , A_k−2 = {w₀, w₄, w₅}, A_k−1 = {w₀, w₃, w₄}. The remainder are the triangles with vertex sets not fully contained in H̅: B₁ = {w₂, w₁, v₁}, B₂ = {w₂, v₁, v₂}, B₃ = {w₂, v₂, v₃}, . . . , B_ℓ−2 = {w₂, v_ℓ−3, v_ℓ−2}, and B_ℓ−1 = {w₂, v_ℓ−2, w₃}. We refer to these collections as 𝒮 = {X, Y }, 𝒜 = {A₁, A₂, . . . , A_k−1}, and ℬ = {B₁, B₂, . . . , B_ℓ−1}. It is clear from Figure 6 that these are the only triangles of G̅. Therefore V (ℐ (G)) = {X, Y, A₁, A₂, . . . , A_k−1, B₁, B₂, . . . , B_ℓ−1}.

We now show that the required adjacencies hold. From the construction of G̅, the following are immediate for ℐ (G): (i)

X∼w1w3Y X\mathop \sim \limits^{{w_1}{w_3}} Y ,

(ii)

X∼w0v1B1∼w1v2B2∼v1v3B3…Bℓ−2∼vℓ−3w3Bℓ−1∼vℓ−2w0Y X\mathop \sim \limits^{{w_0}{v_1}} {B_1}\mathop \sim \limits^{{w_1}{v_2}} {B_2}\mathop \sim \limits^{{v_1}{v_3}} {B_3} \ldots {B_{\ell - 2}}\mathop \sim \limits^{{v_\ell }{{_ - }_3}{w_3}} {B_{\ell - 1}}\mathop \sim \limits^{{v_{\ell - 2}}{w_0}} Y ,

(iii)

X∼w2wk+1A1∼w1wkA2…Ak−2∼w5w3Ak−1∼w4w2Y X\mathop \sim \limits^{{w_2}{w_k}_{ + 1}} {A_1}\mathop \sim \limits^{{w_1}{w_k}} {A_2} \ldots {A_{k - 2}}\mathop \sim \limits^{{w_5}{w_3}} {A_{k - 1}}\mathop \sim \limits^{{w_4}{w_2}} Y .

Hence, we need only show that there are no additional unwanted edges generated in the construction of ℐ (G).

Since G̅ is a planar graph and all of its triangles are facial (that is, the edges of the K₃ form a face in the plane embedding in Figure 6), each triangle is adjacent to at most three others. From (i)–(iiit287) above, triangles X and Y are both adjacent to the maximum three (and hence deg_{ℐ (G)}(X) = deg_{ℐ (G)}(Y) = 3).

Recall that to be adjacent, two triangles share exactly two vertices. Notice that the triangles of 𝒜 are composed entirely of vertices from 𝒲 − {w₂}, and that for 2 ≤ i ≤ ℓ − 2, B_i ∩ 𝒲 = {w₂}; furthermore, B₁ ∩ 𝒲 = {w₁, w₂} and B_ℓ−2 ∩ 𝒲 = {w₂, w₃}. Therefore no triangle of ℬ is adjacent to any triangle of 𝒜. It is similarly easy to see that there are no additional unwanted adjacencies between two triangles of 𝒜 or two triangles of ℬ.

We conclude that the graph G̅ generated by Construction 5.5 yields ℐ (G) = 𝒜 (G) = Θ 〈1, k, ℓ〉.

Before we proceed with the remainder of the theta graph constructions, let us return to Figure 6 to notice the prominence of the wheel subgraph in the complement seed graph G̅. In the constructions throughout this paper, this wheel subgraph will appear repeatedly; indeed, all of the complement seed graphs for the i-graphs of theta graphs have a similar basic form: begin with a wheel, add a path of some length, and then add some collection of edges between them. As stated without proof in Lemma 5.7, Figure 7 below demonstrates that a wheel in a triangle-based complement seed graph G̅ corresponds to a cycle in the i-graph of G. Using this result, in our later constructions with a wheel subgraph, we already have two of the three paths of a theta graph formed. Hence, we need only confirm that whatever unique additions are present in a given construction form the third path in the i-graph.

Figure 7.

The wheel H_k = W_k+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

Lemma 5.7.

For k ≥ 4, let H_k be the wheel W_k+1 = C_k ∨ K₁. Then ℐHk¯≅𝒜Hk¯≅Ck {\cal {I}}\left( {\overline {{H_k}} } \right) \cong {\cal {A}}\left( {\overline {{H_k}} } \right) \cong {C_k} .

We note the following analogous – although less frequently applied – result for fans of the form K₁ + P_k, as illustrated in Figure 8.

Lemma 5.8.

For k ≥ 2, let H_k be the k-fan K₁ ∨ P_k. Then ℐHk¯≅𝒜Hk¯≅Pk−1 {\cal {I}}\left( {\overline {{H_k}} } \right) \cong {\cal {A}}\left( {\overline {{H_k}} } \right) \cong {P_{k - 1}} .

Figure 8.

The fan H_k = K₁ ∨ P_k, 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

5.2.

Θ 〈2, k, ℓ〉 for 2 ≤ k ≤ ℓ

5.2.1.

Construction of G̅ for Θ 〈2, 2, ℓ〉, ℓ ≥ 5

As stated in Proposition 3.7, K_2,3 ≅ Θ 〈2, 2, 2〉 and κ ≅ Θ 〈2, 2, 3〉 are not i-graphs. Extending these results, we find that the length of the third path in Θ 〈2, 2, ℓ〉 has a transition point between ℓ = 4 and ℓ = 5; while ℓ = 4 is still too short to form an i-graph (see Lemma 6.1), for ℓ ≥ 5, Θ 〈2, 2, ℓ〉 is i-graph realizable.

Construction 5.9.

See Figures 9 and 10. Begin with the graph H̅ ≅ W₅ = C₄ ∨ K₁, labelling the degree 3 vertices as w₁, w₂, w₃, w₄ and the central degree 4 vertex as w₀. (a)

If ℓ ≥ 6 (as in Figure 9), attach to H̅ a path P_ℓ−3 : (v₁, v₂, . . . , v_ℓ−3) by joining w₁ to v₁, v₂, . . . , v_ℓ−4. Join v_ℓ−5 to v_ℓ−3. Next, join w₂ to v₁, and w₃ to v_ℓ−3. Then, join w₄ to v_ℓ−4 and v_ℓ−3. Add a new vertex z, joined to w₁, w₄, and v_ℓ−4.

(b)

If ℓ = 5 (as in Figure 10), attach to H̅ a path of P₂ : (v₁, v₂), by joining w₁ to v₁, and w₂ to v₁ and v₂. Then join w₃ to v₂, and w₄ to both v₁ and v₂. Add two new vertices, z₁ and z₂, joining z₁ to v₁, w₁, and w₄, and z₂ to v₂, w₂ and w₃.

We label the resultant (planar) graph G̅.

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

As with our other constructions, the triangles of G̅ are its smallest maximal cliques, and so i(G) = 3. However, we now employ a technique of adding vertices to create K₄’s in G̅ and eliminate any “unwanted” triangles that might arise in our construction. In (b), the addition of z₁ and z₂ eliminate triangles {w₁, w₄, v₁} and {w₂, w₃, v₂}, respectively. Similarly, in (a), z prevents {w₁, w₄, v_ℓ−3} from being a maximal clique of G̅ and hence an i-set of G. The unfortunate trade-off in this triangle-elimination technique is that the remaining triangles are no longer α-sets; the constructions work only for i-graphs, not α-graphs.

Lemma 5.10.

If G̅ is the graph constructed by Construction 5.9, then ℐ (G) = Θ 〈2, 2, ℓ〉, for ℓ ≥ 5.

Proof

We only prove the lemma for case where ℓ ≥ 6; the single case where ℓ = 5 is adequately illustrated in Figure 10 and details can be found in [9].

As in the previous constructions, since each edge of G̅ belongs to a triangle and some triangles are not contained in K₄’s, these triangles of G̅ form the smallest maximal cliques of G̅. We label these triangles as in Figure 9; in particular, X=w0, w1, w2,Y=w0, w3, w4,A=w0, w2, w3,B=w0, w1, w4,D1=w1, w2, v1,Di=w1, vi−1, vi for 2≤i≤ℓ−4,Dℓ−3=vℓ−5, vℓ−4, vℓ−3,Dℓ−2=w4, vℓ−4, vℓ−3,Dℓ−1=w3, w4, vℓ−3. \matrix{ \hfill X & = \hfill & {\left\{ {{w_0},\;{w_1},\;{w_2}} \right\},} \hfill \cr \hfill Y & = \hfill & {\left\{ {{w_0},\;{w_3},\;{w_4}} \right\},} \hfill \cr \hfill A & = \hfill & {\left\{ {{w_0},\;{w_2},\;{w_3}} \right\},} \hfill \cr \hfill B & = \hfill & {\left\{ {{w_0},\;{w_1},\;{w_4}} \right\},} \hfill \cr \hfill {{D_1}} & = \hfill & {\left\{ {{w_1},\;{w_2},\;{v_1}} \right\},} \hfill \cr \hfill {{D_i}} & = \hfill & {\left\{ {{w_1},\;{v_{i - 1}},\;{v_i}} \right\}\;\;\;\;{\rm{for}}\;2 \le i \le \ell - 4,} \hfill \cr \hfill {{D_{\ell - 3}}} & = \hfill & {\left\{ {{v_{\ell - 5}},\;{v_{\ell - 4}},\;{v_{\ell - 3}}} \right\},} \hfill \cr \hfill {{D_{\ell - 2}}} & = \hfill & {\left\{ {{w_4},\;{v_{\ell - 4}},\;{v_{\ell - 3}}} \right\},} \hfill \cr \hfill {{D_{\ell - 1}}} & = \hfill & {\left\{ {{w_3},\;{w_4},\;{v_{\ell - 3}}} \right\}.} \hfill \cr }

It is straightforward to verify that these ℓ+3 sets are precisely the maximal cliques of G̅ of order 3 and, hence, the i-sets of G. Therefore they form the vertex set of ℐ (G). Moving to the edges of ℐ (G), the following adjacencies are clear from Figure 9: (i)

X∼w1w3A∼w2w4Y X\mathop \sim \limits^{{w_1}{w_3}} A\mathop \sim \limits^{{w_2}{w_4}} Y ,

(ii)

X∼w2w4B∼w1w3Y X\mathop \sim \limits^{{w_2}{w_4}} B\mathop \sim \limits^{{w_1}{w_3}} Y ,

(iii)

X∼w0v1D1∼w2v2D2∼v1v3D3…Dℓ−3∼w1vℓ−2Dℓ−2∼vℓ−4w4Dℓ−1∼vℓ−2w0Y X\mathop \sim \limits^{{w_0}{v_1}} {D_1}\mathop \sim \limits^{{w_2}{v_2}} {D_2}\mathop \sim \limits^{{v_1}{v_3}} {D_3} \ldots {D_{\ell - 3}}\mathop \sim \limits^{{w_1}{v_{\ell - }}_2} {D_{\ell - 2}}\mathop \sim \limits^{{v_{\ell - 4}}{w_4}} {D_{\ell - 1}}\mathop \sim \limits^{{v_{\ell - 2}}{w_0}} Y .

As for its vertex set, it is straightforward to verify that the edge set of ℐ (G) consists of precisely the edges listed in (i)–(iii). We conclude that ℐ (G) = Θ 〈2, 2, ℓ〉.

5.2.2.

Construction of G̅ for Θ 〈2, 3, ℓ〉 for ℓ ≥ 5

For many of the results going forward, we apply small modifications to previous constructions. In the first of these, we begin with the graphs from Construction 5.9, which were used to find i-graphs for Θ 〈2, 2, 5〉 and Θ 〈2, 2, ℓ〉 for ℓ ≥ 6, and expand the central wheel used in there to build i-graphs for Θ 〈2, 3, 5〉 and Θ 〈2, 3, ℓ〉 for ℓ ≥ 6.

Construction 5.11.

Refer to Figures 11 and 12. (a)

If ℓ ≥ 6, begin with a copy of the graph G̅ from Construction 5.9. Subdivide the edge w₁w₄, adding the new vertex w₅. Join w₅ to w₀, so that w₀, w₁, . . . , w₅ forms a wheel. Delete the vertex z.

(b)

If ℓ = 5, begin with a copy of the graph G̅ from Construction 5.9. Subdivide the edge w₁w₄, adding the new vertex w₅. Join w₅ to w₀, so that w₀, w₁, . . . , w₅ forms a wheel. Delete the vertex z₁.

We rename the resultant (planar) graph G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} for ℓ ≥ 5.

Figure 11.

The graph G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} from Construction 5.11 (a) such that ℐ (G_{2,3, ℓ}) = 𝒜 (G_{2,3, ℓ}) = Θ 〈2, 3, ℓ〉 for ℓ ≥ 6

Figure 12.

The graph G2,3,5¯ \overline {{G_{2,3,5}}} from Construction 5.11 (b) such that ℐ (G_2,3,5) = Θ 〈2, 3, 5〉, with ℐ (G_2,3,5) over-laid in red

In Construction 5.11 (a), notice that the vertex z is deleted from G̅. In the original Construction 5.9 for a graph G̅ with ℐ (G) = Θ 〈2, 2, ℓ〉 for ℓ ≥ 6, z served to eliminate the unwanted triangle formed by {w₁, w₄, v_ℓ−4}. Now with the expanded wheel including w₅, {w₁, w₄, v_ℓ−4} is not a triangle in G2,3,ℓ¯ℓ≥6 \overline {{G_{2,3,\ell }}} \left( {\ell \ge 6} \right) , and z is not needed. Indeed, as G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} now has α(G_{2,3, ℓ}) = 3, its triangles are also α-sets in G, and so we can immediately extend the construction from i-graphs to α-graphs.

The extension, however, does not apply to Construction 5.11 (b) for the graph G2,3,5¯ \overline {{G_{2,3,5}}} . Here, we no longer require z₁ (which served to eliminate the unwanted triangle formed by {w₁, w₄, v₁}), but z₂ remains and forms the clique {w₂, w₃, z₂, v₂}; thus, α(G_2,3,5) = 4.

The proof for the following Lemma 5.12 is otherwise very similar to the proof of Lemma 5.10, and so is omitted.

Lemma 5.12.

If G2,3,5¯ \overline {{G_{2,3,5}}} is the graph constructed in Construction 5.11 (b), then ℐ (G_2,3,5) = Θ 〈2, 3, 5〉. For ℓ ≥ 6, if G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} is the graph constructed in Construction 5.11 (a), then ℐ (G_{2,3, ℓ}) = 𝒜 (G_{2,3, ℓ}) = Θ 〈2, 3, ℓ〉 for ℓ ≥ 6.

5.2.3.

Construction of G̅ for Θ 〈2, 4, 4〉

In the following construction for a graph G̅ with ℐ (G) = Θ 〈2, 4, 4〉, we again apply the technique of adding vertices to eliminate unwanted triangles.

Figure 13.

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

Construction 5.13.

Refer to Figure 13. Begin with a copy of the graph H̅ ≅ W₇ = C₆ ∨ K₁, labelling the degree 3 vertices as w₁, w₂, . . . , w₆ and the central degree 6 vertex as w₀. Join w₁ to w₄. Add a new vertex v to H̅, joining v to w₁, . . . , w₄. Then, add the new vertex z, joined to v, w₂ and w₃, and the new vertex z′, joined to w₀, w₁, and w₄. We label the resultant (non-planar) graph G̅.

Lemma 5.14.

If G̅ is the graph constructed by Construction 5.13, then ℐ (G) = Θ 〈2, 4, 4〉.

Proof

As shown in Figure 13, the triangles of G̅ forming maximal cliques of G̅, and therefore the i-sets of G, are labelled them as follows: X=w0,w1,w2,B1=w0,w1,w6,D1=w1, w2, v,Y=w0,w3,w4,B2=w0,w5,w6D2=w1, w4, v,A=w0,w2,w3,B3=w0,w4,w5,D3=w3, w4, v. \matrix{ {X = \left\{ {{w_0},{w_1},{w_2}} \right\},} \hfill & {{B_1} = \left\{ {{w_0},{w_1},{w_6}} \right\},} \hfill & {{D_1} = \left\{ {{w_1},\;{w_2},\;v} \right\},} \hfill \cr {Y = \left\{ {{w_0},{w_3},{w_4}} \right\},} \hfill & {{B_2} = \left\{ {{w_0},{w_5},{w_6}} \right\}} \hfill & {{D_2} = \left\{ {{w_1},\;{w_4},\;v} \right\},} \hfill \cr {A = \left\{ {{w_0},{w_2},{w_3}} \right\},} \hfill & {{B_3} = \left\{ {{w_0},{w_4},{w_5}} \right\},} \hfill & {{D_3} = \left\{ {{w_3},\;{w_4},\;v} \right\}.} \hfill \cr }

Similarly to the construction for Θ 〈2, 2, 5〉 in the proof of Lemma 5.10, the vertices z and z′ are added to ensure that {v, w₂, w₃} and {w₀, w₁, w₄}, respectively, are not maximal cliques in G̅, and hence are not i-sets of G.

It can be seen that there are no other triangles in G̅ beyond the nine listed above; we omit the details, which can be found in [9, Lemma 5.19].

From Figure 13, the following triangle adjacencies are immediate: (i)

X∼w1w3A∼w2w4Y X\mathop \sim \limits^{{w_1}{w_3}} A\mathop \sim \limits^{{w_2}{w_4}} Y ,

(ii)

X∼w2w6B1∼w1w5B2∼w6w4B3∼w5w3Y X\mathop \sim \limits^{{w_2}{w_6}} {B_1}\mathop \sim \limits^{{w_1}{w_5}} {B_2}\mathop \sim \limits^{{w_6}{w_4}} {B_3}\mathop \sim \limits^{{w_5}{w_3}} Y ,

(iii)

X∼w0vD1∼w2w4D2∼w1w3D3∼vw0Y X\mathop \sim \limits^{{w_0}v} {D_1}\mathop \sim \limits^{{w_2}{w_4}} {D_2}\mathop \sim \limits^{{w_1}{w_3}} {D_3}\mathop \sim \limits^{v{w_0}} Y .

It is again straightforward to verify that there are no additional edges in ℐ (G) than those listed above. We conclude that ℐ (G) = Θ 〈2, 4, 4〉 as required.

Notice that Construction 5.13 is our first theta graph construction that is not planar as it has a K_3,3 minor. Indeed, with the exception of the constructions that are based upon Construction 5.13, all of our i-graph constructions use planar complement seed graphs.

Problem 1.

(i)

Find a planar graph-complement construction for Θ 〈2, 4, 4〉.

(ii)

Do all i-graphs with largest induced stars of K_1,3, always have a planar graph-complement construction?

A large target graph requires a large seed graph in order to generate a sufficient number of unique i-sets. Can a target graph become too dense to allow for a planar graph-complement construction?

Moving forward, we will no longer explicitly check that there are no additional unaccounted for triangles in our constructions. Should the construction indeed result in triangles of G̅ that produce extraneous vertices in ℐ (G), we can easily remove them using the Deletion Lemma (Lemma 3.10).

5.2.4.

Constructions of G̅ for Θ 〈2, 4, 5〉 and Θ 〈2, 5, 5〉

Construction 5.15.

Refer to Figure 14. (a)

Begin with a copy of the graph G2,3,5¯ \overline {{G_{2,3,5}}} from Construction 5.11 (b) for Θ 〈2, 3, 5〉. Subdivide the edge w₁w₅, adding the new vertex w₆. Join w₆ to w₀, so that w₀, w₁, . . . , w₆ forms a wheel. Call this graph G2,4,5¯ \overline {{G_{2,4,5}}} .

(b)

Begin with a copy of the graph G2,4,5¯ \overline {{G_{2,4,5}}} from Construction 5.15 (a). Subdivide the edge w₁w₆, adding the new vertex w₇. Join w₇ to w₀, so that w₀, w₁, . . . , w₇ forms a wheel. Call this graph G2,5,5¯ \overline {{G_{2,5,5}}} .

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.

Lemma 5.16.

If G2,k,5¯ \overline {{G_{2,k,5}}} is the graph constructed by Construction 5.15, then ℐ (G_2,k,5) = Θ 〈2, k, 5〉, for 4 ≤ k ≤ 5.

Lemma 5.16 follows readily from Figure 14 and we omit the proof.

5.2.5.

Construction of G̅ for Θ 〈2, k, ℓ〉 for ℓ ≥ k ≥ 4 and ℓ ≥ 6

Construction 5.17.

See Figure 15. Begin with a copy of the graph G2,3,ℓ¯ \overline {{G_{2,3,\ell }}} from Construction 5.11 (a) for ℓ ≥ 5. Subdivide the edge w₁w₅ k − 3 times (for k ≤ ℓ), adding the new vertices w₆, w₇, . . . , w_k+2. Join w₆, w₇, . . . , w_k+2 to w₀, so that w₀, w₁, . . . , w_k+2 forms a wheel. Call this graph G2,k,ℓ¯ \overline {{G_{2,k,\ell }}} .

Lemma 5.18.

If G2,k,ℓ¯ \overline {{G_{2,k,\ell }}} is the graph constructed by Construction 5.17, then ℐ (G_2,k,ℓ) = 𝒜 (G_2,k,ℓ) = Θ 〈2, k, ℓ〉, for ℓ ≥ k ≥ 4 and ℓ ≥ 6.

Lemma 5.18 follows from Figure 15.

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

5.3.

Θ 〈3, k, ℓ〉

In the rest of Section 5 we only give the constructions and their associated figures, and state the lemmas without proof. Details can be found in [9, Chapter 5].

5.3.1.

The graph G̅ for Θ 〈3, 3, 4〉

The triangles X, A₁, A₂, Y, B₂, B₁, D₁, D₂, D₃ in Figure 16, and the obvious paths formed by them, illustrate the following lemma.

Lemma 5.19.

Θ 〈3, 3, 4〉 is an i-graph.

Figure 16.

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

5.3.2.

Construction of G̅ for Θ 〈3, 3, 5〉

Construction 5.20.

Refer to Figure 17. Begin with a copy of the graph H̅ ≅ W₇ = C₆ ∨ K₁, labelling the degree 3 vertices as w₁, w₂, . . . , w₆ and the central degree 6 vertex as w₀. Add new vertices v₁ and v₂ to H̅, joined to each other. Then, join v₁ to each of {w₁, w₂, w₅}, and v₂ to each of {w₂, w₄, w₅}. Call this graph G3,3,5¯ \overline {{G_{3,3,5}}} .

Figure 17.

A graph G3,3,5¯ \overline {{G_{3,3,5}}} from Construction 5.20 such that ℐ (G_3,3,5) = Θ 〈3, 3, 5〉.

Lemma 5.21.

If G3,3,5¯ \overline {{G_{3,3,5}}} is the graph constructed by Construction 5.20, then ℐ (G_3,3,5) = 𝒜 (G_3,3,5) = Θ 〈3, 3, 5〉.

5.3.3.

Construction of G̅ for Θ 〈3, 3, ℓ〉 for ℓ ≥ 6

Construction 5.22.

Refer to Figure 19. Begin with a copy of the graph H̅ ≅ W₇ = C₆ ∨ K₁, labelling the degree 3 vertices as w₁, w₂, . . . , w₆ and the central degree 4 vertex as w₀. For ℓ ≥ 6, add to H̅ a new path of ℓ − 3 vertices labelled as v₁, v₂, . . . , v_ℓ−3. Then, join w₁ to each of {v₁, v₂, . . . , v_ℓ−4}, w₄ to v_ℓ−3, and w₅ to v_ℓ−4 and v_ℓ−3. Finally, join v_ℓ−5 to v_ℓ−3, so that {v_ℓ−5, v_ℓ−4, v_ℓ−3} form a K₃. Call this graph G3,3,ℓ¯ \overline {{G_{3,3,\ell }}} for ℓ ≥ 6.

Although the general construction still applies for the case when ℓ = 6, we include a separate figure for the construction of Θ 〈3, 3, 6〉 for reference below, because of the additional complication that now v₁ = v_ℓ−5, and so the single vertex now has dual roles in the construction.

Lemma 5.23.

If G3,3,ℓ¯ \overline {{G_{3,3,\ell }}} is the graph constructed by Construction 5.22, then ℐ (G_{3,3, ℓ}) = 𝒜 (G_{3,3, ℓ}) = Θ 〈3, 3, ℓ〉 for ℓ ≥ 6.

Figure 18.

The graph G3,3,6¯ \overline {{G_{3,3,6}}} from Construction 5.22 such that ℐ (G_3,3,6) = 𝒜 (G_3,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

5.3.4.

Construction of G̅ for Θ 〈3, 4, 4〉

Construction 5.24.

See Figure 20. Begin with a copy of the graph G̅ from Construction 5.13 for Θ 〈2, 4, 4〉, which we rename here as G2,4,4¯ \overline {{G_{2,4,4}}} . Subdivide the edge w₂w₃, adding a new vertex u₁, and joining u₁ to w₀. Delete the vertex z. Call this graph G3,4,4¯ \overline {{G_{3,4,4}}} .

Lemma 5.25.

If G3,4,4¯ \overline {{G_{3,4,4}}} is the graph constructed by Construction 5.24, then ℐ (G_3,4,4) = Θ 〈3, 4, 4〉.

Figure 20.

The graph G3,4,4¯ \overline {{G_{3,4,4}}} from Construction 5.24 such that ℐ (G_3,4,4) = Θ 〈3, 4, 4〉

5.3.5.

Construction of G̅ for Θ 〈3, 4, ℓ〉, ℓ ≥ 5

Construction 5.26.

Begin with a copy of the graph G3,4,4¯ \overline {{G_{3,4,4}}} from Construction 5.24 for Θ 〈3, 4, 4〉. Subdivide the edge w₁w₆ ℓ − 4 times (for ℓ ≥ 5), adding the new vertices w₇, w₈, . . . , w_ℓ+2. Join w₇, w₈, . . . , w_ℓ+2 to w₀, so that w₀, w₁, . . . , w_ℓ+2 forms a wheel. Call this graph G3,4,ℓ¯ \overline {{G_{3,4,\ell }}} .

Lemma 5.27.

If G3,4,ℓ¯ \overline {{G_{3,4,\ell }}} is the graph constructed by Construction 5.26, then ℐ (G_{3,4, ℓ}) = Θ 〈3, 4, ℓ〉 for ℓ ≥ 5.

5.3.6.

Construction of G̅ for Θ 〈3, 5, 5〉

Construction 5.28.

Refer to Figure 21. Begin with a copy of the graph G3,3,5¯ \overline {{G_{3,3,5}}} from Construction 5.20. Subdivide the edge w₁w₆ twice, adding the new vertices w₇ and w₈. Join w₇ and w₈ to w₀, so that w₀, w₁, . . . , w₈ forms a wheel. Call this graph G3,5,5¯ \overline {{G_{3,5,5}}} .

Figure 21.

A graph G3,5,5¯ \overline {{G_{3,5,5}}} from Construction 5.28 such that ℐ (G_3,5,5) = Θ 〈3, 5, 5〉.

Lemma 5.29.

If G3,5,5¯ \overline {{G_{3,5,5}}} is the graph constructed by Construction 5.28, then ℐ (G_3,5,5) = 𝒜 (G_3,5,5) = Θ 〈3, 5, 5〉.

Notice that subdividing only once in Construction 5.28 (adding only w₇ and not w₈) gives an alternative (planar) construction for Θ 〈3, 4, 5〉.

5.4.

Θ 〈j, k, ℓ〉 for 4 ≤ j ≤ k ≤ ℓ and 3 ≤ j ≤ k ≤ ℓ, ℓ ≥ 6

5.4.1.

Construction of G̅ for Θ 〈j, k, ℓ〉 for 4 ≤ j ≤ k ≤ ℓ ≥ 5

Construction 5.30.

Refer to Figure 22. Begin with a copy of the graph G3,4,4¯ \overline {{G_{3,4,4}}} from Construction 5.24. Subdivide the edge u₁w₃, adding the new vertex u₂. Join u₂ to w₀, so that w0,w1,w2,u1,u2,w3,…,w6 {w_0},{w_1},{w_2},{u_1},{u_2},{w_3}, \ldots ,{w_6} forms a wheel. Call this graph G4,4,4¯ \overline {{G_{4,4,4}}} .

Figure 22.

The graph G4,4,4¯ \overline {{G_{4,4,4}}} from Construction 5.30 such that ℐ (G_4,4,4) = Θ 〈4, 4, 4〉

Lemma 5.31.

If G4,4,4¯ \overline {{G_{4,4,4}}} is the graph constructed by Construction 5.30, then ℐ (G_4,4,4) = Θ 〈4, 4, 4〉.

Construction 5.32.

Begin with a copy of the graph G3,3,5¯ \overline {{G_{3,3,5}}} from Construction 5.20. For k = 4 subdivide the edge w₁w₆ once, adding the vertex w₇; for k = 5, subdivide a second time, adding the vertex w₈. For j = 4, subdivide the edge w₂w₃, adding the vertex u₁; for j = 5 (j ≤ k), subdivide a second time, adding the vertex u₂. Connect all new vertices to w₀ to form a wheel. Call this graph Gj,k,5¯ \overline {{G_{j,k,5}}} for 4 ≤ j ≤ k ≤ 5.

An example of the construction of G5,5,5¯ \overline {{G_{5,5,5}}} is given in Figure 23 below.

Figure 23.

A graph G5,5,5¯ \overline {{G_{5,5,5}}} from Construction 5.28 such that ℐ (G_5,5,5) = Θ 〈5, 5, 5〉

Lemma 5.33.

If Gj,k,5¯ \overline {{G_{j,k,5}}} is the graph constructed by Construction 5.32, then ℐ (G_j,k,5) = 𝒜 (G_j,k,5) = Θ 〈j, k, 5〉 for 4 ≤ j ≤ k ≤ 5.

5.4.2.

Construction of G̅ for Θ 〈j, k, ℓ〉 for 3 ≤ j ≤ k ≤ ℓ, ℓ ≥ 6

Construction 5.34.

Begin with a copy of the graph G3,3,ℓ¯ \overline {{G_{3,3,\ell }}} from Construction 5.22 for Θ 〈3, 5, ℓ〉 for ℓ ≥ 6. For 3 ≤ k ≤ ℓ, subdivide the edge w₁w₆ k − 3 times, adding the new vertices w₇, w₈, . . . , w_k+3. Join each of w₇, w₈, . . . , w_k+3 to w₀, so that w₀, w₁, . . . , w_k+3 forms a wheel. Then, for 3 ≤ j ≤ k, subdivide the edge w₂w₃ j − 3 times, adding the new vertices u₁, u₂, . . . , u_j−3. Again, join each of u₁, u₂, . . . , u_j−3 to w₀ to form a wheel. Call this graph Gj,k,ℓ¯ \overline {{G_{j,k,\ell }}} for 3 ≤ j ≤ k ≤ ℓ and ℓ ≥ 6.

Lemma 5.35.

If Gj,k,ℓ¯ \overline {{G_{j,k,\ell }}} for 3 ≤ j ≤ k ≤ ℓ and ℓ ≥ 6 is the graph constructed by Construction 5.34, then ℐ (G_{j, k, ℓ}) = 𝒜 (G_{j, k, ℓ}) = Θ 〈j, k, ℓ〉.

The lemmas above imply the sufficiency of Theorem 5.3: if a theta graph is not one of seven exceptions listed, then it is an i-graph. In the next section, we complete the proof by examining the exception cases.

Figure 24.

The graph Gj,k,ℓ¯ \overline {{G_{j,k,\ell }}} from Construction 5.34 such that ℐ (G_{j, k, ℓ}) = Θ 〈j, k, ℓ〉 for 3 ≤ j ≤ k ≤ ℓ and ℓ ≥ 6

In this section we show that Θ 〈2, 2, 4〉, Θ 〈2, 3, 3〉, Θ 〈2, 3, 4〉, and Θ 〈3, 3, 3〉 are not i-graphs; together with Proposition 3.7, this completes the proof of Theorem 5.3.

6.1.

Θ 〈2, 2, 4〉 is not an i-graph

Proposition 6.1.

The graph Θ 〈2, 2, 4〉 is not i-graph realizable.

Proof

Suppose to the contrary that Θ 〈2, 2, 4〉 is realizable as an i-graph, and that H = Θ 〈2, 2, 4〉 ≅ ℐ (G) for some graph G. Label the vertices of H as in Figure 25.

Figure 25.

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

From Proposition 3.6, the composition of the following i-sets of G are immediate: X=x1,x2,x3, …,xk,Y=y1,y2,x3, …,xk,A=y1,x2,x3, …,xk,B=x1,y2,x3, …,xk,C1=x1,x2,y3, …,xk, \matrix{ \hfill {X = \left\{ {{x_1},{x_2},{x_3},\; \ldots ,{x_k}} \right\},} & \hfill {Y = \left\{ {{y_1},{y_2},{x_3},\; \ldots ,{x_k}} \right\},} \cr \hfill {A = \left\{ {{y_1},{x_2},{x_3},\; \ldots ,{x_k}} \right\},} & \hfill {B = \left\{ {{x_1},{y_2},{x_3},\; \ldots ,{x_k}} \right\},} \cr \hfill {{C_1} = \left\{ {{x_1},{x_2},{y_3},\; \ldots ,{x_k}} \right\},} & \hfill {} \cr } where k ≥ 3 and y₁, y₂, y₃ are three distinct vertices in G − X. These sets are illustrated in blue in Figure 25. This leaves only the composition of C₂ and C₃ (in red) to be determined. As we construct C₂, notice first that y₃ ∈ C₂; otherwise, if say some other z ∈ C₂ so that C1∼y3zC2 C1\mathop \sim \limits^{{y_3}z} {C_2} , then X∼x3zC2 X\mathop \sim \limits^{{x_3}z} {C_2} , and XC₂ ∈ E(H). Thus, a token on one of {x₁, x₂, x₄, . . . , x_k} moves in the transition from C₁ to C₂. We consider three cases.

Case 1: The token on x₁ moves. If C1∼x1zC2 {C_1}\mathop \sim \limits^{{x_1}z} {C_2} for some z ∉ {y₁, y₂}, then |C₂ ∩ Y| = 3, contradicting the distance requirement between i-sets from Observation 3.2. Moreover, from the composition of B, x₁ ≁ y₂, and so C1∼x1y1C2 {C_1}\mathop \sim \limits^{{x_1}{y_1}} {C_2} , so that C₂ = {y₁, x₂, y₃, . . . , x_k}. However, since x₃ ∼ y₃, we have that A∼x3y3C2 A\mathop \sim \limits^{{x_3}{y_3}} {C_2} , so that AC₂ ∈ E(G), a contradiction.

Case 2: The token on x₂ moves. An argument similar to Case 1 constructs C₂ = {x₁, y₂, y₃, . . . , x_k}, with B∼x3y3C2 B\mathop \sim \limits^{{x_3}{y_3}} {C_2} , resulting in the contradiction BC₂ ∈ E(G).

Case 3: The token on x_i for some i ∈ {4, 5, . . . , k} moves. From the compositions of X and Y, x_i is not adjacent to any of {x₃, y₁, y₂}, so the token at x_i moves to some other vertex, say z, so that C1∼xizC2 {C_1}\mathop \sim \limits^{{x_i}z} {C_2} and {x₁, x₂, y₃, z} ⊆ C₂. This again contradicts the distance requirement of Observation 3.2 as |C₂ ∩ Y| = 4.

In all cases, we fail to construct a graph G with ℐ (G) ≅ Θ 〈2, 2, 4〉 and so conclude that no such graph exists.

6.2.

Θ 〈2, 3, 3〉 is not an i-Graph

Proposition 6.2.

The graph Θ 〈2, 3, 3〉 is not i-graph realizable.

Proof

To begin, we proceed similarly to the proof of Proposition 6.1: suppose to the contrary that Θ 〈2, 3, 3〉 is realizable as an i-graph, and that H = Θ 〈2, 3, 3〉 ≅ ℐ (G) for some graph G. Label the vertices of H as in Figure 26. As before, the corresponding i-sets in blue are established from previous results, and those in red are yet to be determined. Moreover, from the composition of these four blue i-sets, we observe that for each i ∈ {1, 2, 3}, x_i ∼ y_j if and only if i = j.

Figure 26.

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

Unlike the construction for Θ 〈2, 2, 4〉, we no longer start with knowledge of the exact composition of Y. We proceed with a series of observations on the contents of the various i-sets: (i)

y₁ ∈ Y, y₂ ∈ B₂, and y₃ ∈ C₂ by three applications of Proposition 3.6.

(ii)

y₁ ∉ B₂ and y₁ ∉ C₂. If y₁ ∈ B₂, then B1∼x1y1B2 {B_1}\mathop \sim \limits^{{x_1}{y_1}} {B_2} (because A shows that y₁ is not adjacent to x₃, . . . , x_k) so that B₂ = {y₁, y₂, x₃, . . . , x_k}, and therefore A∼x2y2B2 A\mathop \sim \limits^{{x_2}{y_2}} {B_2} , which is impossible. Similarly, if y₁ ∈ C₂, then A∼x3y3C2 A\mathop \sim \limits^{{x_3}{y_3}} {C_2} , which is also impossible.

(iii)

y₃ ∉ B₂. Otherwise, B₂ = {x₁, y₂, y₃, x₄, . . . , x_k} and so C1∼x2y2B2 {C_1}\mathop \sim \limits^{{x_2}{y_2}} {B_2} .

(iv)

y₂ ∉ Y and y₃ ∉ Y. If y₂ ∈ Y, then Y = {y₁, y₂, x₃, . . . , x_k} and so B1∼x1y1Y {B_1}\mathop \sim \limits^{{x_1}{y_1}} Y . Likewise, if y₃ ∈ Y then C1∼x1y1Y {C_1}\mathop \sim \limits^{{x_1}{y_1}} Y .

From (i) and (ii), y₁ ∈ Y but y₁ ∉ B₂, and similarly from (iv) y₂ ∈ B₂ but y₂ ∉ Y ; therefore, B2∼y2y1Y {B_2}\mathop \sim \limits^{{y_2}{y_1}} Y . Now, since x₁ ∼ y₁, and y₁ ∈ Y, we have that x₁ ∉ Y. Thus, if x₁ were in B₂, its token would move in the transition from B₂ to Y. However, we have already established that it is the token at y₂ that moves, and so x₁ ∉ B₂. We conclude that B1∼x1zB2 {B_1}\mathop \sim \limits^{{x_1}z} {B_2} for some z ∉ {y₁, y₃}, so that B₂ = {z, y₂, x₃, . . . , x_k}. Notice that since B₂ is independent, and x₂ ∼ y₂, it follows that z ≠ x₂.

Using similar arguments, we determine that C2∼y3y1Y {C_2}\mathop \sim \limits^{{y_3}{y_1}} Y , and that C1∼x1wC2 {C_1}\mathop \sim \limits^{{x_1}w} {C_2} for some w ∉ {y₁, y₂, x₁}. Moreover, C₂ = {w, x₂, y₃, x₄, . . . , x_k}. Again, note that since x₃ ∼ y₃, w ≠ x₃.

From B2∼y2y1Y {B_2}\mathop \sim \limits^{{y_2}{y_1}} Y , we have that Y = {y₁, z, x₃, x₄ . . . , x_k}. However, from C2∼y3y1Y {C_2}\mathop \sim \limits^{{y_3}{y_1}} Y , we also have that Y = {y₁, x₂, w, x₄, . . . , x_k}. As we have already established that z ≠ x₂ and w ≠ x₃, we arrive at two contradicting compositions of Y. Thus, no such graph G exists, and we conclude that Θ 〈2, 3, 3〉 is not an i-graph.

6.3.

Θ 〈2, 3, 4〉 is not an i-Graph

Proposition 6.3.

The graph Θ 〈2, 3, 4〉 is not i-graph realizable.

Proof

The construction for our contradiction begins similarly to that of Θ 〈2, 3, 3〉 in Proposition 6.2. As before, we illustrate the graph in Figure 27, labelling the known sets in blue, and those yet to be determined in red. Given the similarity of Θ 〈2, 3, 3〉 and Θ 〈2, 3, 4〉, many of the observations from Proposition 6.2 carry through to our current proof. In particular, all of (i)–(iv) hold here, including that y₁ ∉ C₂ from (ii). Moreover, the compositions of Y and B₂ also hold, where z is some vertex with z ∉ {y₁, x₂, y₂}.

Figure 27.

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

We now attempt to build C₂. From Proposition 3.6, since X ≁ C₂, y₃ ∈ C₂ (and x₃ ∉ C₂). From the distance requirement of Observation 3.2, |X − C₂| ≤ 2, and so at least one of x₁ or x₂ is in C₂. Recall from the construction for Proposition 6.2 that A∼x2zY A\mathop \sim \limits^{{x_2}z} Y and B1∼x1zB2 {B_1}\mathop \sim \limits^{{x_1}z} {B_2} , and so z is adjacent to both x₁ and x₂. Hence, z ∉ C₂.

Gathering these results shows that none of {x₃, z, y₁} are in C₂, and thus, d(C₂, Y) ≥ 3, contradicting the distance requirement of Observation 3.2. We conclude that no graph G exists such that ℐ (G) = Θ 〈2, 3, 4〉.

6.4.

Θ 〈3, 3, 3〉 is not an i-Graph

Proposition 6.4.

The graph Θ 〈3, 3, 3〉 is not i-graph realizable.

Proof

Let H be the theta graph Θ 〈3, 3, 3〉, with vertices labelled as in Figure 28. Suppose to the contrary that there exists some graph G such that H is the i-graph of G; that is, ℐ (G) = Θ 〈3, 3, 3〉.

Figure 28.

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

Since d_H(A₁, Y) = 2, by Observation 3.4, |A₁ − Y| = 2. Similarly, |B₁ − Y| = 2 and |C₁−Y| = 2. Suppose that, say, x₄ ∉ Y. Hence, by Observation 3.2 |{x₁, x₂, x₃} ∩ Y| ≥ 1. Without loss of generality, say x₁ ∈ Y. Then since y₁ ∉ Y and x₄ ∉ Y, both x₂ and x₃ ∈ Y to satisfy |A₁ − Y| = 2. However, then Y = {x₁, x₂, x₃, z, x₅, . . . , x_k} for some vertex z ∼ x₄, and so X∼x4zY X\mathop \sim \limits^{{x_4}z} Y , which is not so. We therefore conclude that x₄ ∈ Y, and likewise x_i ∈ Y for i ≥ 4. Thus, {x₁, x₂, x₃} ∩ Y = ∅.

Returning to A₁, since d(A₁, Y) = 2 and x₂, x₃ ∉ Y, we have that y₁ ∈ Y. Similarly, y₂, y₃ ∈ Y. Thus, Y = {y₁, y₂, y₃, x₃, . . . , x_k}. Moreover, A₂ is obtained from A₁ by replacing one of x₂ or x₃, by y₂ or y₃, respectively. Say, A1∼x2y2A2 {A_1}\mathop \sim \limits^{{x_2}{y_2}} {A_2} so that A₂ = {y₁, y₂, x₃, . . . , x_k}. Now, however, we have that B1∼x1y1A2 {B_1}\mathop \sim \limits^{{x_1}{y_1}} {A_2} , but clearly B₁ ≁ A₂. It follows that Θ 〈3, 3, 3〉 is not an i-graph.

This completes the proof of Theorem 5.3.

In this section we first display a graph that is neither a theta graph nor an i-graph, and then use the method of graph complements to show that every cubic 3-connected bipartite planar graph is an i-graph.

7.1.

A non-theta non-i-graph

So far, every non-i-graph we have observed is either one of the seven theta graphs from Theorem 5.3, or contains one of those seven as an induced subgraph (as per Corollary 3.11). This leads naturally to the question of whether theta graphs provide a forbidden subgraph characterization for i-graphs. Unfortunately, this is not the case.

Consider the graph 𝒯 in Figure 29: it is not a theta graph, and although it contains several theta graphs as induced subgraphs, none of those induced subgraphs are among the seven non-i-graph theta graphs. In Proposition 7.1 we confirm that 𝒯 is not an i-graph.

Figure 29.

A non-theta non-i-graph 𝒯.

Proposition 7.1.

The graph 𝒯 in Figure 29 is not an i-graph.

Proof

We proceed similarly to the proofs for the theta non-i-graphs in Section 6. Let 𝒯 be the graph in Figure 29, with vertices as labelled, and suppose to the contrary that there is some graph G such that ℐ (G) ≅ 𝒯.

To begin, we determine the vertices of the two induced C₄’s of 𝒯. Immediately from Proposition 3.6, the vertices of X, A₁, B₁, and B₂ are as labelled in Figure 29. Using a second application of Proposition 3.6, A₂ differs from A₁ in exactly one position, different from B₂. Without loss of generality, say, A1∼x3y3A2 {A_1}\mathop \sim \limits^{{x_3}{y_3}} {A_2} . Then again by the proposition, Y = {y₁, y₂, y₃, x₄ . . . , x_k} as in Figure 29.

We now construct the vertices of D₁ through a series of claims: (i)

x₃ is not in D₁.

From Lemma 3.3, D₁ differs from X in one vertex, different from both A₁ and B₁; moreover, x₁ and x₂ are in D₁. Notice that {x₄, x₅, . . . , x_k} ⊆ D₁: suppose to the contrary that, say, x₄ ∉ D₁, so that X∼x4zD1 X\mathop \sim \limits^{{x_4}z} {D_1} . Then z ≠ y₁, since y₁ ∼_G x₁ and D₁ is independent. Likewise z ≠ y₂ and z ≠ y₃. Thus D₁ = {x₁, x₂, x₃, z, x₅, . . . , x_k} has |Y ∩ D₁| = 4, but d(D₁, Y) = 3, contradicting Observation 3.4.

(ii)

y₁, y₂, and y₃ are not in D₁.

As above, y₁ and y₂ are not in D₁, as D₁ is an independent set containing x₁ and x₂. Suppose to the contrary that X∼x3y3D1 X\mathop \sim \limits^{{x_3}{y_3}} {D_1} , so that D₁ = {x₁, x₂, y₃, . . . , x_k}. Then, since x₁ ∼_G y₁, we have that D1∼x1y1A2 {D_1}\mathop \sim \limits^{{x_1}{y_1}} {A_2} , a contradiction.

(iii)

D₁ = {x₁, x₂, z, x₄, . . . , x_k}, where z ∉ {y₁, y₂, y₃}.

Immediate from (i) and (ii).

A contradiction for the existence of G arises as we construct D₂. Since d_𝒯(D₁, Y) = 3 and |D₁ ∩ Y| = 3, at each step along the path through D₂, D₃, and Y, exactly one token departs from a vertex of D₁ and moves to one of Y − D₁ = {y₁, y₂, y₃}. However, D₂ ≠ {y₁, x₂, z, x₄, . . . , x_k}, since otherwise, A1∼x3zD2 {A_1}\mathop \sim \limits^{{x_3}z} {D_2} . Likewise, D₂ ≠ {x₁, y₂, z, x₄, . . . , x_k}. Finally D₂ ≠ {x₁, x₂, y₃, x₄, . . . , x_k} as again we have A2∼y1x1D2 {A_2}\mathop \sim \limits^{{y_1}{x_1}} {D_2} . Thus, we cannot build a set D₂ such that |D₂ ∩ Y| ≤ 2 as required. We so conclude that no such graph G exists, and that 𝒯 is not an i-graph.

Like the seven non-i-graph realizable theta graphs of Theorem 5.3, 𝒯 is a minimal obstruction to a graph being an i-graph; every induced subgraph of 𝒯 is a theta graph.

We conclude with a few open problems. Although the problems are stated here for i-graphs, many are relevant to other reconfiguration graphs pertaining to domination-type parameters and are also mentioned in [8, 9].

A graph G is well-covered if all its maximal independent sets have the same cardinality, that is, if α(G) = i(G).

As a special case of Problem 7, note that for any n ≥ 1, ℐ (K_n) ≅ K_n, and that for k ≡ 2 (mod 3), ℐ (C_k) ≅ C_k.