Limits and Periodicity of Metamour $2$-Distance Graphs
William Q. Erickson Daniel Herden Jonathan Meddaugh Mark R. Sepanski Mitchell Minyard Kyle Rosengartner



[2020]Primary: 05C12, 05C76; Secondary: 05C38

§ ABSTRACT 
    Given a finite simple graph G, let (G) denote its 2-distance graph, in which two vertices are adjacent if and only if they have distance 2 in G.  
    In this paper, we consider the periodic behavior of the sequence G, (G), ^2(G), ^3(G), … obtained by iterating the 2-distance operation.
    In particular, we classify the connected graphs with period 3, and we partially characterize those with period 2.
    We then study two families of graphs whose 2-distance sequence is eventually periodic: namely, generalized Petersen graphs and complete m-ary trees.
    For each family, we show that the eventual period is 2, and we determine the pre-period and the two limit graphs of the sequence.


Topological characterization of modified Kane-Mele-Rashba models via local spin Chern marker
    Tarik P. Cysne
    September 9, 2024 – Version 1.0
============================================================================================











§ INTRODUCTION






The notion of an n-distance graph was introduced by Harary–Hoede–Kadlecek <cit.>, and defined as follows: given a finite simple graph G, its n-distance graph is obtained by placing an edge between two vertices if and only if those vertices have distance n in the original graph G.
Since then, the study of n-distance graphs (in particular, the special case n=2) has developed in several directions, and has garnered increased interest within the last decade.
This recent interest includes work on the connectivity of 2-distance graphs <cit.>, their regularity <cit.>, their diameter <cit.>, 2-distance graphs which have certain maximum degree <cit.> or are isomorphic to the original graph <cit.>, and general characterizations of certain 2-distance graphs <cit.>.
Another topic of interest is the periodicity of graphs with respect to the 2-distance operation.
This question was first addressed in the note <cit.> in 2000 (see also <cit.>), and is the subject of the present paper.

Throughout the paper, we adopt the term metamour graph, which was recently introduced in <cit.> as a synonym for the 2-distance graph.
Starting with some finite simple graph G, we consider the sequence G, (G), ^2(G), ^3(G), …, obtained by repeatedly taking metamour graphs.
A natural problem is to describe the periodic behavior of this metamour sequence, in as much generality as possible.
Our paper solves this problem in several special cases, which we highlight below:

    
  * In Section <ref>, we discuss graphs G with the property M(G)=G≅ G. In particular, we provide two proofs that every graph is an induced subgraph of some graph G with M(G)=G≅ G, see Theorems <ref> and <ref>.
    
  * In Theorem <ref>, we determine the periodic behavior of the metamour sequence in the case where G is formed by joining an arbitrary number of graphs together in a cycle.
    (This generalizes Proposition 2 in Zelinka <cit.>.)
    
  * Theorem <ref> states that for any even positive integer k, every graph is an induced subgraph of a graph whose metamour sequence is k-periodic.
    (This theorem strengthens the main theorem in Zelinka <cit.>, which merely asserted that k-periodic graphs exist for each even k.)
    
  * In Theorem <ref>, we show that if G has metamour period 2, then G and (G) have the same diameter, which is at most 3.
    
  * In fact, when this diameter equals 3, we identify a certain subgraph C_5 (see Theorem <ref>) which must be contained in G.
    
  * In Theorem <ref>, we prove that the only connected graphs with metamour period 3 are the two cycle graphs C_7 and C_9.


In the final two sections of the paper, we consider graphs whose metamour sequence is eventually periodic.
In particular, we study two fundamental families in graph theory: the generalized Petersen graphs G(m,2), and the complete m-ary trees.
In each case (see Theorems <ref> and <ref>), we show that the eventual period is 2, we determine where in the sequence G, (G), ^2(G), ^3(G), … this periodicity begins, and we explicitly describe the two graphs that are the limits of this metamour sequence.

In addition to our main results summarized above, we also answer (in Theorem <ref>) a question posed in <cit.>, regarding the classification of metamour graphs. 
Moreover, the work in this paper led us to Questions <ref> and <ref>, and to

Conjecture <ref>, regarding the parity of metamour periods: roughly speaking, graphs with even metamour periods are “common” (as demonstrated in Theorem <ref>) and those with odd metamour periods are “rare” (conjecturally, finitely many).
Hence a natural direction for further research is the problem of proving Conjecture <ref>, and classifying those graphs whose metamour period is even (respectively, odd).







§ NOTATION






We write  for the nonnegative integers and ^+ for the positive integers. 


Throughout the paper, we use standard graph theoretical notation and terminology, which we summarize as follows.
We write G=(V,E) to denote a simple graph with vertex set V and edge set E.
We also use V(G) and E(G) to denote the vertex and edge sets of G.
We abbreviate the edge {x,y} by writing xy.
Let 
d_G:V× V→∪{∞}
be the distance function on G. 
Recall that the diameter of a connected graph G, denoted by (G), is the maximum value attained by d_G. A disconnected graph has infinite diameter.
We write G_1 ∪ G_2 for the union of two graphs, in which the vertex set is the disjoint union V(G_1) ∪ V(G_2) and the edge set is the disjoint union E(G_1) ∪ E(G_2).
We write G_1 ∇ G_2 for the join of two graphs, which is G_1 ∪ G_2 together with all edges connecting V(G_1) and V(G_2).
We write G for the complement of G, where V(G)=V(G), and xy ∈ E(G) if and only if xy ∉E(G).
We write K_n for the complete graph on n vertices, and C_n for the cycle graph on n vertices.
The edgeless graph on n vertices is the graph with no edges, which we denote by K_n.
We write G_1 ⊆ G_2 to express that G_1 is a subgraph of G_2.
Given a subset S ⊆ V(G), the induced subgraph is the graph with vertex set S, whose edges are all the edges in E(G) with both endpoints in S.
We write G_1 = G_2 to denote equality as graphs of distinguishable vertices, and we write G_1 ≅ G_2 to express that two graphs are isomorphic (i.e., equal up to forgetting vertex labels). A graph G is called self-complementary if G≅G.

The focus of this paper is the metamour graph of G (also known as the 2-distance graph in the literature):


    The metamour graph of G, written as
        
    (G),

    has vertex set V(G), and an edge between x,y∈ V(G) if and only if d_G(x,y) = 2. 

    More generally, we write ^0(G)  G and inductively define
        
    ^k+1(G) (^k(G)),      k ∈.





    Let k∈^+. 
    We say that G has metamour period k if
    
    ^k(G) = G

    and k is minimal with this property.
    We say that G has pseudo-metamour period k if
    
    ^k(G) ≅ G

    and k is minimal with this property.
    We say that G is metamour-complementary if
    
    (G) = G.

    
    
    


Whereas Definition <ref> above pertains to periodic sequences of metamour graphs, the following definition concerns those metamour sequences which are eventually periodic:


    Let k∈^+. We say that G has metamour limit period k if there exists N ∈ such that, for all integers i ≥ N, we have
    
    ^k+i(G) = ^i(G),

    and k is minimal with this property. In this case, we write
    
    lim(G) {^i(G) |  i ≥ N} =
            {^N(G), ^N+1(G), …, ^N+k-1(G) }

    for the metamour limit set of G.


Note that for finite graphs, the metamour limit period always exists, and so the metamour limit set is also finite.








§ GRAPHS THAT ARE METAMOUR GRAPHS






In this section, we collect some basic results on metamour graphs and metamour-complementary graphs. Our main goal is a characterization and discussion of those graphs G such that G=(G') for some graph G', i.e., of graphs which are metamour graphs (see Theorem <ref>).

We start by noting the following relation between (G) and G.

 
    For any graph G, we have
    
    (G)⊆G.

    If there is a graph G' on V(G) such that (G')=G, then G'⊆G.



    This follows immediately from Definition <ref>. In particular, if xy ∈ E(G), then d_G(x,y) = 1, thus xy ∉ E(G).


Metamour-complementary graphs are defined as the graphs G where equality is achieved in (G)⊆G. We provide an alternative characterization of metamour-complementary graphs.


    A graph G is metamour-complementary if and only if (G) ≤ 2.
    



    Suppose (G) = G. If x,y ∈ V with d_G(x,y) ≥ 2, then xy ∈ E(G) = E((G)) and so d_G(x,y) = 2.

    Now suppose (G) ≤ 2. Then for xy ∈ E(G), we have d_G(x,y) = 2 and so xy ∈ E((G)). Since (G) ⊆G by Lemma <ref>, we are done.


Theorem <ref> can be expanded to provide an answer to <cit.> by characterizing those graphs G which are metamour graphs.

 
    Let G=(V,E) be a graph. The following are equivalent:
    
        
  * There exists a graph G' on V such that (G')=G.
        
  * G is metamour-complementary, i.e., (G)=G.
        
  * For every xy ∈ E, there exists z ∈ V∖{x,y} with xz,yz ∉ E.
        
  * (G) ≤ 2.
    



    We first show that (1) and (2) are equivalent.
    It is immediate that (2) implies (1).
    To show that (1) implies (2), suppose (G) ≠ G. 
    By Definition <ref>, there exists xy ∈ E(G) such that there is no z ∈ V ∖{x,y} with xz,yz ∈ E(G). 
    Therefore, for any G'⊆G, we have xy∉(G'). 
    Since (by Lemma <ref>) any G' satisfying (G')=G satisfies G'⊆G, we are done.

    The equivalence of (2) and (3) follow immediately from Definition <ref>, and the equivalence of (2) and (4) from Theorem <ref>.    
    
    
    




















We also note the following nice sufficient characterization.

 
    Let Δ(G) denote the maximum degree of G=(V,E).
    If 
    
    2 Δ(G) < |V|,
 
    then there exists a graph G' such that (G')=G.



    Suppose xy ∈ E. Since (x) + (y)  < |V|, there is some z ∈ V with xz,yz ∉ E. Theorem <ref> finishes the result.



    If G is j-regular, then Corollary <ref> says that a sufficient condition for the existence of a G' such that (G')=G is 2j < |V|. Since |V| = 2|E|/j in this case, the condition can be rewritten as 
    
    j^2 < |E|.




    Theorem <ref> and Corollary <ref> allow us to quickly deduce that many families of graphs have the property that each graph is the metamour graph of its complement:
    
        
  * generalized Petersen graphs P(n,k) for all n≥ 4,
        
  * cycle graphs C_n for all n≥ 5,
        
  * path graphs P_n for all n≥ 5,
        
  * disconnected graphs,
        
  * trees T with (T)≥ 4, and
        
  * undirected Cayley graphs Γ(G,S) with 2|S| < |G|.
    
    On the other hand, graphs of the following types are not the metamour graphs of any graphs:
    
        
  * complete k-partite graphs for all k≥ 2,
        
  * complements of generalized Petersen graphs P(n,k) for n≥ 4,
        
  * complements of cycle graphs C_n  for all n≥ 6, and
        
  * complements of path graphs P_n for all n≥ 4.
        
        
    








§ GRAPHS WITH PSEUDO-METAMOUR PERIOD 1
 





In this section, we will discuss graphs with metamour period 1 and graphs with pseudo-metamour period 1.
We start with the observation that there are only trivial graphs with metamour period 1.


    A graph G has metamour period 1 if and only if G is edgeless.



    With Lemma <ref>, M(G)=G implies G = M(G) ⊆G, and G=K_n for some n∈^+ follows. The converse is trivial.


In contrast, there exist many nontrivial examples of graphs with pseudo-metamour period 1. In the following, we will provide two different families of graphs G' with M(G')=G'≅ G', i.e., of metamour-complementary self-complementary graphs G'. In both cases we are going to see that any graph G can be embedded as an induced subgraph into some metamour-complementary self-complementary graph. Thus, the class of metamour-complementary self-complementary graphs is large and of a complex structure.

Our first example is based on properties of Paley graphs.

 
    Let q be a prime power such that q≡ 1 4. Then the Paley graph QR(q) has as vertex set the elements of the finite field 𝔽_q, with two vertices being adjacent if and only if their difference is a nonzero square in 𝔽_q.


 
    Every Paley graph is metamour-complementary and self-complementary. Moreover, for any finite graph G there exists a prime power q≡ 1 4 such that G embeds as an induced subgraph into QR(q).



    Let q be a prime power such that q≡ 1 4. Then QR(q) is self-complementary <cit.>, and such that every pair of distinct nonadjacent vertices shares q-1/4 common neighbors <cit.>. In particular, (G)=2, and G is metamour-complementary with Theorem <ref>. The embedding property follows as Paley graphs are quasi-random   <cit.>.


An easier and more instructive example of metamour-complementary self-complementary graphs can be given with the help of the following general graph operation. Some similar constructions will be used in the next section.

 
    Let G = (V,E) be a graph, and let 𝒢={G_v | v∈ V} be a collection of graphs indexed by V. We define the join of 𝒢 along G to be the graph constructed as follows. Begin with ⋃_v∈ V G_v. For every vw∈ E, include all possible edges between G_v and G_w.
    Thus, for each vw∈ E, the join G_v ∇ G_w is a subgraph of the join of 𝒢 along G.


  

See Figure <ref> for the visualization of Definition <ref> in the case where G = C_5.
(This particular case was constructed by Zelinka <cit.>, just before Proposition 2.)
In the figure, an edge between G_i and G_j represents all of the edges in G_i ∇ G_j. 

 
    Every graph G embeds as an induced subgraph into a metamour-complementary self-complementary graph G' with |V(G')| = 4  |V(G)|+1.



   Let G' denote the join of the family of graphs {G_1, …, G_5} along C_5; see Figure <ref>. It is easy to verify that G' is metamour-complementary with M(G')=G' as shown in Figure <ref>. Note that this graph M(G')=G' is (isomorphic to) the join of the family of graphs {G_1, G_3, G_5, G_2, G_4}  along C_5.
   
  

   In case of the specific choice G_1 := K_1 trivial, G_2 :=G_5 :=G, and G_3 := G_4 := G, any choice of isomorphisms φ_1: G_1 →G_1, φ_2: G_2 →G_3, φ_3: G_3 →G_5, φ_4: G_4 →G_2, and φ_5: G_5 →G_4 extends to an    isomorphism φ: G' →G'.


   


Note that any nontrivial metamour-complementary self-comple­men­tary graph has metamour period 2. With Theorem <ref>, this includes Paley graphs.
We end this section with a general characterization of metamour-complementary graphs with metamour period 2.

 
    A graph G is metamour-complementary with metamour period 2 if and only if (G) = (G) = 2.



    

    This follows immediately from Theorem <ref>.
    (See also <cit.>.)


We will have more to say about graphs with metamour period 2 in Section <ref>.







§ GRAPHS WITH EVEN METAMOUR PERIOD
 





In this section, we will see that for all even k≥ 2, the class of graphs with metamour period k is large and of a complex structure. This is again evidenced by showing that every graph G can be embedded as an induced subgraph into some graph with metamour period k (see Theorem <ref>). We will also show that the same is true for graphs with pseudo-metamour period k.

We start by introducing an auxiliary sequence of integers.


    Let n be an odd positive integer.
    We define 
    
    μ(n) min{k∈^+ | 2^k≡±1n}.

    For example, starting with n=3, the first few values of μ(n) are 

    1, 2, 3, 3, 5, 6, 4, 4, 9, 6, 11, 10, 9, 14, 5, 5, 12, 18, 12, 10, 7, 12, 23, 21,
    
    8, 26, 20, 9, 29, 30, 6, 6, 33, 22, 35, 9, 20, 30, 39, 27, 41, 8, 28, 11, …

This sequence can be found as entry A003558 in the OEIS <cit.>.





The following result on odd cycle graphs serves as a good comparison of metamour period versus pseudo-metamour period (see Definition <ref> above). Note that we exclude the case n=3 below, due to the fact that C_3 = K_3 and (K_3)=K_3.
 
    Let n ≥ 5 be odd, and let k,ℓ∈.
    We have the following:
    
        
  * ^k(C_n)≅ C_n.
        
  * ^k(C_n)=C_n if and only if μ(n) | k.
        
  * ^k(C_n)=^ℓ(C_n) if and only if k≡ℓμ(n).
    



    Write the vertices of C_n as v_i, i∈/n, with edges v_i v_i+1. Then it is straightforward to verify that the edges of ^k(C_n) are of the form v_i v_i+2^k. The statements of the theorem follow.



    Theorem <ref> takes also care of even cycle graphs C_n. In particular, given any n∈^+, we can write n=2^i u with i∈ and some odd u∈^+. Then ^i(C_n) is the disjoint union of 2^i cycle graphs C_u, where we set C_1 := K_1.






In the following, we describe a few more constructions based on our Definition <ref>. We start with a characterization of isomorphic graphs.

 
    Let n ≥ 7 be odd, and let 𝒢={G_i | 1≤ i ≤ n} and 𝒢'={G'_i | 1≤ i ≤ n} be two collections of graphs, where we interpret all indices as elements of /n. Let G denote the join of 𝒢 along C_n and G' the join of 𝒢' along C_n, respectively.
    Then G≅ G' if and only if there exists some j∈/n such that either G'_i≅ G_j+i or G'_i≅ G_j-i for all 1≤ i ≤ n.



    Note that μ(n) ≥ 3 as n≥ 7. It is straightforward to verify that ^2(G) is the join of 𝒢 along ^2(C_n). Thus G ∩^2(G) =⋃_1≤ i ≤ n G_i, and similarly (G) ∩^3(G) =⋃_1≤ i ≤ nG_i. In particular,
    
    E(G ∩^2(G))∪ E((G) ∩^3(G))= ⋃_1≤ i ≤ n{xy | x,y ∈ V(G_i), x y},

    and we recover V(G_i) (up to the index). With this information, we can rediscover {G_i | 1≤ i ≤ n} from G up to an index shift/flip.


We now can generalize Theorem <ref> as follows:

 
    Let n ≥ 5 be odd, and let 𝒢={G_i | 1≤ i ≤ n} be a collection of graphs with at least one G_i nontrivial. Let G be the join of 𝒢 along C_n.
    
    Similarly, let 𝒢={G_i | 1≤ i ≤ n} and let G^0 be the join of 𝒢 along C_n.  Then we have the following:  
    
        
  * ^k(G)=G if and only if μ(n) | k and k is even.
        
  * ^k(G)=G^0 if and only if μ(n) | k and k is odd.
        
        
        
        
  * If n≥ 7 and G_i G_i = G_j for all i,j, then ^k(G) ≅^ℓ(G) if and only if k≡ℓ 2. 
    



    It is straightforward to verify that ^k(G) is the join of either 𝒢 (when k is even), or 𝒢 (when k is odd), along ^k(C_n). The first two statements of the theorem follow from this and Theorem <ref>. The last statement follows from Theorem <ref>.


As an example of Theorem <ref>, 
let 𝒢={G_i  |   1≤ i ≤ 7} where every G_i = K_2, and let G be the join of 𝒢 along C_7, see Figure <ref>.
Similarly, let G^0 be the join of {G_i = K_2 |  1≤ i ≤ 7} along C_7.
Since μ(7)=3, we have the following three results from Theorem <ref>:

    
  * ^k(G)=G if and only if 6|k.
    
  * ^k(G)=G^0 if and only if k is an odd multiple of 3.
    
  * ^k(G)≅^ℓ(G) if and only if k≡ℓ 2.









































We continue with a construction of graphs with even metamour period k.



    Let G be a graph and k∈^+ even. Then G embeds as an induced subgraph into a graph G' with metamour period k. In addition, we can achieve |V(G')|=|V(G)|+4 for k=2 and |V(G')|=|V(G)|+2^k-2 for k≥ 4.
    



    Let n=5 for k=2 and n=2^k-1 for k≥ 4. Observe that n≥ 5 with μ(n)=k.
    Let 𝒢={G_i | 1≤ i ≤ n} with G_1=G and G_i=K_1 for 2≤ i ≤ n.
    Let G' be the join of 𝒢 along C_n so that G embeds as an induced subgraph into G'. By Theorem <ref> (or Theorem <ref> if G is trivial), G' has metamour period k.


In particular, for any even k, there are infinitely many connected graphs whose metamour period is k. This result is in stark contrast to our upcoming Conjecture <ref> (concerning odd metamour periods).

We close this section with a variation of Theorem <ref> which provides a construction of graphs with even pseudo-metamour period k.



    Let G be a graph and k∈^+ even. Then G embeds as an induced subgraph into a graph G' with metamour period k and G'^i(G') for all 1≤ i< k. In particular, G' has pseudo-metamour period k.
    



    Let n=2^k+1. Then n≥ 5 with μ(n)=k.
    Choose any collection of graphs 𝒢={G_i | 1≤ i ≤ n} such that G_1=G and all |V(G_i)| are distinct.
    Let G' be the join of 𝒢 along C_n, and use Theorem <ref> for the result.
























§ MORE ON GRAPHS WITH METAMOUR PERIOD 2
  





In this section and the next, we study graphs with metamour period 2 and 3, respectively. In particular, in this section, we will be focusing on the question whether there exist any graphs
with metamour period 2 that do not result from joining graphs along C_5. We will aim towards a
more complete characterization of graphs with metamour period 2.


    It is straightforward to verify that ^2(C_5)=C_5. More generally, by adjoining vertices to C_5 as depicted in Figure <ref>, we can construct additional examples of graphs with metamour period 2.
    


These examples lead to a general construction of an infinite family of graphs with metamour period 2, constructed via Definition <ref>.
An important element of this construction will be the graph defined below: 



    We write C_5 to denote the graph obtained from C_5 by adding an additional vertex that is connected to two adjacent vertices of C_5.  (The notation is meant to suggest C_5 with a “hat.”
    This is the graph in the center of Figure <ref>.)


The graph C_5 already provides a simple example of a graph with metamour period 2 that is not the result of joining graphs along C_5. Can we tell any more about the structure of graphs with metamour period 2? We start with a very general observation.

 
    
    
    
    Let G be a graph with metamour period 2, and let G' denote the join of a collection of graphs 𝒢 along G. Then G' has again metamour period 2.
    In particular, this holds for any join of graphs {G_1, …, G_5} along C_5, see Figure <ref>, and any join of graphs {G_1, …, G_6} along C_5, see Figure <ref>.
    



    Let 𝒢= { G_i | i∈ I }, and denote 𝒢= {G_i | i∈ I }. Using Definition <ref>, it is straightforward to check that (G') 
    is the join of 𝒢 along (G).    
    
    From this, it is straightforward to verify that .



   The graph on the right side of Figure <ref> is the join of {K_1,K_1,K_1,K_1,K_1,K_2} along C_5.

   Note also that every nontrivial metamour-complementary self-com­ple­mentary graph G has metamour period 2 and thus qualifies for Theorem <ref>. This includes all Paley graphs, see Theorem <ref>. 

    
    

Our next result can be viewed as a generalization of Theorem <ref>.

 
    Suppose G=(V,E) is a connected graph with metamour period 2. Then (G) is connected and either
    
    (G) = ((G)) = 2     (G)=G,

    or
    
    (G) = ((G)) = 3     (G)⊊G.

    Moreover, for all distinct x,y∈ V, we have
    
    d_G(x,y)=1     d_(G)(x,y) = 2,
     
            d_G(x,y)=2     d_(G)(x,y) = 1,
     
            d_G(x,y)=3     d_(G)(x,y) = 3.

    
    
    
    
    
    
    



    Since ^2(G) = G is connected, (G) is connected. It follows that (G) ≥ 2 since (K_n)=K_n is disconnected for n≥ 2 while K_1 has metamour period 1.
    Moreover, if there existed x,y∈ V with d_G(x,y)=4, then there would exist z∈ V so that d_G(x,z)=d_G(z,y)=2. This would force xz,yz∈ E((G)) and xy∉E((G)). By metamour periodicity, this would show that xy∈ E, a contradiction. As (G) also has metamour period 2, the roles of G and (G) are symmetrical and we see that
    
    2 ≤(G), ((G)) ≤ 3.


    Now, if (G)=2, then for distinct x,y∈ V, either xy∈ E or xy ∈(G). From this, it follows that (G) = G. By periodicity and Theorem <ref>, (G)=2 as well. By symmetry, we see that 
    
    (G) =2 ((G)) = 2.


    From this, we also conclude that (G) =3 ((G)) = 3. In this case, the existence of distance-three vertices implies that (G)≠G.
    
    
    
    
    
    
    
    
    
    

    Now let x,y∈ V be distinct. By periodicity, d_G(x,y)=1 implies d_(G)(x,y) = 2.
    Moreover, by Definition <ref>, d_G(x,y)=2 implies d_(G)(x,y) = 1. 
    By symmetry, we thus obtain both equivalences involving distance 1 and 2.
    In turn, this yields the equivalence involving distance 3. 
 
















 
    Suppose G is a connected graph with metamour period 2 and (G) = 3. Then G contains a subgraph isomorphic to C_5 (shown in the middle of Figure <ref>).



    Let x,y ∈ V(G) with d_G(x,y) = 3. As d_(G)(x,y) = 3, let (w_0,w_1,w_2,w_3) be a minimal path from x to y in (G). For 0≤ i ≤ 2, since w_i w_i+1∈ E((G)), there is some u'_i ∈ V(G) with w_iu'_i,u'_iw_i+1∈ E(G). 
    
    Define a walk (u_0,u_1,…,u_6) by
    
    u_i =
            
                w_i/2,    for i even, 
    
                u'_(i-1)/2,    otherwise.

    After possibly relabeling (see Figure <ref>), it is straightforward to verify that there are two possibilities:
    
        
  * All of the vertices u_i are distinct.
        
  * The only vertices u_i that are not distinct are u_3 = u_5.
    
    
    By minimality, we have u_0u_4,u_2u_6∈ E(G), giving us the two possible configurations depicted in Figure <ref>.    
                
        If the vertices are all distinct, then, after possibly relabeling, it is straightforward to check that u_0 u_3 ∈ E((G)) and u_3 u_6 ∈ E(G). As a result, in either possibility from above, we have a copy of C_5  (see Figure <ref>).
        


In light of Theorem <ref>, it seems reasonable to ask for a full characterization of diameter-3 graphs with metamour period 2 (see Theorem <ref>). In particular, we have the following question:
 
    Is every connected diameter-3 graph with metamour period 2 the join of some graphs along C_5 (as in Figure <ref>)?


A negative answer to Question <ref> may result in the discovery of a whole new family of diameter-3 graphs with metamour period 2 similar to Paley graphs as diameter-2 graphs with metamour period 2.

In this context, one may also ask the following question:
 
    Is every connected diameter-2 graph with metamour period 2 the join of some graphs along a Paley graph?















§ GRAPHS WITH METAMOUR PERIOD 3
 





In contrast to Section <ref>, we will provide a full characterization of graphs with metamour period 3 in Theorem <ref> and Corollary <ref>. 

En route to these results, we begin with a slate of lemmas.
 
    Let G be a connected graph with metamour period 3.
    
        
  * Then E(G), E((G)), and E(^2(G)) are pairwise disjoint.
        
  * If v_1v_2,v_2v_3 ∈ E(G') for some G' ∈{G,(G),^2(G)}, then v_1v_3 ∉ E(^2(G')).
        
  * If v_1v_2,v_2v_3 ∈ E(G') and v_1v_2',v_2'v_3 ∈ E((G')) for some G' ∈{G,(G),^2(G)}, then v_1v_3 ∈ E((G')).
    



    The first part follows from Lemma <ref> applied to each of the pairs of graphs ^i(G) and ^i+1(G) for 0≤ i ≤ 2 combined with metamour period 3. 
    For the second part, Definition <ref> shows that v_1v_2,v_2v_3 ∈ E(G') implies v_1 v_3 is in either E(G') or E((G')). Combined with part one, we are done. 
    For the third part, v_1v_2',v_2'v_3 ∈ E((G')) implies v_1 v_3 is in either E((G')) or E(^2(G')). Combined with part two, we are done.


 
    Suppose G=(V,E) is a connected graph with metamour period 3. For v_1v_2 ∈ E, there is a walk (w_0,w_1,…,w_8) in G such that w_0=v_1, w_8 = v_2, w_0w_2, w_2w_4, w_4w_6, w_6w_8 ∈ E((G)), and w_0w_4, w_4w_8 ∈ E(^2(G)), see Figure <ref>. Furthermore, one of the following must hold:
    
        
  * All vertices w_i are distinct.
        
  * The only vertices w_i that are not distinct are w_0 = w_7 and w_1 = w_8.
    





    Begin with w_0=v_1 and w_8=v_2 so that w_0 w_8 ∈ E. 
    By metamour period 3, there exists w_4 ∈ V so that w_0 w_4, w_4 w_8 ∈ E(^2(G)). 
    From this it follows that there exist w_2, w_6 ∈ V so that w_0w_2, w_2w_4, w_4w_6, w_6w_8 ∈ E((G)).
    Finally, this shows that there exist w_1, w_3, w_5, w_7 ∈ V so that (w_0,w_1,…,w_8) in a walk in G.
    
    By construction, any pair of adjacent vertices in Figure <ref> must be distinct in G (solid lines), respectively (G) (dotted lines), and ^2(G) (dashed lines). Furthermore, Lemma <ref> shows that w_0 ∉{w_3,w_5,w_6}, w_1 ∉{w_3,w_4,w_5,w_6}, and w_2 ∉{w_5,w_6,w_7,w_8}.

    Next we show that w_3 and w_5 are distinct. By way of contradiction, suppose w_3 = w_5. From Lemma <ref>(3), we would have w_2w_6 ∈ E((G)). Therefore, either w_0w_6 ∈ E((G)), which implies w_0w_8 ∉ E, or w_0w_6 ∈ E(^2(G)), which implies w_4w_6 ∉ E((G)). Contradiction.
    By similar arguments, w_1 ≠ w_7 and w_1w_3,w_5w_7 ∈ E((G)).

    By symmetry, it only remains to show that assuming w_0 = w_7 and w_1 ≠ w_8 leads to a contradiction, see Figure <ref>.
    

    Case 1: w_1w_8 ∈ E.
    Since w_0w_8∈ E, we get w_8w_2 ∉ E((G)) and hence w_8w_2 ∈ E. Thus, either w_8w_3 ∈ E, which implies w_8w_4 ∉ E(^2(G)), or w_8w_3 ∈ E((G)), which implies w_1w_8 ∉ E. Contradiction.

    Case 2: w_1w_8 ∈ E((G)).
    By Lemma <ref>, we have w_1w_6 ∈ E((G)). Since w_1w_6,w_6w_4 ∈ E((G)), we get either w_1w_4 ∈ E((G)), which implies w_1w_2 ∉ E, or w_1w_4 ∈ E(^2(G)), which implies w_8w_1 ∉ E((G)). Contradiction.


 
    Suppose G is a connected graph with metamour period 3. Then G contains an induced copy of either C_7 or C_9.
    



    Begin with the walk from Lemma <ref>, (w_0,…,w_8). If w_0 = w_7 and w_1 = w_8, we will see that we get an induced C_7. When all w_i are distinct, we will get an induced C_9. As the arguments are similar and overlap, we give details here only for the first case. 
    
    Suppose that w_0 = w_7, w_1 = w_8, and all other w_i are distinct.    
    By Lemma <ref>(1), we see that w_5w_0, w_0w_2, w_2w_4, w_4w_6, w_6w_1, w_1w_3, w_1w_4, w_4w_0 ∉ E(G). Since w_6w_4,w_4w_2 ∈ E((G)), we have w_6w_2 ∉ E(G) from Lemma <ref>(2). Similar arguments show w_2w_5, w_3w_6 ∉ E(G). Since w_4w_0 ∈ E(^2(G)), we have w_0w_3 ∉ E(G). Similarly, w_5w_1 ∉ E(G).
    
    
    Finally, suppose w_3w_5 ∈ E(G). Then w_2w_5 ∈ E((G)). Since w_4w_2,w_2w_5 ∈ E((G)), we get w_4w_5 ∉ E(G). Contradiction.
    
    


 
    Suppose G is a connected graph with  metamour period 3. 
    Then G contains an induced copy of C_n, n∈{7,9}, on vertices w_i, 0≤ i ≤ n-1, so that w_i w_i± 4∈ E(^2(G)) for all i, with indices interpreted n.
    



    Continue the notation and arguments from Lemmas <ref> and <ref>.
    We only give details in the case where all vertices w_i are distinct since the case of w_0 = w_7 and w_1 = w_8 is similar and straightforward.

    Note that w_i w_i± 2∈ E((G)) for all i. Thus, w_0w_2,w_2w_4 ∈ E((G)), and either w_0w_4 ∈ E((G)) or w_0w_4 ∈ E(^2(G)). Suppose w_0w_4 ∈ E((G)). Then either w_0w_6 ∈ E((G)), which implies w_0w_8 ∉ E(G), or w_0w_6 ∈ E(^2(G)), which together with w_0w_4 ∈ E(^2(G)) implies w_4w_6 ∉ E((G)). Contradiction.
    
    The others statements follow by similar arguments.


We arrive at the main theorem of this section.

 
    G=(V,E) is a connected graph with metamour period 3 if and only if it is isomorphic to either C_7 or C_9.
    
    
    
    
    



    Let G be a connected graph with metamour period 3. 
    Begin with the induced copy of C_n, n∈{7,9}, on w_0,…,w_n-1 from Lemma <ref>. It remains to show that G has no additional vertices.
    By way of contradiction, suppose there exists v∈ V ∖{w_0,…,w_n-1}.
    After relabeling, suppose vw_0 ∈ E. 
    
    Then either vw_1 ∈ E or vw_1 ∈ E((G)). By way of contradiction, suppose vw_1 ∈ E. 
    As a result, either v w_2 ∈ E or v w_2 ∈ E((G)). In the later case, combining with w_0 w_2 ∈ E((G)), we would get v w_0 ∉ E. Contradiction. Therefore, v w_2 ∈ E.     
    We can similarly conclude vw_3,vw_4 ∈ E. As then w_0v,vw_4 ∈ E, it follows that w_0 w_4 ∉ E(^2(G)). Contradiction. Thus, vw_1 ∈ E((G)). Similarly, vw_n-1∈ E((G)).

    Since vw_1, w_1w_3 ∈ E((G)), we get either v w_3 ∈ E((G)) or v w_3 ∈ E(^2(G)).
    If vw_3 ∈ E(^2(G)), then vw_3,w_3w_n-1∈ E(^2(G)) by Lemma <ref>, and so vw_n-1∉ E((G)). Contradiction. Thus vw_3 ∈ E((G)), and either  vw_5 ∈ E((G)) or vw_5 ∈ E(^2(G)). If vw_5 ∈ E(^2(G)), then w_1w_5 ∈ E(^2(G)) implies the contradiction vw_1 ∉ E((G)). Thus, vw_5 ∈ E((G)).

    Case 1: w_0 = w_7 and w_1 = w_8 with n=7.
    
    
    
    With vw_5, vw_n-1 = vw_6 ∈ E((G)), we have the final contradiction w_5w_6 ∉ E. 

    Case 2: The vertices are all distinct with n=9.
    
    With vw_5 ∈ E((G)) we also have vw_4 ∈ E((G)) by symmetry. Now vw_4, vw_5 ∈ E((G)) implies w_4w_5 ∉ E. Contradiction.


The following result is now immediate.

 
    A nontrivial graph has metamour period 3 if and only if it is the disjoint union of some copies of C_7 and C_9.


In general, we conjecture that connected graphs with odd metamour period are rare. If true, it would be especially interesting to classify them. Note the conjectured difference to graphs with even metamour period, Theorem <ref>.

 
    For each odd k∈^+, there exist only finitely many connected graphs with metamour period k.








§ METAMOURS OF GENERALIZED PETERSEN GRAPHS






To help with digestion of Definition <ref> below, we will begin with a walk of 2^k + 1 vertices and 2^k associated edges. For each i, 0 ≤ i ≤ k-1, this walk will be broken up into 2^k-i-1 smaller walks of 2^i+1 + 1 consecutive vertices and 2^i+1 edges. For the jth such smaller walk, 0 ≤ j ≤ 2^k-i-1-1, we will look at its first, middle, and last vertex. In particular, there will be 2^i edges each between the middle vertex and the vertices at either end of this small walk.
 
    Fix G=(E,V), u,v ∈ V distinct vertices, and k∈^+. A 2-walk of length k from u to v is a walk π = (w_0,w_1,…,w_2^k) in G with u=w_0 and v=w_2^k such that:    
    
        
  * For all 0 ≤ i ≤ k-1 and 0 ≤ j ≤ 2^k-i-1-1, 
            w_2j·2^i, w_(2j+1)·2^i, and w_2(j+1)·2^i are distinct.
        
  * For all 0 ≤ j ≤ 2^k-1-1, w_2jw_2(j+1)∉ E.
    
    
    Note that restriction of π to (w_2j· 2^i, …, w_2(j+1)· 2^i) gives a 2-walk of length i+1 from w_j· 2^i+1=w_2j· 2^i to w_(j+1)· 2^i+1 =w_2(j+1)· 2^i.
    We will say that π is fully minimal if, for all 1 ≤ i ≤ k-1 and 0 ≤ j ≤ 2^k-i-1-1, there is no 2-walk from w_j· 2^i+1 to w_(j+1)· 2^i+1 of length i. Again, restricting a fully minimal 2-walk π to (w_j· 2^i+1, …, w_(j+1)· 2^i+1) gives a fully minimal 2-walk of length i+1 from w_j· 2^i+1 to w_(j+1)· 2^i+1.


 
    Continue the notation from Definition <ref>. We will say that 
    
    d_2(u,v) = i

    if the minimal length of a 2-walk between u and v is i. 
    
    With this notation, if a 2-walk π = (w_0,w_1,…,w_2^k) of length k 
    from u to v satisfies d_2(w_j· 2^i+1, w_(j+1)· 2^i+1)=i+1 for all 1 ≤ i ≤ k-1 and 0 ≤ j ≤ 2^k-i-1-1, then π will trivially be fully minimal. However, the converse of this statement is not true. Also, neither is it true that every minimal length 2-walk is fully minimal nor that every fully minimal 2-walk is of minimal length.


In the case of k=1 in Definition <ref>, the existence of a (fully minimal) 2-walk of length k from u to v is equivalent to uv∈ E(^1(G)). However, this is no longer true when k≥ 2. To that end, from Definition <ref>, we immediately get the following condition to have an edge in ^k(G).
 
    Let G=(V,E), u,v ∈ V distinct vertices, and k∈^+. Then uv ∈ E(^k(G)) if and only if there is a 2-walk (w_0,w_1,…,w_2^k) of length k from u to v in G such that, for 0 ≤ i ≤ k and 0 ≤ j ≤ 2^k-i - 1, 
    
    w_j· 2^iw_(j+1)·2^i∈ E(^i(G)).

    


Lemma <ref> gives a necessary and sufficient condition to have an edge in ^k(G), but it is very hard to verify. Theorem <ref> below gives a sufficient condition that is easier to check if it is satisfied.
 
    
    Let G=(V,E) with distinct vertices u,v ∈ V. If there is a fully minimal 2-walk of length k from u to v in G, then uv ∈ E(^k(G)).



    
    Let (w_0,w_1,…,w_2^k) be a fully minimal 2-walk of length k from u to v. As w_2jw_2j+1,w_2j+1w_2(j+1)∈ E for 0 ≤ j ≤ 2^k-1-1 and w_2jw_2(j+1)∉ E, we get w_2jw_2(j+1)∈ E(^1(G)).

    If uv∉E(^k(G)), then, noting Lemma <ref>, choose the smallest i, 1 ≤ i ≤ k-1, such that there is some j, 0 ≤ j ≤ 2^k-i-1 - 1, 
    so that w_j· 2^i+1w_(j+1)·2^i+1∉ E(^i+1(G)). 
 
    However, minimality of i gives
    w_2j· 2^iw_(2j+1)·2^i,   w_(2j+1)·2^iw_2(j+1)·2^i∈ E(^i(G)). Thus, we must have 
    w_j· 2^i+1w_(j+1)·2^i+1=w_2j· 2^i w_2(j+1)·2^i∈ E(^i(G)) as w_j· 2^i+1w_(j+1)·2^i+1∉ E(^i+1(G)).   
    Lemma <ref> now shows that there exists a 2-walk of length i from w_j· 2^i+1 to w_(j+1)·2^i+1, which is a contradiction.


The next lemma will allow us to bootstrap up metamour orders by expanding 2-walks.
  
    
    Let uv ∈ E(^k(G)) and π =( w_0,w_1,…,w_2^k) a 2-walk from u to v in G such that, for 0 ≤ i ≤ k and 0 ≤ j ≤ 2^k-i - 1, w_j·2^iw_(j+1)·2^i∈ E(^i(G)). 
    
    Suppose that, for 0 ≤ a ≤ 2^k - 1, there is a fully minimal 2-walk of length 2 from w_a to w_a+1. Then uv ∈ E(^k+2(G)) as well.



    Construct a 2-walk, π' = (w_0',w_1',…,w_2^k+2'), of length k+2 from π by replacing each edge w_a w_a+1 in π by its corresponding fully minimal 2-walk of length 2 from w_a to w_a+1. Observe that w'_4a = w_a. By construction, note that, for 0 ≤ j ≤ 2^k+1-1, we have w'_2jw'_2(j+1)∈ E(^1(G)).
    
    
    Arguing as in Lemma <ref>, suppose uv ∉E(^k+2(G)). Using Lemma <ref>, choose the smallest i, 1 ≤ i ≤ k+1, such that there is some j, 0 ≤ j ≤ 2^k-i-1 - 1, so that w_j· 2^i+1' w_(j+1)·2^i+1' ∉ E(^i+1(G)). By full minimality of the added 2-walks, we see that i≥ 2.
    By minimality of i, w'_2j·2^iw'_(2j+1)·2^i,w'_(2j+1)·2^iw'_2(j+1)·2^i∈ E(^i(G))
    which forces w_j· 2^i+1' w_(j+1)·2^i+1' ∈ E(^i(G)). Thus 
    w_j·2^i-1  w_(j+1)·2^i-1∈ E(^i(G)), which violates its membership in E(^i-1(G)).
    



    
    


    
    
    


Write G(m,j) for the generalized Petersen graph where m,j∈^+ with m≥ 5 and 1≤ j < m/2. We will use {v_i, u_i | 0≤ i < m} as vertex set with edges

    v_i v_i+1,    v_i u_i,  and  u_i u_i+j for all  0≤ i<m,

where indices are to be read modulo m. We may refer to the {v_i} as the exterior vertices and the {u_i} as the interior vertices.
Observe that the interior vertices break up into (m,j) cycles of size m/(m,j) each, where (m,j) denotes the greatest common divisor of m and j.

Our first main result, Theorem <ref>, will calculate the metamour limit period and metamour limit set of G(m,2).
With an eye towards applying Lemma <ref> in the context of certain generalized Petersen graphs, we prove the following lemma.
 
    Let m∈^+ with m≥ 5. If uv ∈ E(G(m,2)), there exists a fully minimal 2-walk of length 2 from u to v.



    It will be sufficient to show that every edge of G(m,2) lies in an induced subgraph isomorphic to C_5. For this, look at the cycle given by (v_i,v_i+1,v_i+2,u_i+2,u_i,v_i), see Figure <ref>.    
    


The next theorem shows that metamour edges persist in G(m,2) and are sorted only by parity.
 
    Let m,n,ℓ,ℓ_1,ℓ_2∈ with m≥ 5. Then 
    
    E(^n(G(m,2))) ⊆ E(^n+2ℓ(G(m,2)))

    and
    
    E(^ℓ_1(G(m,2))) ∩ E(^ℓ_2(G(m,2))) = ∅
    
    if ℓ_1 and ℓ_2 have opposite parities.


    
    Lemmas <ref> and <ref> show that 
    
    E(^n(G(m,2))) ⊆ E(^n+2ℓ(G(m,2))).

    From this, we see that 
    E(^ℓ_1(G(m,2))) ∩ E(^ℓ_2(G(m,2))) is empty if ℓ_1 and ℓ_2 have opposite parities since the two sets can be embedded into adjacent metamour powers of G(m,2).


In order to calculate the metamour limit set for G(m,2), we continue developing our notations from Definition <ref>. 
 
    Let k∈^+. Define the fully minimal k-set, 
    
    _k(G(m,2)) ⊆ E(G(m,2)) ∪ E(G(m,2)),

    as the set of all edges uv, with distinct u,v∈ V(G(m,2)), for which there exists a fully minimal 2-walk of length k from u to v. 
    Let
    
    _ev(G(m,2)) = ⋃_k  even_k(G(m,2)),

    
    _od(G(m,2)) = ⋃_k odd_k(G(m,2)).

    We say that _ev(G(m,2)) stabilizes by N∈^+ if
    
    _ev(G(m,2)) = ⋃_k  even
     k ≤  N_k(G(m,2)).

    Similarly, _od(G(m,2)) stabilizes by N∈^+ if
    
    _od(G(m,2)) = ⋃_k  odd
     k ≤  N_k(G(m,2)).

    Note that N is not unique.

By Theorem <ref>, we see that

    _k(G(m,2)) ⊆^k(G(m,2)).


Next we see that the fully minimal k-sets eventually capture all possible edges uv, u,v∈ V(G(m,2)). 
 
    Let m∈^+ with m≥ 5 and distinct u,v∈ V(G(m,2)). Then there exists k∈^+ such that uv∈_k(G(m,2)).


 The special case m=6 can easily be verified by direct inspection.
    For m 6, the proof examines, by symmetry, the three possible options for u and v to be either exterior or interior vertices. As the cases are similar, we give details only for the case where u and v are both exterior vertices. 

    First choose α∈^+, α≥ 3, so that 2^α-1 < m ≤ 2^α. After possibly relabeling, and also conflating _m with  when convenient, we may assume u=v_a and v=v_b with 0≤ a<b and 1≤ b-a ≤m/2. For b-a =1, we have uv ∈_2(G(m,2)) with Lemma <ref>, and for b-a =2, one easily checks uv ∈_1(G(m,2)). Thus, we can restrict ourselves to the case 3≤ b-a ≤m/2. Choose β∈^+, β≥ 2 so that 2^β-1 < b-a ≤ 2^β. Note that 2^β < 2(b-a)≤ m ≤ 2^α, thus β≤α -1. 

    We will look at walks π from v_a to v_b of the form
    
    (v_a, v_a+1, …, v_a+x,
            u_a+x, u_a+x+2, …, u_a+x+2y,
            v_a+x+2y, v_a+x+2y-1, …, v_b)

    with x,y∈ and a+x+2y ≥ b. Such a walk has length x+1+y+ 1+ (a+x+2y-b) = 2x +3y +2 -(b-a). We will require that
    
    2x +3y +2 -(b-a) = 2^β.

    Note that it can be verified that x+2y<m so that, in fact, π is always a path.

    Write c=2^β-2+ b-a≥ 2. If c≡ 0  3, use x=0 and y=c/3 and observe that this choice indeed satisfies a+x+2y ≥ b. In this case,
    we have
    
    π = (v_a,u_a, u_a+2, …, u_a+2y,
            v_a+2y, v_a+2y-1, …, v_b),

    and we claim that π is fully minimal. First, as 2^β < 2(b-a)≤ m, we have c=2^β-2+ b-a < 3/2 m and 2y= 2/3 c< m, and π is indeed a path. Moreover, for m 6, condition (2) of Definition <ref> is automatically satisfied, too, and π is a 2-walk of length β. If we relabel π as (w_0,w_1,…,w_2^β), it now suffices to show that there is no 
    2-walk from w_j· 2^i+1 to w_(j+1)· 2^i+1 of length i
    for all 1 ≤ i ≤β-1 and 0 ≤ j ≤ 2^β-i-1-1. 

    The argument breaks into four cases depending on the location of w_j· 2^i+1 and w_(j+1)· 2^i+1 with respect to exterior and interior vertices. As the arguments are similar, we only give details here for two representative cases.
    
    For the first case considered here, suppose that w_j· 2^i+1 and w_(j+1)· 2^i+1 are both exterior vertices, neither equal to w_0. 
    The exterior path between these two vertices has 2^i+1 edges with 2^i+1≤ 2y-(b-a). As y=1/3(2^β-2+(b-a)), it follows that 
    2^i+1≤2/3(2^β-2-1/2(b-a)) < 2^β, and i ≤β -2 ≤α -3.
    
    However, the shortest possible path between w_j· 2^i+1 and w_(j+1)· 2^i+1 would have at least either 2^i+2 edges going along interior vertices or m-2^i+1/2+2 edges by going in the opposite direction. The first possibility is too large to admit a 2-walk of length 2^i. Turning to the second possibility, the existence of a 2-walk of length 2^i would require m-2^i+1/2+2 ≤ 2^i so that m ≤ 2^i+2-4. Thus m < 2^i+2 and α≤ i+2, which is a contradiction. 

    For the second case considered here, suppose w_j· 2^i+1 and w_(j+1)· 2^i+1 are both interior vertices. 
    Then j≥ 1 and 2^i+2≤ (j+1)· 2^i+1≤ y+1 =  1/3(2^β-2+(b-a))+1 ≤1/3(2^β+1+1) < 2^β so that i≤β -3 ≤α -4. However, the shortest possible path between w_j· 2^i+1 and w_(j+1)· 2^i+1 has either 2^i+1 or m/2-2^i+1 edges. The first possibility is too large to allow a 2-walk of length 2^i. For the second possibility to work, we would need m/2-2^i+1≤ 2^i so that m≤ 2^i+2+2^i+1<2^i+3. Then α≤ i+3, which is a contradiction.
    
    Finally, the cases of c≡ 1 3 and c≡ 2 3 are done using x=2 and x=1, respectively. The details are similar and omitted.


Finally, we can calculate the metamour limit period and metamour limit set of G(m,2).
 
    Let m∈^+ with m≥ 5. Then G(m,2) has metamour limit period 2. 
    
    The metamour limit set consists of (V(G(m,2)),_ev(G(m,2))) and (V(G(m,2)),_od(G(m,2))), where _ev(G(m,2)) and _od(G(m,2)) stabilize by 2 ⌊ m/2 ⌋ +m-8. Moreover,  
    
    _ev(G(m,2)) = E(^2ℓ(G(m,2)))
 and 
    _od(G(m,2)) = E(^2ℓ+1(G(m,2)))

    for all sufficiently large ℓ∈. Finally, 
    
    _ev(G(m,2)) ∪_od(G(m,2)) = E(G(m,2)) ∪ E(G(m,2)).




    By Theorem <ref>, we see that _k(G(m,2)) ⊆ E(^k(G(m,2))). By Theorem <ref> and the fact that G(m,2) is finite, we see that   
    
    _ev(G(m,2)) ⊆ E(^2ℓ(G(m,2)))
 and
       
    _od(G(m,2)) ⊆ E(^2ℓ+1(G(m,2)))

    for all sufficiently large ℓ∈.    
    From Theorem <ref> and Lemma <ref>, we see that
    
    E(^2ℓ(G(m,2))) ∩ E(^2ℓ+1(G(m,2))) = ∅
 
    and
    
    _ev(G(m,2)) ∪_od(G(m,2)) = E(G(m,2)) ∪ E(G(m,2))

    so that, in fact, 
    
    _ev(G(m,2)) = E(^2ℓ(G(m,2)))
 and
       
    _od(G(m,2)) = E(^2ℓ+1(G(m,2)))

    for all sufficiently large ℓ∈.
    
    For the statement on stability, first observe that G(m,2) ∪G(m,2) has 2m2 = m(2m-1) edges, which group up into 2 ⌊ m/2 ⌋ +m equivalence classes with respect to index shift modulo m. For m 5, E(G(m,2)) and E((G(m,2))) consist of 3 and 6 of these classes, respectively. Moreover, by Theorem <ref>, for growing even and odd k, respectively, E(^k(G(m,2))) either stays the same or grows by adding one or several of these equivalence classes. The metamour iterates will stabilize if E(^k(G(m,2)))=E(^k+2(G(m,2))), which will happen for some k≥ 2 ⌊ m/2 ⌋ +m-8.





































    

    















    
    
    
    
    
















    














    




















































We end with a characterization for the connectedness of (G(m,j)). From Definition <ref>, observe that (G) is connected if and only if for each distinct u,v∈ V(G), there exists n∈^+ and a walk in G, (w_0,w_1,…,w_2n), with w_2i,w_2i+1,w_2(i+1) distinct  and w_2iw_2(i+1)∉E(V) for all 0≤ i ≤ n-1.
















    
















        












        





















 
    Let m,j ∈^+ with m ≥ 5 and j < m/2. Then (G(m,j)) is connected if and only if either
    
        
  * m is odd or
        
  * m and j are even.
    
    Otherwise, (G(m,j)) has two connected components.



    Let u,v∈ G(m,j) be distinct.   
    Consider first the case of odd m.

    If both u,v are exterior vertices, then moving either in a clockwise or counterclockwise manner around the exterior vertices will furnish a path of even length showing that u and v are connected in (G(m,j)). It remains to show that each interior vertex is connected to an exterior vertex in (G(m,j)). For this, use the path (u_i,u_i+j,v_i+j) for i∈_m.

    Now consider the case of m,j even. Following an argument similar to the one in the previous paragraph, it is immediate that the sets of vertices {v_i, u_i  |  i∈ 2_m} and {v_i, u_i  |  i∈ 2_m+1} are both connected in (G(m,j)). The path (v_1,v_2,u_2) finishes this case.

    Finally, consider the case of m even and j odd. Following again an argument similar to the one in the first paragraph, it is immediate that the sets of vertices {v_i, u_i+1 |  i∈ 2_m} and {v_i, u_i+1 |  i∈ 2_m+1} are both connected in (G(m,j)). However, as these two sets of vertices provide a 2-coloring of G(m,j), (G(m,j)) cannot be connected.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    




§ METAMOUR GRAPHS OF COMPLETE M-ARY TREES


In this section, we give a full description of the periodic behavior and limit set of the complete m-ary tree under the metamour operation.
From now on, for h,m ∈^+ with m≥ 2, we let T  T(h,m) denote the complete m-ary tree with height h, where the height is the number of levels below the root vertex of T.
Recall that the depth of a vertex is its distance from the root.
It turns out that the central role in our analysis is played by ^2(T).
We thus begin with some auxiliary lemmas relating to this graph.


    
    Let x,y ∈ V(T).
    Then xy ∈ E(^2(T)) if and only if d_T(x,y) = 4.



    
    Suppose that xy ∈ E(^2(T)).
    Then by Lemma <ref>, there exists a 2-walk π = (x, u, v, w, y) in T, in the sense of Definition <ref>; in particular, the vertices x, v and y are all distinct.
    Since T contains no cycles, it follows that xy ∉ E(T) and therefore u ≠ y and x ≠ w.
    Moreover, we must have u ≠ w because otherwise d_T(x,y) = 2, which means xy ∈ E((T)) and thus xy ∉ E(^2(T)), contradicting our supposition.
    Therefore π is a path. Since T contains no cycles, there is no shorter path from x to y, and thus d_T(x,y) = 4.
    Conversely, suppose that d_T(x,y) = 4.
    Then there is a fully minimal 2-walk of length 2 from x to y (in the sense of Definition <ref>), and so by Theorem <ref> we have xy ∈ E(^2(T)).


In order to describe the relative positions of vertex pairs, we introduce the following shorthand.
Given vertices x,y ∈ V(T),
there is a unique minimal path from x to y, consisting of a sequence of p upward steps followed by a sequence of q downward steps, with p,q ∈ such that p+q = d_T(x,y).
We abbreviate this minimal path as

    π_T(x,y) = (x, ↑^p, ↓^q, y).

For example, x and y are first cousins if and only if we have π_T(x,y) = (x, ↑^2, ↓^2, y); as another example, x is the great-grandchild of y if and only if π_T(x,y) = (x,↑^3,↓^0, y).

















        






























   






    
    Let T = T(h,m) with h ≥ 5, and let xy ∈ E(^2(T)).
    Then there exists z ∈ V(T) such that both xz and yz are in E(^3(T)).



    We need to find z such that d_^2(T)(x,z) = d_^2(T)(y,z) = 2.
    Equivalently, z must be distinct from x and y, and must be connected to x (and separately to y) by concatenating two length-4 paths in T; moreover, we must have d_T(x,z) ≠ 4 and d_T(y,z) ≠ 4.
    Since by hypothesis we have xy ∈ E(^2(T)), Lemma <ref> implies that d_T(x,y)=4.
    Therefore, there are three cases (up to symmetry) which must be checked:
    
    
        
  * If π_T(x,y) = (x,↑^4,↓^0,y), then we can take z such that π_T(x,z) = (x,↑^4,↓^2,z), as in Figure <ref>(A).
        
  * If π_T(x,y) = (x, ↑^3, ↓^1,y), then we can take z such that π_T(x,z) = (x,↑^4, ↓^4, z) as depicted in Figure <ref>(B), as long as x has depth ≥ 4.
        We can also take z such that π_T(x,z) = (x, ↑^2, ↓^4, z) as depicted in Figure <ref>(C), as long as x has depth ≤ h-2. 
        The tree T(h,m) admits at least one of these two possibilities if and only if h ≥ 5.

        
  * If π_T(x,y) = (x, ↑^2, ↓^2, y), then we can take z such that π_T(x,z) = (x, ↑^4, ↓^2, z) as in Figure <ref>(D), as long as x and y have depth ≥ 4.
        We can also take z such that π_T(x,z) = (x, ↑^2, ↓^0, z) as in Figure <ref>(E), as long as x and y have depth ≤ h-2.
        The tree T(h,m) admits at least one of these possibilities if and only if h ≥ 5. 





    
    Let T = T(h,m), where h ≥ 5.
    Suppose d_^2(T)(x,y) = 3. Then there exists z ∈ V(T) such that both xz and yz are in E(^3(T)) unless



x and y both have depth 1 in T with m = 2 and h ∈{5,6}.





        




        

    



    
We need to find a vertex z with the same properties described in the proof of Lemma <ref>.
    Up to symmetry, there are 15 relative positions for x and y such that d_^2(T)(x,y) = 3, and such that x and y do not both have depth 1 in T.
    (To determine these 15 positions, one need only check vertex pairs whose distance is a positive even integer which is at most 3 × 4 = 12.)
    In Table <ref>, we exhibit a choice of the desired vertex z for each of these 15 positions, using the shorthand in (<ref>).
    (Note that the vertex z described in the table may not be unique; rather, any z that satisfies the location given in the table has the desired property.)
    In each case, it is straightforward to verify (via diagrams like those in Figure <ref>) that both xz and yz belong to E(^3(T)).

    
    Suppose now that x and y both have depth 1 in T.
    If m > 2, then we observe that d_^2(T)(x,y) = 2. If m = 2 and h>6, then we can take z such that π_T(x,z) = (x,↑^1, ↓^7, z).
    If, however, m=2 and h ∈{5,6}, then d_^2(T)(x,y) = 3, and it is straightforward to verify that there is no vertex z with the desired property.






    
     Let T = T(h,m) with h ≥ 5.
    Then ^2(T) has two connected components, namely the vertices with even depth and the vertices with odd depth.
    The maximum of the diameters of these two connected components is ⌈ h/2 ⌉.



    It is clear that if d_T(x,y) = 4, then the depths of x and y have the same parity.
    Thus by Lemma <ref>, if xy ∈ E(^2(T)) then the depth of x and the depth of y have the same parity.
    
    Conversely, we claim that any two vertices x and y, whose depths have the same parity, are connected in ^2(T).
    To see this, observe that because T is a tree, there is a unique path in T between x and y, which necessarily has even length.
    If this length is divisible by 4, then we are done by Lemma <ref>.
    Thus, let us assume that the length is 4ℓ+2 for some ℓ∈, and that the path is given by (x,w_1,w_2,…,w_4ℓ+1,y). For ℓ>0, if w_4ℓ-1 is distinct from the root of the tree T, let z denote any neighbor of w_4ℓ-1 distinct from both w_4ℓ-2 and w_4ℓ. Then,
    
    (x,w_1,w_2,…,w_4ℓ-2,w_4ℓ-1,z,w_4ℓ-1,w_4ℓ,w_4ℓ+1,y)

    is a walk in T of length 4ℓ for which, starting with the vertex x, every fourth vertex is distance 4 from the previous vertex. Thus, the path (x,w_4,w_8,…,w_4ℓ-4,z,y) connects x and y in ^2(T). If w_3 is distinct from the root of the tree T, we can make a similar argument to show that x and y are connected in ^2(T). This leaves us to consider the following special cases:

        

    
        
  * Suppose that ℓ=1, and that w_3 is the root of the tree T. In this situation, x and y have both depth 3 and are connected in ^2(T) as depicted in Figure <ref>(A).
        
  * Suppose that ℓ=0, and that x and y have distinct depths. Without loss of generality, let us assume that x has the larger depth. Then, as long as x has depth ≥ 4, x and y are connected in ^2(T) as depicted in Figure <ref>(B). If x has depth ≤ h-2, an alternative connecting path is shown in Figure <ref>(C).
        
  * Suppose that ℓ=0, and that x and y have the same depth. Then, as long as x has depth ≥ 2, x and y are connected in ^2(T) as depicted in Figure <ref>(D). If x has depth ≤ h-4, an alternative connecting path is shown in Figure <ref>(E).
    
    Hence ^2(T) has exactly two connected components.
    
    The argument above also shows that if x and y are in the same connected component with d_T(x,y)≥ 8, then d_^2(T)(x,y) = ⌈ d_T(x,y)/4 ⌉.
    Therefore, since diam(T) = 2h, the maximum distance between connected vertices in ^2(T) is ⌈ h/2 ⌉.


    
    

To streamline the statement of our results, we partition the positive integers into segments S_i whose endpoints are consecutive powers of 2:

    S_i  (2^i-1, 2^i],      i = 0, 1, 2, …,

where we use the standard interval notation restricted to the integers.
In other words, we have

    S_i = { s ∈^+ |⌈log_2 s ⌉ = i}.

Note that S_0 = {1} and S_1 = {2}.



    Let i∈^+ with i ≠ 2.
    If i is even (resp., odd), then every element of S_i can be written as the sum of two (not necessarily distinct) elements in the union of S_1 (resp., S_0) and S_i-1.



    The statement is obviously true for i=1. Thus let i ∈^+ with i≥ 3.
    We have S_i = [2^i-1 + 1,   2^i] and S_i-1 = [2^i-2+1,   2^i-1].
    Since the sumset of S_i-1 is 
    
    {s+t | s,t ∈ S_i-1} = [2min S_i-1, 2max S_i-1] = [2^i-1 + 2, 2^i],

    we have proved the lemma for all elements of S_i except for 2^i-1+1.
    Now, if i is even, we complete the proof by writing 2^i-1 + 1 as the sum of 2 ∈ S_1 and 2^i-1-1 ∈ S_i-1. 
    Likewise, if i is odd, we complete the proof by writing 2^i-1 + 1 as the sum of 1 ∈ S_0 and 2^i-1∈ S_i-1.



    
    Let ℓ∈^+.
    Then every element of
    
    ⋃_0 ≤  i ≤ ℓ
     i ≡ ℓ  ( mod  2) S_i,

    except for 1 and 3 (which appear only when ℓ is even), can be written as the sum of two (not necessarily distinct) elements of 
    
    ⋃_0 ≤  i ≤ ℓ-1 
     i ≡ ℓ-1   ( mod  2) S_i.




    This follows immediately from Lemma <ref>. 
    
    
    Note that the sets S_0={1} and S_2={3,4} are excluded from Lemma <ref> which leads to the exceptional cases.


It turns out that the distances in ^2(T) are sufficient to completely describe the edges in every subsequent metamour graph of T.
The key to the proof of the following lemma is Corollary <ref> above, which will allow us always to split a path in ^2(T) into two subpaths of desired lengths.


    
    Let T = T(h,m) be the complete m-ary tree with height h ≥ 5.
    Let x,y ∈ V(T), with the exception of the case 
    
    depth x = depth y = 1,      m=2,      h ∈{5,6}.

    For k ≥ 2, we have
   
    xy ∈ E(^k(T)) ⟺ d_^2(T)(x,y) ∈  ⋃_0 ≤  i ≤  k-2
     i ≡  k  2    S_i ,

    where the sets S_i are defined in (<ref>).
    In the case (<ref>), the edge xy does not occur in ^k(T) for any k ≥ 2.



    We use induction on k.
    In the base cases k=2 and k=3, the theorem is true by definition, since S_0 = {1} and S_1 = {2}.
    
    Note that in the exceptional case (<ref>), we have d_^2(T)(x,y) = 3 (see the proof of Lemma <ref>), and indeed 3 does not belong to S_0 or S_1.

    As our induction hypothesis, assume that the theorem holds up to some value of k; we now show that it also holds for k+1.
    We first prove the “⟹” direction of the biconditional in the theorem.
    For ease of notation, in the rest of this proof we abbreviate
    
    d  d_^2(T)(x,y).

    Let xy ∈ E(^k+1(T)). Then xy ∉ E(^k(T)). Thus, by our induction hypothesis, d∉⋃_0 ≤  i ≤  k-2,  i ≡  k  2  S_i. Hence, we must have either d∈⋃_0 ≤  i ≤  k-3,  i ≡  k+1  2  S_i or d∈⋃_i≥ k-1  S_i.
     
    In the latter case, we claim that actually d ∈ S_k-1.
    To see this, recall that xy ∈ E(^k+1(T)) implies xz,yz ∈ E(^k(T)) for some z∈ V(T). 
    We have d_^2(T)(x,z), d_^2(T)(z,y) ≤max S_k-2 = 2^k-2 by induction hypothesis. 
    Hence, d≤ d_^2(T)(x,z)+d_^2(T)(z,y)≤ 2^k-1 by triangle inequality, which is the largest element of S_k-1.
    Thus, xy ∈ E(^k+1(T)) implies d∈⋃_0 ≤  i ≤  k-1,  i ≡  k+1  2  S_i, which proves the “⟹” direction in the theorem.

    To prove the converse, suppose that d∈⋃_0 ≤  i ≤  k-1,  i ≡  k+1  2  S_i.
    Then automatically xy ∉E(^k(T)) by induction hypothesis, and
    we must show that xy ∈ E(^k+1(T)).
    
    Assume for now that d ≠ 1,3.
    Then, by Corollary <ref>, where ℓ = k-1, the number d can be written as the sum of two (possibly equal) elements
    
    b,c ∈⋃_i ≤  k-2 
     i ≡  k   mod  2 S_i.

    Since b+c = d, there exists some z ∈ V(T) such that d_M^2(T)(x,z) = b and d_M^2(T)(z,y) = c.
    Moreover, by (<ref>) and the induction hypothesis, both xz and yz lie in E(^k(T)).
    Since xy is not an edge in ^k(T), we conclude that xy ∈ E(^k+1(T)), thereby proving the “⟸” direction in the theorem (as long as d ≠ 1, 3).
    
    It remains to treat the cases where d∈{1,3}.
    In either case, note that k is odd.
    By Lemmas <ref> and <ref> (for d=1 and d=3, respectively), there exists a vertex z ∈ V(T) such that both xz and yz are in E(^3(T)), except in the exceptional case (<ref>).
    Hence, outside of (<ref>), since k is odd, it follows that both xz and yz are in E(^k(T)).
    Therefore we have xy ∈ E(^k+1(T)), which completes the proof.
    In the case (<ref>), by Lemma <ref> there is no such vertex z, and so the edge xy does not occur in ^4(T), nor in any successive metamour graph as can easily be verified by direct inspection.
    

We now give the main result of this section, showing that T(h,m) has metamour limit period 2, with a pre-period of ⌈log_2 h⌉:



    Let T = T(h,m) be the complete m-ary tree with height h ≥ 5.
    Then we have ^k(T) = ^k+2(T) if and only if k ≥⌈log_2 h ⌉.
    In this range, the two graphs in the metamour limit set of T are given by the edge criterion
    
    xy ∈ E(^k(T)) ⟺⌈log_2 d_^2(T)(x,y) ⌉≡ k mod 2

    for all x,y ∈ V(T), with the exception of the case where depth x = depth y = 1 with m=2 and h ∈{5,6}; in that case, xy is not an edge in either metamour limit graph.
    
    
    
    
    
    
    



    It is clear from Lemma <ref> that if k ≥ 2, then xy ∈ E(^k(T)) implies xy ∈ E(^k+2(T)).
    By Lemma <ref>, the maximum distance between two connected vertices in ^2(T) is ⌈ h/2 ⌉.
    By (<ref>), the smallest integer i such that ⌈ h/2 ⌉∈ S_i is given by
    
    ⌈log_2 ⌈ h/2 ⌉⌉ = ⌈log_2 h ⌉ - 1.

    Therefore, if d_M^2(T)(x,y) = ⌈ h/2 ⌉, then by Lemma <ref>, the quantity in (<ref>) is the unique value of k such that xy ∉E(^k(T)) but xy ∈ E(^k+2(T)). 
    Hence we have ^k(T) = ^k+2(T) if and only if k is strictly greater than (<ref>).


Finally, for the sake of completeness, we describe the metamour graphs in the cases where h < 5.
The following behavior can be verified directly by drawing the first few metamour graphs, and so we leave the details to the reader:



    
  * Let T = T(1,m).
    Then (T) = K_m ∪ K_1, and for all k ≥ 2, we have ^k(T) = K_m+1.

    
  * Let T = T(2,m).
    Then (T) = K_m ∪ Wd(m,m), where Wd(m,m) is the windmill graph obtained by taking m copies of K_m with a common vertex.
    We then have ^2(T) = (K_m)^∇ m∪K_m+1, followed by ^3(T) = (K_m)^∪  m∪K_m+1.
    (The notation G^∇ m denotes the join of m copies of G.)
    For all k ≥ 4, we have ^k(T) = K_m^2 + m + 1.
    
  * Let T = T(3,m).
    We have ^5(T) = (K_m)^∪  m^2∪K_m^2 + m + 1, and so ^k(T) = K_m^3+m^2+m+1 for all k ≥ 6.
    
  * Let T = T(4,m).
    Then T has metamour limit period 2, with the metamour limit set as given in Theorem <ref>.
    If m=2, then this periodic behavior begins at k = 4.
    If m ≥ 3, then this periodic behavior begins at k = 6.
    

    













    
    






abbrvnat


