BIPARTITE STEINHAUS GRAPHS WITH CONNECTIVITY TWO
Dae-Keun Lim · East Asian Mathematical Journal · 2009
Abstract. In this paper, we investigate the generating strings and thenumber of 2-(edge)connected bipartite Steinhaus graphs. 1. IntroductionLet T = a 11 a 12 a 1n be an n-long string of zeros and ones with a 11 =0. The Steinhaus graph G;generated by T has as its adjacency matrix, theSteinhaus matrix, A(G) = [a ij ] which is obtained from the following, called theSteinhaus property:a ij =8<:0 if 1 i= j n;a i 1;j 1 + a i 1;j (mod 2) if 1 <i<jn;a ji if 1 j<in.In this case, Tis called the generating string of G. It is obvious that there areexactly 2 n 1 Steinhaus graphs of order n. The vertices of a Steinhaus graph areusually labeled by their corresponding row numbers. In Figure 1, the Steinhausgraph generated by 00110110 is pictured. For each 1 in, the n-long stringa i1 a ii a i;i+1 a i;n in A(G) generates A(G) by Steinhaus property. Thus,the generating string is the general generating string with respect to 1.The partner P(G) of Gis the Steinhaus graph generated by the reverse ofthe last column of A(G), i.e., a