Infinite self-interchange graphs
Benjamin L. Schwartz · Pacific Journal of Mathematics · 1969
Let G be an unoriented graph.Let I(G) denote the interchange graph of G. lfG = I(G), we shall say G is a selfinterchange graph (SIG).If for some positive integer m ^ 1, we have I m (G) = G, we shall say G is eventually self interchange (ESIG).This paper extends previous results to characterize all finite degree SIG's and ESIG's, (loops and parallel edges permitted), finite or infinite, connected or disconnected.It will be seen that when infinite graphs are considered, several earlier results change.For example, there are ESIG's which are not SIG's; and loop-free SIG's which are not regular.1* Terminology• In this paper, we shall use the unmodified term graph to mean locally finite s-graph with loops permitted.The case of parallel edges forbidden will be denoted restricted graph.An elementary chain will be called a line.The interchange operation is so defined that the interchange of a loop is again a loop 1 .A loop is considered a complete 1-graph 1 .A loop contributes 1 to the degree of its vertex 1 .If a graph G has two parallel edges, the corresponding two vertices of I(G) are likewise joined by two parallel edges 1 .DEFINITION.Let G be a graph.Suppose the components of G are {Gi I i e A} where A is some index set.We shall say that H is component-subgraph (hyphinated), or C-subgraph for short, if and only if components of H are {Gi \ i e B) where B is some subset of A.Similarly, if G' and G" are disjoint graphs whose components are {Gi I i e A} and {G< | i e B) respectively, where A and B are disjoint index sets, we say the graph consisting of the components of G' and the components of G", {G { | i e A U B) is the C-union of G' and G".Where context makes it clear, we shall sometimes write this using the ordinary union symbol \J, e.g.G' U G".2* Preliminaries* It has sometimes been asserted that G is a SIG if and only if G is regular of degree 2 [8], [12].This assertion is valid only if the hypothesis include that G is loop-free and finite.Nonregular SIG's with loops have been known for some time [5].The author has elsewhere [17] characterized all finite connected s-graph SIG's (loops permitted).We restate the result here for later use: all