CHARACTERIZING SYMMETRIC DIAMETRICAL GRAPHS OF ORDER 12 AND DIAMETER 4

http://ijmms.hindawi.com

© Hindawi Publishing Corp.

CHARACTERIZING SYMMETRIC DIAMETRICAL GRAPHS OF ORDER 12 AND DIAMETER 4

S. AL-ADDASI and H. Al-EZEH

Received 21 March 2001 and in revised form 29 August 2001

A diametrical graphGis said to be symmetric ifd(u,v)+d(v,u)¯ =d(G)for allu,v∈ V (G), where ¯uis the buddy ofu. If moreover,Gis bipartite, then it is called anS-graph.

It would be shown that the Cartesian productK2×C6is not only the uniqueS-graph of order 12 and diameter 4, but also the unique symmetric diametrical graph of order 12 and diameter 4.

2000 Mathematics Subject Classification: 05C75.

1. Introduction. Diametrical graphs are an interesting class of graphs. They have been investigated by quite many authors under different names. Some of them studied the properties of these graphs, see Mulder [5,6], Parthasarathy and Nandakumar [7], and Göbel and Veldman [3]. Certain special classes of diametrical graphs have been classified and studied by others, see Göbel and Veldman [3] and Berman and Kotzig [2].

In that direction, Al-Addasi [1] has studied some properties of bipartite diametri- cal graphs of diameter 4 and constructed anS-graph of diameter 4 and order 4kfor anyk≥2. (Recall that the Cartesian productG¹×G2of two graphsG¹andG²is the graph whose vertex set consists of all ordered pairs(x1,x2)wherex1is a vertex of G1andx2is a vertex ofG2such that two vertices(x1,x2)and(y1,y2)are adjacent exactly when eitherx¹=y¹andx²y²is an edge ofG², orx¹y¹is an edge ofG¹and x2=y2. Also recall thatK2,C6denote the complete graph with two vertices and the cycle of length 6, respectively.) Fork=3, this S-graph is isomorphic toK2×C6. In this paper, we show that up to isomorphism the graphK2×C6is not only the unique S-graph of order 12 and diameter 4 but also the unique symmetric diametrical graph of such an order and diameter.

For undefined notions and terminology, the reader is referred to Harary [4]. We con- sider only finite simple connected graphs with no loops or multiple edges. We would useV (G),E(G)to denote the vertex set and edge set of the graphG, respectively. The distance dG(u,v)(or simplyd(u,v)) between two verticesu, v inG, is the length of a shortest(u,v)-path inG, where the length of a path is the number of its edges.

The diameterd(G)of a graphGis the maximal possible distance between two ver- tices inG. For any two verticesu,v inG, the intervalIG(u,v)is the set of vertices {w∈V (G):wlies on a shortest(u,v)-path inG}, when no confusion can arise, we writeI(u,v), see Mulder [5]. The order of a graphGis the number of vertices ofG. The set of all vertices in a graphG, which are at distancekfrom a vertexv inG, is denoted byNk(v); the set of all neighborsN1(v)ofvis also denoted byN(v). The degree of a vertexv in a graphG, denoted by deg_Gv, is the number of vertices in

N(v). IfAis a subset of the vertex set of a graphG, thenAdenotes the subgraph ofGinduced byA. A subgraph ofGcontaining all vertices ofGis called a spanning subgraph ofG. IfSis a subset of the vertex set of the graphG, thenG−Sis the sub- graph ofGinduced byV (G)−S. IfGis connected whileG−Sis not, thenSis called a vertex cut ofG. IfBis a set of edges joining vertices fromGwhereB∩E(G)= ∅, then the graphG+Bis obtained fromGby adding all edges inB.

Two verticesuandvof a nontrivial connected graphGare said to be diametrical if d(u,v)=d(G). A nontrivial connected graphGis called diametrical if each vertexv ofG has a unique diametrical vertex ¯v, the vertex ¯v is called the buddy ofv, see Mulder [5,6]. A diametrical graphGis called symmetric ifd(u,v)+d(v,u)¯ =d(G)for allu,v∈V (G), that is,V (G)=I(u,u)¯ for anyu∈V (G), see Göbel and Veldman [3]. A bipartite symmetric diametrical graph is called anS-graph, see Berman and Kotzig [2].

2. Symmetric diametrical graphs. In this section, we introduce some properties of symmetric diametrical graphs that we will use in the sequel. The following two results are proved in Göbel and Veldman [3].

Theorem2.1. IfSis a vertex cut of a diametrical graphG, then no vertex ofShas degree|S|−1in the induced subgraphSofG.

The previous theorem implies that no vertex cut of a diametrical graph induces a complete subgraph. In particular, a diametrical graph has no cut vertex.

Corollary2.2. Every diametrical graphGother thanK2has no vertex of degree1.

Proposition2.3. LetGbe a diametrical graph of diameterd. ThenGis symmetric if and only if for each pairu,v∈V (G)withv∈Ni(u), we havev¯∈Nd−i(u).

Proof. LetG be symmetric and let u,v∈V (G). Thend(v,u)+d(u,v)¯ =d. If v∈N1(u), thend(u,v)¯ =d−i, that is, ¯v∈Nd−i(u).

Conversely, assume that ¯v∈Nd−i(u)wheneveru,v∈V (G)withv∈N¹(u). Let x,y ∈ V (G). Then x ∈Ni(u) for some i∈ {0,1,...,d} and, by assumption, ¯x ∈ Nd−i(y). Henced(x,y)+d(y,x)¯ =i+d−i=d. ThusGis symmetric.

Corollary2.4. IfGis a symmetric diametrical graph of diameterdandu∈V (G), then for each0≤i≤d,Nd−i(u)= {v¯:v∈Ni(u)}. And hence|Nd−i(u)| = |Ni(u)|.

Proof. SinceGis symmetric,v∈Ni(u)if and only if ¯v∈Nd−i(u). HenceNd−i(u)=

{v¯:v∈Ni(u)}. Also, since the buddy is unique,|Nd−i(u)| = |Ni(u)|.

A diametrical graph is called harmonic if ¯uv¯∈E(G) wheneveruv ∈E(G). The result ofTheorem 2.5is shown in Göbel and Veldman [3].

Theorem2.5. Every symmetric diametrical graph is harmonic.

3. Symmetric diametrical graphs of order12and diameter4

Theorem 3.1. In a symmetric diametrical graph G of order12and diameter4, there is no vertex of degree2.

v v¯

u1 u¯2

u2 u¯1

x y z

z¯ y¯ x¯ G1 Figure3.1

Proof. Assume to the contrary thatG has a vertexv of degree 2. LetN(v)= {u1,u2}. ByCorollary 2.4,N3(v)= {u¯1,u¯2}. HenceN2(v)contains exactly six vertices.

SinceN(v)is a vertex cut ofG, byTheorem 2.1, the verticesu1andu2are nonadja- cent. The same holds for ¯u¹and ¯u². Clearly, ¯x∈N²(v)wheneverx∈N²(v). SoN²(v) consists of three pairs of diametrical vertices. Sinced(G)=4, each of the two vertices u1andu2cannot be adjacent to more than three vertices ofN2(v). But every vertex ofN2(v)is adjacent to at least one of the two verticesu1andu2, sou1is adjacent to exactly three vertices ofN2(v)andu2is adjacent to the other three. Ifx,y, andz are the vertices fromN2(v)adjacent tou1, then ¯x, ¯y, and ¯zare those adjacent tou2. ByTheorem 2.5, the vertex ¯u1is adjacent to ¯x, ¯y, and ¯z; while ¯u2is adjacent tox, y, and z. So we get the spanning subgraphG1 ofG depicted inFigure 3.1. For all u∈ {x,y,z}and allw∈ {x,¯ y,¯ z}¯ , the verticesuandware not adjacent; for other- wise,d(u1,u¯1)≤3. HenceG1⊆G⊆G1+ {xy,xz,yz,x¯y,¯ x¯z,¯y¯z}¯. This implies that d(x,z)¯ =d(x,y)¯ =d(x,x)¯ =4, a contradiction.

Theorem3.2. A symmetric diametrical graphGof order12and diameter4con- tains no vertex of degree4.

Proof. Assume to the contrary thatGhas a vertexvof degree 4, and letN(v)= {u1,u²,u³,u⁴}. ByCorollary 2.4, |N3(v)| =4 and hence|N2(v)| =2. Clearly,N²(v) consists of a vertex and its buddy, sayN2(v)= {x,x}¯ . Then any vertex of N(v)is adjacent to at most one of the two verticesx, ¯x. But, byCorollary 2.2andTheorem 3.1, each vertex ofN(v)has degree at least 3. Then deg_N(v)z≥1 for anyz∈N(v). Now, sincex2∈N2(v), there is a vertex, sayu1, ofN(v)adjacent tox. Butu1has a neighbor inN(v), sayu2. ByTheorem 2.5, the vertex ¯u1is adjacent to both ¯xand ¯u2. Thusu2is not adjacent to ¯x, becaused(G)=4. So, sinceGis symmetric, that is,V (G)=I(v,v)¯ , the vertexu2is adjacent tox, and hence ¯u2is adjacent to ¯x. Since ¯x∈N2(v), then at least one ofu3,u4, sayu4, is adjacent to ¯x. Then ¯u4is adjacent tox. The vertexu3

is adjacent to exactly one of the two verticesxand ¯x, so we distinguish two cases.

Case1. If u3 is adjacent to ¯x. Then ¯u3 is adjacent tox. Since d(x,x)¯ =4, the vertexu3is not adjacent to any of u1,u2. So, byTheorem 3.1, the vertexu3 must be adjacent tou4, and hence ¯u3is adjacent to ¯u4. It is obvious that any additional

v u2 u¯2 v¯

u1 u¯3

u3

u¯1 z

w

w¯ z¯

G Figure3.2

edge in N(v) or N3(v)would decrease the distance between x and ¯x to 3. Then d(u1,u¯1)=d(u1,u¯2)=4, contradictingGis diametrical.

Case2. Ifu3is adjacent tox. Then ¯u3is adjacent to ¯x. ByTheorem 3.1, the vertex u4has at least one neighbor inN(v). But thend(x,x)¯ =3, a contradiction.

Therefore,Gcannot contain a vertex of degree 4.

Theorem 3.3. A symmetric diametrical graph G of order 12and diameter 4 is isomorphic toK2×C6.

Proof. If G has a vertex v of degree greater than 4, then, by Corollary 2.4,

|N3(v)|>4 and hence|V (G)| =1+ |N(v)| + |N2(v)| + |N3(v)| +1>12, a contra- diction. SoGhas no vertex of degree greater than 4. Then, by the previous theorem, every vertex ofGhas degree at most 3. But fromCorollary 2.2andTheorem 3.1, every vertex ofGhas degree at least 3. HenceGis 3-regular. Pick a vertexvfromV (G)and letN(v)= {u1,u2,u3}. Then|N2(v)| =4. SinceN(v)is a vertex cut ofG, then by Theorem 2.1, each vertex ofN(v)has at most one neighbor inN(v). HenceN(v) has at most one edge. We proceed by contradiction to show thatE(N(v))= ∅. So, assume that there is an edge, sayu1u2, inN(v)and hence ¯u1u¯2∈E(G). Thenu1

has exactly one neighbor, say x, inN2(v). Then, byTheorem 2.5, the vertex ¯u1 is adjacent to ¯x. Similarly,u²has exactly one neighboryinN²(v). The vertexyis dif- ferent from ¯xbecause otherwised(x,x)¯ ≤3, which is impossible. Alsoyis different fromx becauseG is 3-regular and each of the four vertices in N2(v)has at least one neighbor inN(v). ThusN²(v)= {x,x,y,¯ y}. By¯ Theorem 2.5, ¯u²y¯∈E(G). Since Gis 3-regular and each ofu1,u2has already three neighbors, the neighbor of each of ¯x, ¯y fromN(v)isu3. Then, again byTheorem 2.5, the edgesxu¯3,yu¯3belong to E(G). Then, the 3-regularity ofGandTheorem 2.5imply that eitherxy,x¯y¯∈E(G)or xy,¯ xy¯ ∈E(G). But now we have eitherd(x,y)¯ =d(x,x)¯ ord(x,x)¯ =3, respectively, a contradiction in any case. Therefore, we deduce thatN(v)has no edges. Then each ofu1,u2,u3has two neighbors fromN2(v). If we letN(ui,v)denote the set of neighbors ofuifromN2(v), (fori=1,2,3), then{N(u1,v),N(u2,v),N(u3,v)} ⊆ {{x,y},{x,y},{¯ x,y},{¯ x,¯ y}}¯ . Then there exist i,j ∈ {1,2,3} with i≠ j such that N(ui,v)∩N(uj,v)= ∅, and hence|N(uk,v)∩N(ui,v)| = |N(uk,v)∩N(uj,v)| =

1, where {k} = {1,2,3} − {i,j}. Then G is the graph depicted inFigure 3.2 where {z,z,w,¯ w} = {x,¯ x,y,¯ y}¯ . Now it is obvious that G is isomorphic to the Cartesian productK2×C6.

References

[1] S. Al-Addasi,Diametrical graphs, Master’s thesis, University of Jordan, Amman, 1993.

[2] A. Berman and A. Kotzig,Cross-cloning and antipodal graphs, Discrete Math.69(1988), no. 2, 107–114.

[3] F. Göbel and H. J. Veldman,Even graphs, J. Graph Theory10(1986), no. 2, 225–239.

[4] F. Harary,Graph Theory, 3rd ed., Addison Wesley, Massachusetts, 1972.

[5] H. M. Mulder,The Interval Function of a Graph, Mathematical Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam, 1980.

[6] ,n-cubes and median graphs, J. Graph Theory4(1980), no. 1, 107–110.

[7] K. R. Parthasarathy and R. Nandakumar,Unique eccentric point graphs, Discrete Math.46 (1983), no. 1, 69–74.

S. Al-Addasi: Department of Mathematics, Hashemite University, Zarqa, Jordan E-mail address:[email protected]

H. Al-Ezeh: Department of Mathematics, University of Jordan, Amman, Jordan