# Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders

Authors: Salah Al-Addasi; Hasan Al-Ezeh
Journal: International Journal of Mathematics and Mathematical Sciences
 (2008)

---

## Abstract

We provide a process to extend any bipartite diametrical graph of diameter 4 to anS-graph of the same diameter and partite sets. For a bipartite diametrical graph of diameter 4 and partite sets
U and W, where 2m=|U|≤|W|, we prove that 2m
is a sharp upper bound of |W| and construct an S-graph G(2m,2m)
in which this upper bound is attained, this graph can be viewed as a generalization of the Rhombic Dodecahedron. Then we show that for any m≥2, the graph G(2m,2m)  is the unique (up to isomorphism) bipartite diametrical graph of diameter 4 and partite sets of cardinalities
2m and 2m, and hence in particular, for m=3,
the graph G(6,8)
which is just the Rhombic Dodecahedron is the unique (up to isomorphism) bipartite diametrical graph of such a diameter and cardinalities of partite sets. Thus we complete a characterization of  S-graphs of diameter 4 and cardinality of the smaller partite set not exceeding 6. We prove that the neighborhoods of vertices of the larger partite set of
G(2m,2m) form a matroid whose basis graph is the hypercube Qm. We prove that any  S-graph of diameter 4 is bipartite self complementary, thus in particular
G(2m,2m). Finally, we study some additional properties of  G(2m,2m) concerning the order of its automorphism group, girth, domination number, and when being Eulerian.


---

## Body

## 1. Introduction

There are frequent occasions in which graphs with a lot of symmetries are required.
One such family of
graphs is that ofS-graphs. S-graphs form a special type of
symmetric diametrical graphs which are one of the most interesting classes of
diametrical graphs, see [1, 2], as well as of k-pairable graphs
introduced in [3]. Diametrical graphs were studied under different names, see
[2, 4–6].All graphs we consider are assumed to be finite, connected, and to have no
loops or multiple edges. For undefined notions and terminology, we use [7].Two vertices,u, and v of a nontrivial connected graph G are said to be diametrical if d(u,v)=diam(G). A nontrivial connected graph G is called diametrical if each vertex v of G has a unique diametrical vertex v¯,
the vertex v¯ is called the buddy of v,
see [4] and [5]. A diametrical graph G is called minimal if removing any edge
of G produces a graph which is not diametrical of
the same diameter. A diametrical graph G in which u¯v¯∈E(G), whenever uv∈E(G), is called harmonic. A diametrical graph G is called maximal if there is no
diametrical graph H with the same vertex set and diameter as G such that E(H) contains E(G) properly. A diametrical graph G is called symmetric if d(u,v)+d(v,u¯)=diam(G) for all u,v∈V(G),
see [2], that is, a diametrical graph G is symmetric if and only if V(G)=I(u,u¯) for any u∈V(G),
where I(u,u¯) denotes the interval of G consisting of all vertices on shortest (u,u¯)-paths, see [5]. A symmetric
diametrical graph is called an antipodal graph, and a bipartite
antipodal graph is called an S-graph, see [1].It is shown in [8] that the concepts of symmetric and maximal are
equivalent in the class of bipartite diametrical graphs of diameter 4.
We provide a process to extend any given bipartite diametrical graph of
diameter 4 to a maximal diametrical graph and hence an S-graph
of the same diameter and partite sets.For a bipartite diametrical graph of diameter4 and partite sets U and W with |U|≤|W|,
it is given in [8] that |W|≤(|U|(1/2)|U|).
In this paper, we improve this upper bound by proving that |W|≤2m,
where m=(1/2)|U|.
To show that 2m is a sharp upper bound, we construct a
bipartite diametrical graph, which we denote by G(2m,2m),
of diameter 4 in which this maximum value of |W| is attained. In particular, when m=3,
the graph G(2m,2m) is indeed just the Rhombic Dodecahedron which
is sometimes also called the Rhomboidal Dodecahedron, see [9]. The Rhombic
Dodecahedron appears in some applications in natural sciences, see, for
example, [10, 11]. It is the convex polyhedron depicted in Figure 1 and
can be built up by placing six cubes on the faces of a seventh, taking the
centers of outer cubes and the vertices of the inner as its vertices, and
joining the center of each outer cube to the closer four vertices of the inner.
The number |U| is a sharp lower bound of |W| which is previously known through a graph
constructed in [8], which we denote in this paper by G(2m,2m). For m=3,
it is proven in [12] that, up to isomorphism, the graph G(2m,2m)=K2×C6 is the unique symmetric diametrical graph of
order 12 and diameter 4. For larger m, G(2m,2m) needs not be the unique symmetric diametrical bipartite graph of
diameter 4. We give an example of an S-graph with the same cardinalities
of partite sets as those of G(8,8) but not isomorphic to G(8,8). On the other hand, we prove that, for any m≥2,
the graph G(2m,2m) is not only the unique (up to isomorphism) S-graph
of diameter 4 and partite sets of cardinalities 2m and 2m, but also is the unique bipartite diametrical
graph of such a diameter and partite sets. Consequently, the Rhombic
Dodecahedron is the unique diametrical graph of diameter 4 and maximum order where the smaller partite
set has cardinality 6.
Joining this to the main result of [12], our result about the upper bound of the cardinality of the larger partite
set completes a characterization of S-graphs
of diameter 4 and cardinality of the smaller partite set not
exceeding 6.Figure 1
The Rhombic Dodecahedron.Matroids constitute an important unifying structure which has many
equivalent definitions. According to one of these definitions, amatroid on a finite set I is a collection β of subsets of I, called bases, which satisfies the
exchange property: for all A,B∈β and a∈A−B, there exists b∈B−A such that (A−{a})∪{b}∈β.
It is well known that all the bases
of a matroid have the same cardinality. The basis graphG(β) of a matroid β is the graph whose vertices are the bases of
the matroid, where two vertices A,B are adjacent if they differ by a single
exchange, that is, if the symmetric difference (A−B)∪(B−A) has exactly two elements. The basis graphs
faithfully represent their matroids, see [13] and references therein; thus
studying the basis graph amounts to studying the matroid itself. We prove that
the neighborhoods of the vertices of the larger partite set of G(2m,2m) form a matroid whose basis graph is the
hypercube Qm.
The hypercubes together with the Rhombic Dodecahedra appear as the cells in the
tight span of a totally split-decomposable metric which is used in the field of
phylogenetic analysis, see [14].A bipartite graphG with partite sets U and W is called bipartite self complementary if G is a subgraph of K|U|,|W| which is isomorphic to its complement K|U|,|W|−E(G) with respect to the complete bipartite graph
with the same partite sets, see [15]. We show that the graphs G(2m,2m) and G(2m,2m) are bipartite self complementary and study
some of their properties concerning girth, domination number, order of
automorphism group, and when being Eulerian.


## 2. A Sharp Upper Bound of the Cardinality of the Larger Partite Set

One basic property of any bipartite
diametrical graph of even diameter is that each of the partite sets has an even
number of elements, as stated in Lemma2.1, see [8].Lemma 2.1.
IfG is a bipartite diametrical graph of even
diameter d and partite sets U and W, then for each v∈V, both v and v¯ belong to the same partite set, and hence |U| and |W| are even.In particular, whendiam(G)=4,
each partite set of G consists of a vertex v,
its buddy v¯, and those vertices equidistant to v and v¯.It is shown in [2] that symmetric diametrical graphs form a proper
special class of maximal diametrical graphs. But the two concepts coincide in
the class of bipartite diametrical graphs of diameter 4 according to the following fact which was
proven in [8].Lemma 2.2.
LetG be a bipartite diametrical graph of diameter 4. Then the following are equivalent:
(i)
G is maximal in the class of bipartite
diametrical graphs with the same partite sets as G;(ii)
G is maximal;(iii)
G is symmetric.The following theorem includes a process to extend any given bipartite
diametrical graph of diameter4 to a bipartite diametrical graph of the same
diameter and partite sets, which is maximal in the class of bipartite
diametrical graphs with the same partite sets, and hence, by the previous
lemma, is an S-graph.Theorem 2.3.
LetG be a bipartite diametrical graph of diameter 4 and partite sets U and W. Then, the following hold:
(i)
ifu∈U and w∈W such that the set {u,u¯,w,w¯} of vertices is independent, then the graph G+uw is bipartite diametrical of the same diameter
and partite sets as G;(ii)
ifuw∈E(G) but u¯w¯∉E(G), then the graph G+u¯w¯ is bipartite diametrical of the same diameter
and partite sets as G;(iii)
ifH is a graph obtained from G by repeated applications of (i) and (ii) until
none of them is applicable, then H is an S-graph of the same diameter and
partite sets as G.Proof.
(i) Assume to the contrary thatG+uw is either not diametrical or has diameter less
than 4. Then there exists a vertex v∈V(G) such that dG+uw(v,v¯)<4.
But, since G+uw is also bipartite with the same partite sets
as G and both v,v¯ belong to the same part of V(G),
then dG+uw(v,v¯) is even. Hence dG+uw(v,v¯)=2.
Thus there exists a (v,v¯)-path P in G+uw containing the new edge uw and having length 2. Then either {v,v¯}={u,u¯} and P is uwu¯ or {v,v¯}={w,w¯} and P is w¯uw,
which gives a contradiction in both cases since wu¯,w¯u∉E(G+uw).
Therefore, G+uw is a diametrical graph of diameter 4.
(ii) Letuw∈E(G) such that u¯w¯∉E(G) with u∈U and w∈W, where U and W are the partite sets of G. Then u¯w∉E(G) because otherwise dG(u,u¯)=2,
which is not the case. Similarly, uw¯∉E(G).
Now, we will show by contradiction that G+u¯w¯ is diametrical of diameter 4. Assume not, then
there exists a vertex v∈V(G) such that dG+u¯w¯(v,v¯)<4.
Clearly, G+u¯w¯ is bipartite with the same partite sets as G since u¯∈U and w¯∈W.
But both v and v¯ belong to the same part of V(G),
hence dG+u¯w¯(v,v¯) is even, and so dG+u¯w¯(v,v¯)=2.
Thus, there exists a (v,v¯)-path P in G+u¯w¯ containing the new edge u¯w¯ and having length 2. Consequently, either {v,v¯}={u,u¯} and P is u¯w¯u or {v,v¯}={w,w¯} and P is wu¯w¯,
which gives a contradiction in both cases since uw¯,u¯w∉E(G+u¯w¯).
Therefore, G+u¯w¯ is bipartite diametrical of diameter 4.
(iii) LetH be a graph obtained from G by
addition of edges according to (i) or (ii) until none of them can be
applied. By Lemma 2.2,
it would be enough to show that H is maximal in the class of bipartite
diametrical graphs of diameter 4 and partite sets U and W. Assume to the contrary that there exist two
nonadjacent vertices u∈U and w∈W of H such that H+uw still diametrical of diameter 4. Then, since (ii) is no more applicable on H, we have u¯w¯∉E(H). But also (i) is not applicable on H, so the set {u,u¯,w,w¯} is not independent, therefore either uw¯∈E(H) or u¯w∈E(H). Consequently, either dH(w,w¯)=2 or dH(u,u¯)=2, a contradiction.The only bipartite diametrical graph of diameter4 in which the smaller partite set has
cardinality less than 6 is the 8-cycle as Lemma 2.4 (proven in [8]) says.Lemma 2.4.
IfG is a bipartite diametrical graph of diameter 4
and partite sets U and W with |U|≤|W|,
then |U|≥6 unless G=C8.For a bipartite diametrical graph of diameter 4 and partite setsU and W with |U|≤|W|, we have |U|≠2,
and whenever |U|=4,
we must have |W|=4.
It was shown in [8] that if |U|≥6,
then |W|≤(2mm), where  m=(1/2)|U|.
Thus for |U|=6,
we have |W|≤20.
This is not a sharp upper bound, as shown at the end of this section. In order
to obtain a sharp upper bound, we start by the following lemma.Lemma 2.5.
Letu and v be distinct vertices of a diametrical graph G of diameter d≥3.
Then N(u)⊈N(v).Proof.
Ifu=v¯,
then N(u)∩N(v)=ϕ since d(u,v)≥3.
Suppose that u≠v¯ and assume to the contrary that N(u)⊆N(v).
Any shortest path joining v¯ and u must include a vertex from N(u);
let x be such a vertex in such a path. Then d(v¯,u)=d(v¯,x)+d(x,u)=d(v¯,x)+1. But x∈N(u)⊆N(v) and v is the only vertex of G at distance d from v¯,
hence d(v¯,x)=d−1.
Therefore, d(v¯,u)=(d−1)+1=d, contradicting the uniqueness of the buddy
vertex of    v¯.In particular, two distinct vertices in a diametrical graph of diameter
at least 3 cannot have the same neighborhood.Before tending to give an upper bound of|W|,
let us recall the following fact proven in [8].Lemma 2.6.
Every vertexv of an S-graph G of diameter 4
is adjacent to exactly half of the vertices in the partite set of G not containing v.We are now in a position to prove our improvement of the upper bound of|W|.Theorem 2.7.
LetG be a bipartite diametrical graph of diameter 4
and partite sets U and W, where 2m=|U|≤|W|. Then, |W|≤2m.Proof.
By Theorem2.3, there exists
an S-graph H with the same diameter and partite sets
as G which has G as a subgraph. Then, by Lemma 2.6, each
vertex w∈W has exactly m neighbors in U.
Clearly, NH(w) cannot contain a vertex and its buddy. But
Lemma 2.5 implies that the |W| sets NH(w), w∈W are mutually distinct. Hence, |W| must be less than or equal to the number of
ways of choosing single representatives from each of m two-element sets; clearly that number is 2m.Now, ifG is a bipartite diametrical graph of
diameter 4 and partite sets U and W, where |U|≤|W|, then by Lemma 2.1, |U|=2m for some positive integer m. Since diam(G)=4, we must have m≥2. In the next section, we will construct for
each integer m≥2 a bipartite diametrical graph of
diameter 4 and partite sets U and W with |U|=2m and |W|=2m, which is the maximum possible cardinality
of W according to the previous theorem.
Consequently, the upper bound of |W| given in Theorem 2.7 is indeed sharp.


## 3. Constructing the GraphG(2m,2m) with Maximum Cardinality of the Larger Partite Set

For a bipartite diametrical graph of diameter4 and partite sets U and W with 2m=|U|≤|W|, an obvious lower bound of |W| is 2m. An S-graph of diameter 4 and partite sets with equal cardinalities was
constructed in [8] as follows.Lemma 3.1.
For any integerm≥2, the graph G whose vertex set is the disjoint union U∪W, where U={u1,u¯1,u2,u¯2,…,um,u¯m} and W={w1,w¯1,w2,w¯2,…,wm,w¯m}, and edge set is
(3.1)E(G)={uiwt:1≤i≤m,1≤t≤m+1−i}∪{uiw¯t:1≤i≤m,m+1−i<t≤m}∪{u¯iw¯t:1≤i≤m,1≤t≤m+1−i}∪{u¯iwt:1≤i≤m,m+1−i<t≤m}
is an S-graph of diameter 4.We will denote the graphG in Lemma 3.1 by G(2m,2m).
The graph G(8,8) is depicted in Figure 2(a).Two nonisomorphicS-graphs with minimum |W|.
Any two vertices of H at distance 2 from each other have exactly 2
common neighbors.
(a)(b)The next theorem provides an example of a bipartite diametrical graph of diameter4 and partite sets U and W with |U|≤|W| in which the maximum possible value of |W| given in Theorem 2.7 is attained.Theorem 3.2.
Suppose thatm>1 is an integer. There is a unique S-graph
of diameter 4 with partite sets U, W satisfying |U|=2m and |W|=2m.Proof.
LetU={u1,u1*,…,um,um*} and W={w1,…,w2m}. By Lemma 2.6
and the proof of Theorem 2.7
there is only one way to make an S-graph of diameter 4 with partite sets U, W and with ui and ui* being buddies, i=1,…,m: put the wj into one-to-one correspondence with the 2m different sets S={u1′,…,um′} in which ui′ is one of ui, ui* for each i=1,…,m, and define adjacency by setting N(wj)=S if wj corresponds to S in the one-to-one correspondence. It is
straightforward to see that the graph so defined is an S-graph of diameter 4; for each w in W, the buddy of w is the vertex in W whose set of neighbors is U−N(w).We will denote the graph constructed in the proof of Theorem3.2 by G(2m,2m).The following fact follows immediately from the constructions of the
graphsG(2m,2m) and G(2m,2m).Corollary 3.3.
For any integerm≥2, if G is a bipartite diametrical graph of
diameter 4 and partite sets U and W, where 2m=|U|≤|W|, then 2m≤|W|≤2m, where both inequalities are sharp.Example 3.4.
Form=3,
the graph G(2m,2m)=G(6,8) which we have already constructed is indeed the Rhombic Dodecahedron
depicted in Figure 1.


## 4. Some Properties of the GraphsG(2m,2m) and G(2m,2m)

We have seen in the previous section that for any integerm≥2 and partite sets U and W with 2m=|U|≤|W|, the graph G(2m,2m) is a bipartite diametrical graph of diameter 4 and such partite sets with minimum possible
order, while G(2m,2m) is one with maximum possible order.Now we will show that the graphG(2m,2m) is always included within the graph G(2m,2m),
recall that a subgraph H of G is isometric if dG(u,v)=dH(u,v) for all u,v∈V(H),
see [16].Theorem 4.1.
For any integerm≥2, the graph G(2m,2m) has an isometric subgraph isomorphic to G(2m,2m).Proof.
LetU={u1,u¯1,u2,u¯2,…,um,u¯m} and W={w1,w2,…,w2m} be the partite sets of the graph G(2m,2m).
Then, by the construction of G(2m,2m), for each i=1,2,…,m,
there exists a unique vertex yi∈W such that N(yi)={ui:1≤i≤m+1−i}∪{u¯i:m+1−i<i≤m}, and hence N(y¯i)={u¯i:1≤i≤m+1−i}∪{ui:m+1−i<i≤m}. Then,the set of vertices U∪{y1,y¯1,y2,y¯2,…,ym,y¯m} induces a subgraph H of G(2m,2m) isomorphic to G(2m,2m). Obviously, the buddy of a vertex of H in H is precisely its buddy in G(2m,2m). To show that H is isometric, let x and z be any two distinct vertices of H. If x=z¯ or xz∈E(H), then dH(x,z)=dG(2m,2m)(x,z). So suppose that x≠z¯ and xz∉E(H). Then it is clear that dH(x,z)=dG(2m,2m)(x,z)=2 when both x and z belong to the same partite set of H. Thus let x and z be in different partite sets of H, say x∈U and z∈WH={y1,y¯1,y2,y¯2,…,ym,y¯m}. Then xz∉E(G(2m,2m)) for otherwise we would have NG(2m,2m)(z)⊇NH(z)∪{x} which contradicts the fact that degG(2m,2m)z=m.
Then, dH(x,z)=dG(2m,2m)(x,z)=3. Therefore H is an isometric subgraph of G(2m,2m).The Rhombic Dodecahedron and the even cyclesC2n(n≥2) are minimal diametrical graphs, while the
graph K2×C6 is not, for if we remove an edge e corresponding to K2,
then the obtained graph (K2×C6)−e is again diametrical of the same diameter.
Notice also that the graph K2×C6 is just G(6,6), which means that G(2m,2m) need not be minimal. But the graph G(2m,2m) is minimal diametrical as the next result
says.Theorem 4.2.
For any integerm≥2, if H is an S-graph of diameter 4 and partite sets of cardinalities 2m and 2m, then H is a minimal diametrical graph.Proof.
By Theorem3.2, the graph H is isomorphic to G(2m,2m). Let uw be an edge of G=G(2m,2m),
where u∈U and w∈W. Then NG−uw(w)=NG(w)−{u}, NG(w¯)=U−NG(w), and u¯∈NG(w¯). Let x∈W be the vertex whose neighborhood in G is NG(x)=(NG(w¯)−{u¯})∪{u}.
Then NG−uw(x)∩NG−uw(w)=ϕ. Hence, dG−uw(w,x)≠2. But dG−uw(w,x) is even, so dG−uw(w,x)≥4. Clearly x≠w¯ since u∉NG(w¯). Therefore, x and w¯ are two distinct vertices with dG−uw(w,x)≥4 and dG−uw(w,w¯)≥4, which implies that G−uw is not diametrical of diameter 4. Since uw was an arbitrary edge of G(2m,2m), the graph H which is isomorphic to G(2m,2m) is minimal.Now we can improve Theorem3.2and show that the graph G(2m,2m) is not only the unique (up to
isomorphism) S-graph of
diameter 4 and partite sets of cardinalities 2m and 2m, but also the unique (up to isomorphism)
bipartite diametrical graph of such a diameter and partite sets.Theorem 4.3.
For any integerm≥2, if G is a bipartite diametrical graph of
diameter 4 and partite sets of cardinalities 2m and 2m, then G is isomorphic to G(2m,2m).Proof.
LetG be a bipartite diametrical graph of
diameter 4 and partite sets UG and WG with |UG|=2m and |WG|=2m. In view of Theorem 3.2, it would be enough to
show that G is symmetric. So, assume to the contrary that G is not symmetric. Then, by Theorem  2.3, the
graph G is a proper subgraph of an S-graph H of the same diameter and partite sets as G. Let uw∈E(H)−E(G). Then G⊆H−uw⊆H,
and hence for any x,y∈V(G), we have dG(x,y)≥dH−uw(x,y)≥dH(x,y). Therefore, H−uw is diametrical of the same diameter and
partite sets as G and H, which contradicts the minimality of H implied by the previous theorem.The following characterization of the Rhombic DodecahedronG(6,8) is a direct consequence of Theorem 4.3
and Theorem 2.7.Corollary 4.4.
The Rhombic Dodecahedron is the unique (up to isomorphism) bipartite
diametrical graph of diameter 4 and partite setsU and W, where 6=|U|<|W|.According to [12], if G is an S-graph of order n and diameter 4 with partite sets U and W such that G≠C8, then n≥12. Moreover, if n=12,
then |U|=|W|=6.
It is also shown in [12] that K2×C6 is the unique (up to isomorphism) symmetric
diametrical graph of order 12 and diameter 4 and hence in particular the unique S-graph of such an order and diameter. The previous corollary shows that
the Rhombic Dodecahedron is not only the unique (up to isomorphism) S-graph
of order 14 and diameter 4, but also the unique (up to isomorphism) bipartite
diametrical graph of such an order and diameter. Combining these results with
Lemma 2.4, we can completely
characterize the S-graphs of
diameter 4 and cardinality of the smaller partite set
not exceeding 6.Corollary 4.5.
LetG be an S-graph of diameter 4 and
cardinality of the smaller partite set not exceeding 6. Then G is isomorphic to one of the graphs: C8, K2×C6 and the Rhombic Dodecahedron.In the set of bipartite diametrical graphs of diameter4 and partite sets U and W with 2m=|U|≤|W|, although the graph G(2m,2m) is the unique (up to isomorphism) with maximum order, the graph G(2m,2m) needs not be the only one with minimum order,
for example, the graphs K2×C6=G(6,6) and (K2×C6)−e, where e is an edge correspoding to K2, both have minimum order. Even under the
condition of being symmetric, although G(6,6) was proven in [12] to be the only one, G(2m,2m) in general needs not be unique, for example, G(8,8) and the graph H of diameter 4 in Figure 2 are nonisomorphic S-graphs with
minimum order.Now we will prove that the set of all neighborhoods of vertices of the
larger partite set in the graphG(2m,2m) forms a matroid on the smaller partite set,
and determine its basis graph.Theorem 4.6.
LetU and W be the partite sets of G(2m,2m) with cardinalities 2m and 2m,
respectively. Then β={N(w):w∈W} forms a matroid on U whose basis graph is the hypercube Qm.Proof.
LetN(wi),N(wj) be two elements of β with a∈N(wi)−N(wj).
Then a¯∈N(wj).
Thus the set S=(N(wi)−{a})∪{a¯} has exactly m elements and contains no pair of diametrical
vertices. So by the construction of G(2m,2m),
there exists a vertex wk∈W such that N(wk)=S.
Therefore, (N(wi)−{a})∪{a¯}∈β and hence β is a matroid.
Now to determine the basis graph
of β, let N(wj) be a base of the matroid β obtained from a base N(wi) by a single exchange. Then N(wj)=(N(wi)−{a})∪{b} for some a∈N(wi) and some b∉N(wi).
But the set N(wj) contains exactly one of a,a¯.
Then b must be a¯.
Therefore, a single exchange is precisely replacing a vertex by its buddy,
which means that two vertices in G(β) are adjacent if and only if one of them can be
obtained from the other by replacing a vertex from U by its buddy. Now since U={u1,u¯1,u2,u¯2,…,um,u¯m},
we can represent each vertex N(w) of G(β) by a binary string r1r2⋯rm, where for i=1,2,…,m, we put
(4.1)ri={0,ui∈N(w)1,u¯i∈N(w),
thus two vertices of G(β) are adjacent if and only if their binary representations
differ at exactly one place. This is just the binary representation of the
hypercube Qm.It is shown in [8] that G(2m,2m) has exactly 8m automorphisms. This indicates that G(2m,2m) has a lot of symmetry. The next result reflects
the higher symmetry G(2m,2m) possesses.Theorem 4.7.
For any integerm≥3, the automorphism group Aut(G(2m,2m)) has order 2mm!.Proof.
Letf be an automorphism of G(2m,2m). Then, since f preserves degrees of vertices and |U|≠|W|, it follows by Lemma 2.6 that the vertex f(w1)=w must belong to W. Then f(N(w1))=N(w), and hence since f preserves distances between vertices, we must
have f(u)=f(u¯)¯ for every vertex u∈U−N(w1)=N(w¯1). Now for any vertex x∈W−{w1}, by the construction of G(2m,2m), there exists a unique vertex y∈W such that N(y)=f(N(x)) and hence f(x)=y. This gives an automorphism f of G(2m,2m). Thus an automorphism of G(2m,2m) is completely defined by specifying the image
of every vertex in the closed neighborhood N[w1]. From the proof above, the image of w1 can be any vertex from W, and the set of images of the vertices
from N(w1) must only be the set of neighbors of f(w1). This implies that we have exactly 2m ways to choose f(w1) and then m! ways to choose the set of images of the
vertices from N(w1). Therefore, G(2m,2m) has exactly 2mm! automorphisms.One can easily verify that theS-graphs of diameter  4 and
order at most 14, already characterized
in Corollary 4.5, are bipartite self complementary.
The following result assures that this is the case for any S-graph of diameter 4.Theorem 4.8.
IfG is an S-graph
of diameter 4, then G is bipartite self complementary.Proof.
LetU={u1,u2,…,uk,u¯1,u¯2,…,u¯k} and W={w1,w2,…,wt,w¯1,w¯2,…,w¯t} be the partite sets of G which is a subgraph of K2k,2t. Then, by Lemma 2.6, each vertex x from U is adjacent to exactly half of the vertices
of W, and x¯ is adjacent to the other half. Thus, the
one-to-one correspondence ϕ from V(G) to V(K2k,2t−E(G)), which fixes every vertex in W and sends every vertex in U to its buddy,  preserves adjacency.Consequently, bothG(2m,2m) and G(2m,2m) are bipartite self complementary.Finally, we close this section by the following result including some
properties ofG(2m,2m) and G(2m,2m) concerning girth, domination number, and
being Eulerian.Theorem 4.9.
(i) The girth of each of the
graphsG(2m,2m) and G(2m,2m), where m≥3, is  4; while the graph G(4,4) has
girth 8.
(ii) The domination number of anyS-graph
of diameter 4 is 4. Hence, each of G(2m,2m) and G(2m,2m) has domination number 4.
(iii) AnyS-graph of diameter
4 is Eulerian if and only if the
cardinality of each of its partite sets is divisible by 4. Hence, the graphs G(2m,2m) and G(2m,2m) are Eulerian if and only if m is even.Proof.
(i) The graphG(4,4) is the 8-cycle. Now consider m≥3. In the graph G(2m,2m), we have N(u1)={w1,w2,…,wm} and N(u2)={w1,w2,…,wm−1}∪{w¯m}. Then u1w1u2w2u1 is a
4-cycle in the bipartite graph G(2m,2m) which implies that the girth of G(2m,2m) is 4. Now since G(2m,2m) is bipartite, then by Theorem 4.1, its girth is also 4.
(ii) LetG be an S-graph
of diameter 4 and partite sets U and W. Then by Lemma 2.6, each vertex in one of the partite sets is
adjacent to exactly half of the vertices of the other partite set. Thus, G cannot have a dominating set with number of
elements less than 4. But for any two vertices u,w, where u∈U and w∈W, we have N(u)∪N(u¯)=W and N(w)∪N(w¯)=U. Therefore, {u,u¯,w,w¯} is a dominating set of G.
(iii) LetG be an S-graph
of diameter 4 and partite sets U and W. By Lemma 2.6,
each vertex of G has degree either (1/2)|U| or (1/2)|W|. Therefore, the degree of every vertex of G is even if and only if both |U| and |W| are multiples of 4.One might put for further research the
following question. For anS-graph of diameter 4 and partite sets U and W, where 2m=|U|≤|W|,
a sharp lower bound and a sharp upper bound of |W| are 2m and 2m, respectively. If m>3, then for each integer t with m<t<2m−1, what about the existence of an S-graph
of diameter 4 and partite sets U and W, where 2m=|U| and |W|=2t?



---

*Source: 468583-2008-02-20.xml*