ON LARGE (∆, D, D, 1) GRAPHS
∗
J. G´omez, J. F`abrega and J.L.A. Yebra Universitat Polit`ecnica de Catalunya
Abstract Concern about fault tolerance in the design of interconnection networks has aroused interest in finding large graphs such that the subgraphs obtained by deleting any set of up to s vertices have small diameter. Clearly, 1 ≤ s ≤ ∆ − 1, where ∆ is the maximum degree of the graph. Graphs of maximum degree ∆, diameter ≤ D and such that the graphs obtained by deletion of up to s vertices have diameter ≤ D′ are known as (∆, D, D′ , s) graphs. This paper considers the case s = 1 and D = D′ . In other words, it deals with the search for large graphs whose diameter does not increase after deleting one vertex. The paper also contains an updated table of the largest known (∆, D, D, 1) graphs, in which most of the entries correspond to the constructions put forward in this paper.
Keywords: Interconnection networks; Large graphs; Compound graphs; Product of graphs; Vulnerability; (∆, D, D′ , s)-problem.
1
Introduction and some previous results
The designer of interconnection networks must allow for the fact that machines and/or communication links may malfunction or cease to function. In this event it is important that communication can still be achieved with reasonable efficiency. It may be required, for instance, that between any two nodes of the remaining network there still exists a path of length not exceeding some fixed value. As a general reference for interconnection networks, see [19]. In terms of graphs and digraphs this problem is modeled in the literature as the (∆, D, D′ , s) − problem, which looks for the largest graphs of maximum degree ∆ and diameter D such that the subgraphs obtained by deleting ∗ Supported
by the Spanish Research Council under project MTM2005-08990-C02-01 and by the Catalan Research Council under
project 2005SGR00256. e–mail:
[email protected],
[email protected],
[email protected]
1
any set of up to s vertices have diameter ≤ D′ . For graphs, the cases s = 1 and D′ − D = 0, 1, 2 have been studied, see [3, 6, 10, 11, 12, 16, 13, 23, 27, 39, 40]. The case s = ∆ − 1 has been studied in [44, 47]. The increase in the diameter caused by edge deletion has also been studied, see for instance [6, 16, 42]. Regarding digraphs the (∆, D, D′ , s) − problem has been considered for the general case in [35], for iterated line digraphs in [1, 14, 20, 37], for Kautz digraphs in [18], for bipartite digraphs in [26, 38], and for asymptotically optimal digraphs in [36]. See also [32] for products of graphs. Finally, [34] contains a comparative survey on vulnerability in graphs. The problem is reminiscent of the well-known (∆, D)-problem which deals with the construction of graphs and digraphs with the largest possible order for given degree ∆ and diameter D. We refer to [33] for history, background and development. Easily accessible on-line tables of the largest known (∆, D)−graphs are kept in [48] and [49]. In this paper, we deal with the construction of large (∆, D, D, 1)−graphs, that is, large graphs whose diameter does not increase (D′ = D) after the deletion of s = 1 vertex. They are sometimes called invulnerable graphs. Bounds on the order of such graphs can be obtained as follows: In any (∆, D, D, 1)−graph, any pair of nonadjacent vertices must be joined by at least s + 1 = 2 different paths of length ≤ D. Since from any vertex there are at most ∆ paths of length 1, at most ∆(∆ − 1) paths of length 2 and in general at most ∆(∆ − 1)k−1 paths of length k, the maximum order of a (∆, D, D, 1)−graph is bounded by N ≤1+∆+
∆(∆ − 1) + ∆(∆ − 1)2 + · · · + ∆(∆ − 1)D−1 2
(1)
If ∆ > 2, this bound cannot be achieved for D > 2. Indeed, notice first that the bound could only be attained by regular graphs of degree ∆. Next, since any two vertices at distance 2 should be joined by some other path of length ≤ D, the girth of the graph must satisfy g ≤ D + 2. Moreover, the bound (1) can only be attained when there are exactly 2 (vertex-)disjoint paths joining any two vertices at distance ≥ 2. However, this requires that the girth of the graph be larger than 2D − 2. Otherwise, there would be vertices u and v joined by two paths of length ≤ D − 1, and then between u and some neighbor of v there would be two paths of length ≤ D which are not disjoint. Therefore, we obtain 2D − 2 < g ≤ D + 2, so that D < 4. Moreover, the bound (1) cannot be achieved for D = 3, see [45]. As indicated above, this work deals with the construction of large (∆, D, D, 1)−graphs. We construct large graphs or families of graphs by appropriately applying several general techniques: graphs on alphabets, compounding of graphs, different products of graphs and addition of vertices to known graphs. In this way, the order of many largest (∆, D, D, 1)-graphs is improved. Table 1 shows the largest known (∆, D, D, 1)-graphs. The graphs proposed in this work are denoted either by ♠ or by a black box . Those denoted by ♠ are new constructions defined in this work, whereas the graphs denoted by
has been obtained in this work by addition of vertices to
already known (∆, D, D, 1)−graphs, keeping their properties. 2
D
2
3
4
5
6
7
8
9
10
∆ ⊙
2 ⊙
3 ⊙
C4 ⊙ 4
C5 5
K3,3 ⊙ BP 12 6
⊙
C6 6
⊙
C7 7
⊙
C8 8
⊙
⊙
C9 9
C10 10
⊙
C11 11
⊙
C12 12
BP ♠ 17 K1,1 ♠ 13 K1,3 18 34 52
BS 102
♠ 31 K1,3 124
♠ 43 K1,3 172
♠ 43 K1,3 172
♠ 4 P2 56
♠ 4 Q2 120
K+ 193
Cs (8, 6, 2) 512
Cs (9, 7, 2) 1 152
K+ 2 1 538
Dl Cs (9, 2, 2) 26 36
4
BP 10
5
⊙ BP, Cl 16
3∗P 30
O5 126
O5 126
♠ 4 Q3 320
16 ⊕ Q3 480
♠ 4 H3 2 912
6 ⊕ H3 4 368
95[K96 ] 9 120
6
P (K2,2 ) 20
2 ∗ 24 48
O5 126
O6 462
K+ 973
K+ 2 919
♠ 4 H4 10 920
K+ 26 247
K+ 78 733
3 ∗ 24 72
O5 126
O6 462
O7 1 716
♠ 2 × 1H4 5 460
♠ 4 H5 31 248
8 ⊕ H5 62 496
♠ (40) ∧2 H4
7
♠ 6 K1,3 24
8
15(K2,2 ) 2 ∗ HS 100 30
K+ 321
K+ 1 284
K+ 5 121
K+ 20 484
K+ 81 921
K+ 327 684
1 310 721
15(K2,2 ) d 3 ∗ HS ♠ P (2, 3) ♠ P (2, 4) ♠ P (2, 5) 150 32 384 1 536 6 141
♠ 2 × 2H5 31 248
♠ 4 H7 156 864
10 ⊕ H7
♠ Q5 ∇ 1 H 5
392 160
2 437 344
9
163 800
K+
Gew 4 ∗ HS 200 56
K+ 751
K+ 3 755
K+ 18 751
K+ 93 755
♠ K 6 ∧ 2 H7
♠ HS ∧2 H7
♠ Q5 ∇ 2 H 7
588 240
2 941 200
12 235 392
Gew d 5 ∗ HS 250 57
+ K+ 811
+ K+ 4 055
+ K+ 20 251
♠ 2 × 2H7 156 864
♠ K 7 ∧ 1 H7
♠ P 5 ∇1 H7
♠ Q7 ∇ 1 H 7
823 536
3 647 088
31 372 800
32(K2,2 ) 6 ∗ HS 300 64
K+ 1 513
K+ 9 078
K+ 54 433
K+ 326 598
♠ K 6 ∧ 2 H9
♠ HS ∧2 H9
♠ Q′8 ∧2 H9
2 790 060
16 607 500
116 584 650
5 ∗ 74 ♠ P (3, 3) ♠ P (3, 4) ♠ P (3, 5) 370 1 728 10 368 62 208
♠ 2 × 2 H9
♠ K 7 ∧ 1 H9
♠ P 7 ∇1 H9
♠ Q9 ∇ 1 H 9
13
32(K2,2 ) d 66
531 440
3 720 080
22 719 060
217 890 400
14
HS(K2,2 ) 100
5 ∗ 91 455
K+ 2 745
K+ 19 215
K+ 134 457
15
HS(K2,2 )d 102
6 ∗ 91 546
+ K+ 2 913
+ K+ 20 391
+ K+ 142 689
⊙
10 11 12
K+
♠ K8 ∧2 H11
♠ P8′ ∧2 H11
♠ Q9 ∇2 H11
941 199
9 920 736
65 547 720
581 071 680
♠ 2 × 2 H11
♠ K9 ∧1 H11
♠ P9 ∇1 H11
♠ Q11 ∇1 H11
1 417 248
12 755 232
96 727 176
1 037 425 536
Table 1: Largest known (∆, D, D, 1) graphs (2 ≤ ∆ ≤ 15, 2 ≤ D. ≤ 10)
3
⊙
Optimal values
P
Petersen graph
HS
Hoffman-Singlenton graph; see [29]
Dl
graph proposed by C. Delorme; see [17]
BS
Biggs-Smith graph; see [8]
K
Kautz graph; see [30, 21]
K+
Expanded Kautz graph; see 4.3.6 of Chapter 4 of [12], and Section 3
K+
Addition to Kautz graph; see Section 3
+ K+
Addition to expanded Kautz graph; see Section 3
P (d, k)
See Section 2
G(K2,2 )
See 4.3.4 in [41]
G1 (Km )
See 4.3.2 in [41] and Section 5
⊕
See 4.3.1 in [41]
∗
See 4.3.6 in [41] and Section 4
d
Duplication of vertices
Pq
Incidence graph of projective plane, bipartite Moore graph with diameter 3), [4, 7, 28]
Qq
Generalized quadrangles, bipartite Moore graph with diameter 4, [2, 4, 7]
Hq
Generalized hexagons, bipartite Moore graph with diameter 6, [2, 4, 7]
Cs
A graph on alphabet; see 4.3.7 in [12]
n Ki,j
See Section 6
4B
Special product of bipartite graphs; see Section 4
2 × mB
See Section 3
Q ∧i B
See Section 5 and [23]
B1 ∇i B2
See Section 5 and [23]
Oj
Akers graph
BP
Special graph found by J. Bond and C. Peyrat, [41]
Cl
Clebsch graph; see [15]
Gew
Gewirtz graph; see [22] Table 2: Notations and symbols used in the Table 1.
4
General families: Graphs on alphabet P (d, k)
2
We begin by recalling two notable results about the vulnerability of general families of graphs, presented by J. Bond and C. Peyrat in [11, 12, 41]. The first concerns the underlying graph U (D) of a digraph D, that is, the graph obtained by replacing each arc (u1 , u2 ) (or every pair of symmetric arcs (u1 , u2 ), (u2 , u1 )) of a digraph D by the edge u1 u2 in U (D). In a digraph D, Γ+ (x) [Γ− (x)] denotes the set of vertices adjacent from [to] a vertex x, and d+ (x) = |Γ+ (x)| [d− (x) = |Γ− (x)|] is the out-degree [in-degree] of x. Theorem 1. [41] Let D be a connected digraph which verifies that for each pair of vertices x, y ∈ D, |Γ+ (x) ∩ Γ+ (y)| = 6 1 and |Γ− (x) ∩ Γ− (y)| = 6 1. Then, when any vertex is deleted from U (D), its diameter is bounded above by the diameter of the digraph D. Next, let D′ be a digraph so that each of its vertices has both in-degree d− and out-degree d+ greater than or equal to 2. As a consequence of the previous Theorem, we have the following result: Theorem 2. [41] Let D = Ln (D′ ) be an iterated line digraph of some digraph D′ , and let U (D) be the underlying graph of D. Then, when any vertex is deleted from U (D), its diameter is bounded above by the diameter of the digraph D. De Bruijn and Kautz digraphs are two important instances of such digraphs. Indeed, the De Bruijn [Kautz] digraph are the iterated line digraphs of a complete digraph [a complete digraph without loops]. Hence, De Bruijn and Kautz graphs with even degree ∆ and diameter D are the underlying graphs of iterated line digraphs with n = D − 1, and have order N= and N=
∆ 2
D
D−1 ∆ ∆ +1 2 2
(2)
(3)
respectively. C. Peyrat [41] presented a family of (∆, D, D, 1) graphs for odd degree by adding vertices to the Kautz graph, increasing their degree by one unit and obtaining the expanded Kautz graphs with order D−1 D−3 ∆+1 ∆−1 ∆+1 ∆−1 ∆−1 N= + 2 2 4 2 2
(4)
In this section, we present a family of large graphs on alphabets which are (4d + 1, D, D, 1)-graphs. Definition 1. The P (d, k) is the graph whose vertices are the sequences x = α, a; x1 x2 . . . xk−1 xk , 5
(5)
where α ∈ Z2 , a ∈ Zd+1 , and xi ∈ Z2d , and every vertex x is adjacent to the 4d + 1 vertices: α + xk+1 , a + 1 + α − xk , a − 1 −
jx
k+1
j x 2k k
2
k
; x2 x3 . . . xk xk+1 , xk+1 ∈ Z2d
; x0 x1 . . . xk−2 xk−1 ,
(6)
x0 ∈ Z2d
(7)
α ¯ , a; x1 x2 . . . xk−1 xk
(8)
and the calculations for the first digit are mod 2 whereas those for the second digit are mod d + 1. The graph P (d, k) is loopless and has order N = 2(d + 1)(2d)k . Moreover, we have: Theorem 3. The graph P (d, k) has diameter D = k + 1. Proof. We must show a path of length k or k + 1 between any pair of vertices. Let x = α, a; x1 x2 . . . xk−1 xk k X yi and let be the origin vertex. We denote the destination vertex by y = β, b; y1 x2 . . . yk−1 yk . Let Y0 = i=1
k j X yi k . We distinguish three cases: Y1 = 2 i=1
A:
ya
= α + Y0 , a + k + Y1 ; y1 y2 . . . yk−1 yk ,
B:
yb
= α ¯ + Y0 , a + k + Y1 ; y1 y2 . . . yk−1 yk
C:
yc
= α + γ + Y0 , a + k + 1 + Y1 + s; y1 y2 . . . yk−1 yk ,
for
s ∈ Zd .
The corresponding paths of length at most k + 1 are: Case A: x = α, a; x1 x2 . . . xk−1 xk , α + xk+1 , a + 1 + xk+1 ; x2 x3 . . . xk y1 , 2 ...,
α + Y0 , a + k + Y1 ; y1 y2 . . . yk−1 yk = y a Case B:
k steps of adjacency (6)
x = α, a; x1 x2 . . . xk−1 xk , ..., α+
j X
yi , a + j +
i=1
w=α ¯+
j X i=1
j j X i=1
yi , a + j +
yi k ; xj+1 xk y1 . . . yj = v, 2
j j X yi k i=1
...,
xj+1 xk y1 . . . yj , 2
α ¯ + Y0 , a + k + Y1 ; y1 y2 . . . yk−1 yk = y b 6
j steps of adjacency (6)
k − j steps of adjacency (6)
together with one step of adjacency (8) for the edge v w. Observe that in this case there are k + 1 different paths (corresponding to j = 0, 1, . . . , k). Finally, Case C: x = α, a; x1 x2 . . . xk−1 xk , 1 step of adjacency (6) 2s+γ ; x x . . . x 2s + γ = α + 2s + γ, a + 1 + 2 3 k 2 = α + γ, a + 1 + s; x2 x3 . . . xk 2s + 1 . . . ... α + γ + Y0 , a + k + 1 + Y1 + s; y1 y2 . . . yk−1 yk = y c
k steps of adjacency (6)
Therefore, in terms of its degree and diameter the order of the graph P (d, k) = P ((∆ − 1)/4, D − 1) is N=
∆+3 2
∆−1 2
D−1
(9)
Figure 1 shows the graph P (1, 2). t t tP t @ PPP P P @ PP P @ PP Pt t @t t
0,0;10
0,1;01
1,0;00
1,1;00
1,0;10
1,1;01
0,0;00
0,1;00
tP P
t t @ PP P P @ P P P @ PP @ Pt t t
t
1,1;11
0,0;11
0,1;11
1,0;11
t
0,1;10
1,0;01
1,1;10
0,0;01
Figure 1: Graph P (1, 2) Concerning the behaviour of the diameter of the graph P (d, k), when one vertex is deleted we have: Theorem 4. The graph P (d, k) is a (∆, D, D, 1)-graph. Proof. The graph P (d, k) can be seen as the underlying graph of the digraph P ∗ (d, k) with adjacency rules (6) and (8). Now we apply Theorem 1 and the only case which is not considered is when at least one of the paths that joins two vertices x and y corresponds to case B in the proof of Theorem 3. In that case, there are k + 1 paths of length k + 1 from x to y. To be more precise, the path Pj , 0 ≤ j ≤ k, uses j steps of type (6), followed by one step of type (8) and k − j steps of type (6) again. Now we denote the path Pj by x = (0, z0 ), (0, z1 ), . . . , (0, zj−1 )(0, zj ), (1, zj ), (1, zj+1 ), . . . , (1, zk ) = y. Observe that the deleted vertex, denoted 7
by (β, zj ), can belong to several of these k + 1 paths. However, according to the adjacency rules it can be verified ¯ zj−1 ), (β, ¯ zj ), (β, ¯ zj+1 )}. that (β, zj ) 6∈ {(β, zj−1 ), (β, zj+1 ), (β, Let us consider that the deleted vertex belongs to several paths. We denote the deleted vertex for each path by (βp , zp ), (βq , zq ), . . . , (βr , zr ), where p < q < . . . < r. Let us assume that βp = 0 and βr = 1 (the other cases can be treated in a similar way). A path from x to y of length ≤ k + 1 which does not contain the deleted vertex is x = (0, z0 ), (0, z1 ), · · · , (0, zp−1 ), (1, zp−1 ), (1, zp ) = (0, zr ), (0, zr+1 ), · · · , (0, zk ), (1, zk ) = y. Observe that, for the same degree ∆ = 4d + 1 and the same diameter, the order given by (9) is greater than the order given by (4). For instance, the graph P (2, 3) is a (9, 4, 4, 1)−graph with order N = 2(3)43 = 384, which is the largest known order for a (9, 4, 4, 1)−graph. See Table 1 for other large invulnerable graphs P (d, k). In the next section, we increase the values of (3) and (4), by using a special technique for adding vertices to a graph while maintaining its (maximum) degree and its diameter.
3
Addition of vertices in Kautz graphs
Kautz digraphs have been recalled in Section 2 as iterated line digraphs of a complete digraph without loops: K ∗ (d, D) = LD−1 K ∗ (d, 1) (the star denotes digraph). However, there are alternative definitions. For instance, in [30] it is defined as the digraph whose vertices are labeled with words x1 x2 . . . xD , where xi ∈ Zd+1 and xi 6= xi+1 for 1 ≤ i ≤ k − 1, and a vertex x1 x2 . . . xD is adjacent to the vertices x2 . . . xD xD+1 , where xD+1 can be any letter different from xD . Hence, the digraph K ∗ (d, D) is d−regular and has dD + dD−1 vertices. In addition, its diameter is D. Indeed, let y = y1 y2 . . . yD be the destination vertex and let x = x1 x2 . . . xD−1 xD , be the origin vertex. When xD 6= y1 a path from x to y of length D is x1 x2 . . . xD−1 xD ,
x2 . . . xD−1 xD y1 ,
. . . . . . , xD y1 . . . yD−1 ,
y1 y2 . . . yD−1 yD ,
whereas when xD = y1 a path from x to y of length D − 1 is x1 x2 . . . xD−1 y1 ,
x2 . . . xD−1 y1 y2 ,
. . . . . . , y1 y2 . . . yD−1 yD
Applying either Theorem 1 or Theorem 2, Bond and Peyrat proved that the underlying graph of Kautz digraph, the Kautz graph K(∆, D), is a (∆, D, D, 1)−graph with order given by (3) and degree ∆ ≤ 2d (since the underlying graph of Kautz digraph K ∗ (d, 2) has degree ∆ = 2d − 1 < 2d). As mentioned before, Bond and Peyrat also presented a family of (∆, D, D, 1) graphs for odd degree using the technique of addition of vertices to the Kautz graphs, increasing their degree by one unit and obtaining the expanded Kautz graphs whose order is given by (4). In order to add ⌊d/2⌋ (d + 1) (d)
D−3
vertices to Kautz graph K(2d, D), D ≥ 3, in such a way that the
resultant graph has degree ∆ = 2d + 1 and is a (∆, D, D, 1)-graph, let us first consider the disjoint subsets 8
of the vertex set of the Kautz digraph K ∗ (d, D) (which coincides with the set of vertices of the Kautz graph U (K ∗ (d, D)) = K(2d, D)): P x2 x3 . . . xD−1 = {zx2 x3 . . . xD−1 t such that z, t ∈ Zd+1 , z 6= x2 and t 6= xD−1 } Each of these subsets has cardinality d2 . Let us now denote the elements of P x2 x3 . . . xD−1 by a; x2 x3 . . . xD−1 ; b where a, b ∈ Zd . Let l ∈ Z⌊d/2⌋ . One way to add a vertex L for every l to each of the disjoint subsets of vertices P x2 x3 . . . xD−1 is as follows. Vertices adjacent from vertex L are given by the following adjacency rule: L → a; x2 x3 . . . xD−1 ; a + l, a ∈ Zd whereas vertices adjacent to vertex L are given by the adjacency rule: a + l + 1; x2 x3 . . . xD−1 ; a → L, a ∈ Zd Observe that the previous adjacency rule involves that the out-degree and in-degree of any vertex of any subset P x2 x3 . . . xD−1 is at most d + 1. More precisely, if the out-degree [in-degree] of a vertex is d + 1 then its in-degree [out-degree] is d. Moreover, reasoning as at the beginning of this section to show paths of length D or D−1 between two vertices of the Kautz digraph, it can be proved that the resulting digraph has diameter D. Finally, according to the previous adjacency rules, it is clear that the digraph so constructed is such that for each pair of vertices x, y, both |Γ+ (x) ∩ Γ+ (y)| = 6 1 and |Γ− (x) ∩ Γ− (y)| = 6 1 hold. Then, according to Theorem 1, the underlying graph of this digraph, known as the expanded Kautz graph K + (2d + 1, D) (= K + ) is a (2d + 1, D, D, 1)-graph. We are now ready to increase the values (3) and (4) by adding some vertices to both Kautz and expanded Kautz graphs, while keeping their degrees and their characteristics of vulnerability. This is accomplished by using the (d+1)d vertices of K(2d, D) with degree one unit less than ∆ = 2d, which have the structure x1 x2 x1 x2 · · · x1 x2 when D is even, and x1 x2 x1 x2 · · · x2 x1 when D is odd. + Definition 2. If D is odd the graphs K+ and K+ are obtained by adding ⌊d/2⌋ vertices, called m, m ∈
{0, 1, 2, . . . , ⌊d/2⌋ − 1}, to the Kautz graph K and to the expanded Kautz graphs K + , respectively, with the adjacency rule: p 2m p 2m . . . 2m p, m∼ q 2m + 1 q 2m + 1 2m + 1 q,
p ∈ Zd+1 , p 6= 2m q ∈ Zd+1 , q 6= 2m + 1
+ If D is even the graphs K+ and K+ are obtained by adding just one vertex, called 0, with the adjacency rule: p 0 p 0 . . . p 0, p ∈ Zd+1 , p 6= 0 0∼ 0 q 0 q . . . 0 q, q ∈ Z , q 6= 0 d+1
+ The graph K+ has degree ∆ = 2d and the graph K+ has degree ∆ = 2d + 1.
9
+ Theorem 5. The graphs K+ and K+ are (∆, D, D, 1)-graphs if D ≥ 2.
Proof. We only deal with the case D odd, because the case D even is similar and even simpler. Since all vertices adjacent to the added vertices m ∈ {0, 1, 2, . . . , d2 − 1} are different, and taking into account Theorem 1, it suffices to exhibit 2 paths of length ≤ D between the added vertices and the vertices of the original graph (K and K + ). In the case of graph K+ , we distinguish two cases • A first path between vertices m and x1 x2 . . . xD is (if
2m 6= x1 )
(if
2m = x1 )
m
m
x1 2m x1 2m . . . 2m x1
x2 x1 x2 x1 . . . x1 x2
2m x1 2m . . . 2m x1 x2
x1 x2 x1 . . . x1 x2 x3
......
......
2m x1 x2 . . . xD−1
x2 x1 x2 . . . xD−2 xD−1
x1 x2 . . . xD
x1 x2 . . . xD
and a second path is
(if
2m 6= x1 )
(if
2m = x1 )
m
m
xD 2m xD . . . 2m xD
xD−1 xD xD−1 xD . . . xD−1 xD xD−1
xD−1 xD 2m xD 2m xD
xD−2 xD−1 xD xD−1 xD . . . xD−1 xD
......
......
x2 x3 . . . xD 2m
x2 x3 . . . xD xD−1
x1 x2 . . . xD
x1 x2 . . . xD
• Between vertices m1 and m2 two paths are First path
Second path
m1
m1
2m2 2m1 2m2 . . . 2m1 2m2
2m2 + 1 2m1 + 1 2m2 + 1 . . . 2m1 + 1 2m2 + 1
2m1 2m2 . . . 2m1 2m2 2m2
2m1 + 1 2m2 + 1 . . . 2m1 + 1 2m2 + 1 2m2 + 1
m2
m2
+ For the graph K+ , according to Theorem 1, it is enough to exhibit 2 paths of length ≤ D between the added
10
vertices and the vertices of the sets P x2 x3 . . . xD−1 . That is, between vertices m and lx2 . . . xD−1 . A first path is (if
2m 6= x2 )
(if
2m = x2 )
m
m
x2 2m x2 2m . . . 2m x2
x3 x2 x3 x2 . . . x2 x3
2m x2 2m . . . 2m x2 x3
x2 x3 x2 . . . x2 x3 x4
......
......
2m x2 x3 . . . xD−1 q =
x′3 x2 x3 . . . xD−2 xD−1 s =
(2m)′ ; x2 x3 . . . xD−1 ; q ′ = v ′
x′3 ; x2 x3 . . . xD−2 xD−1 ; s′ = v ′′
lx2 . . . xD−1
lx2 . . . xD−1
where (q ′ − (2m)′ ) mod d, s′ − x′3 mod d < (if
d 2
and v ′ ∼ y ∼ v ′′ . And a second path is
2m 6= xD−1 )
(if
2m = xD−1 )
m
m
xD−1 2m + 1 . . . xD−1
xD−2 xD xD−1 xD . . . xD−1 xD−2
xD−2 xD−1 2m + 1 . . . xD−1
xD−3 xD−2 xD xD−1 xD . . . xD−1 xD−2
......
......
rx2 x3 . . . xD−1 2m + 1 =
tx2 x3 . . . xD−1 xD−2 =
r′ ; x2 x3 . . . xD−1 ; (2m + 1)′ = u′
t′ ; x2 x3 . . . xD−1 ; x′D−2 = u′′
lx2 . . . xD−1
lx2 . . . xD−1 .
Hence, in terms of their diameter, the graph K+ has order ∆ + 1 ∆ D−1 + 1 2 2 N= ∆ + 1 ∆ D−1 + d 2 2 2
+ and the graph K+ has order ∆+1 2 N= ∆+1 2
∆−1 D−1 2 ∆−1 D−1 2
+ +
Figure 2 shows the graph K+ (2, 2).
4
∆−1 4
∆−1 4
∆+1 2
∆+1 2
if D is even if D is odd
∆−1 D−3 2 ∆−1 D−3 2
+1 + d2
if D is even if D is odd
Products of graphs
The technique of product of graphs can be used in two different ways: to study known products of graphs and to design new ones with desired characteristics. 11
t B B
$
01
10 t
B
B @ B 0 12 21 t t @Bt @ @ @ @t 02 @ @ @ @t 20
%
Figure 2: The graph K+ (2, 2) As an example of the first, J. Bond and C. Peyrat studied the vulnerability of products of graphs K ∗ G and N ⊕ G; see for instance [12]. In particular, to construct the graph K ∗ G, K copies of a (∆ − K + 1, D − 1, D, 1) graph G are joined together by complete graphs that join the same vertices of different copies. They proved that K ∗ G is a (∆, D, D, 1) graph. In this section, we illustrate the second possibility with two products of bipartite graphs.
4.1
The graph 2 × mB
Let B be a bipartite graph B = (VB ∪ UB , EB ) with |VB | = |UB | = n and degree ∆B and diameter DB . Each vertex is denoted by (x, i), where x ∈ {0, 1, . . . , N2B − 1} and i is a binary digit, such that, if i = 0 [i = 1] then x belongs to VB [UB ]. Let us take 2m copies of a the bipartite graph B, where vertex (x, i) of a copy (j, l), j ∈ {0, 1}, l ∈ {0, 1, . . . , m − 1}, is denoted by (x, i, j, l). Definition 3. The graph 2 × mB consists of 2m copies of the bipartite graph B which are joined according to the adjacency rule:
where ¯j denotes j + 1 mod 2.
(x, k, ¯j, l), (x, i, j, l) ∼ (x, j, i, q),
k ∈ {0, 1} q 6= l
The graph 2 × mB has order N = 4mn and degree ∆ = ∆B + m + 1. Figure 3 illustrates the construction of the graph 2 × 2B. Each oval represents a copy of a bipartite graphs B with order NB = 2n. The two stable sets of each copy of B are separated by a dashed line. The graph 2 × 2B is obtained by adding 12 perfect matchings among some of these stable sets, according to Figure 3. Theorem 6. The graph 2 × mB has diameter D = DB + 1. 12
$' $ tP (x, 0, 0, 0) t (x, 0, 1, 0) PP PP PP P Pt t (x, 1, 1, 0) (x, 1, 0, 0) Q Q %& & % Q Q Q Q $ $ ' ' Q Q tP Q (x, 0, 0, 1)
t (x, 0, 1, 1) P PP P P PP Pt (x, 1, 1, 1) t (x, 1, 0, 1) '
&
%&
%
Figure 3: Construction of the graph 2 × 2B Proof. The different paths of length ≤ DB + 1 from a vertex (x, i, j, l) to the destination vertices are: • (x, i, j, l) (1) , (x, j, i, q), (≤D. B. .−1), (y, j + DB − 1, i, q) • (x, i, j, l) (1) , (x, j, i, q), (≤D . . .B ), (y, j + DB , i, q) • (x, i, j, l) (1) , (x, j, i, q) (1) , (x, j, ¯i, q), (≤D. B. .−1), (y, j + DB − 1, ¯i, q) • (x, i, j, l) (1) , (x, j, i, q) (1) , (x, ¯j, ¯i, q), (≤D. B. .−1), (y, ¯j + DB − 1, ¯i, q) • (x, i, j, l) (1) , (x, k − DB − 1, ¯j, l), (≤D. B. .−1), (y, k, ¯j, l) • (x, i, j, l), (≤D . . .B ), (y, k, j, l) Here (1) , means that the adjacency rule of Definition 3 is used, while (≤k) . . . means that there exists a path of length ≤ k in the corresponding copy of B. We use this simple notation in the sequel. Theorem 7. If DB is even, 2 × mB is a (∆, D, D, 1)-graph. Proof. Let (z, h, j, l) be the deleted vertex. The cases where the proof of Theorem 6 does not guarantee that the distance between two vertices is ≤ DB +1 are: between the pair of vertices (x, i, j, l), (y, k, j, l); (z, j, h, l), (y, h, ¯j, l); ¯ ¯j, l). Different paths of length ≤ DB + 1 joining these pairs of vertices, which do not contain and (z, j, h, l), (y, h, the deleted vertex, are: • (x, i, j, l) (1) , (x, i, ¯j, l), (≤D. B. .−1), (y, ¯i, ¯j, l) (1) , (y, k, j, l) • (z, j, h, l), (≤D. B. .−1), (y, ¯j, h, l) (1) , (y, h, ¯j, l) ¯ ¯j, l) • (z, j, h, l), (≤D. B. .−1), (y, ¯j, l) (1) , (y, h, ¯j, l) (1) , (y, h, 13
4.2
The graph 4B
Let B be a bipartite graph with the same characteristics as in the previous subsection. Vertex (x, i) of a copy l, l ∈ {0, 1, 2, 3}, is denoted by (x, i, l). Definition 4. The graph 4B consists of 4 copies of the bipartite graph B joined by 4 perfect matchings between the same stable sets of B, as illustrated in Figure 4. '$ t '
t
(x, 1, 0)
$
%$ &' '$ t(x, 0, 1) t (x, 0, 0)
(x, 1, 3)
t(x, 1, 1) t &' %$ &%
(x, 0, 3)
t &
t
(x, 0, 2)
%
&% (x, 1, 2)
Figure 4: Construction of the graph 4B
The graph 4B has order N = 4NB and degree ∆ = ∆B + 1. Notice that it is a bipartite graph. Theorem 8. The graph 4B has diameter D = DB + 2. Moreover, if DB ≥ 5 and ∆B ≥ 3 the graph 4B is a (∆, D, D, 1)-graph. Proof. First, let us prove the first statement. We assume that DB is even, since for the other case the proof is similar. Moreover, without loss of generality we can choose as origin any vertex (x, 0, 0). Using the fact that B is bipartite, paths of length ≤ DB + 2 from this vertex to the different destination vertices are: • (x, 0, 0) (1) , (x, 0, 1), (≤D . . .B ), (y, 0, 1) • (x, 0, 0) (1) , (x, 0, 1), (≤D. B. .−1), (y, 1, 1) • (x, 0, 0) (1) , (x, 0, 1) (1) , (x1 , 1, 1) (1) , (x1 , 1, 2), (≤D. B. .−2), (y, 1, 2) • (x, 0, 0) (1) , (x, 0, 1) (1) , (s1 , 1, 1) (1) , (s, 1, 2), (≤D. B. .−1), (y, 0, 2) • (x, 0, 0), (≤D. B. .−1), (y, 1, 0) (1) , (y, 1, 3))) • (x, 0, 0) (1) , (s, 1, 0), (≤D. B. .−1), (y, 0, 3) 14
To prove the second statement, we can assume, without loss of generality, that the deleted vertex is (z, 0, 0), and again we assume that DB is even, since for the other case the proof is similar. The situations where the proof of the first part of this theorem does not guarantee that the distance between two vertices is still ≤ DB + 2 and their corresponding paths of length ≤ DB + 2 are: • (x, 0, 0) (1) , (x1 , 1, 0) (1) , (x1 , 1, 3), (≤D. B. .−2), (y, 1, 3) • (x, 0, 0) (1) , (x1 , 1, 0) (1) , (x1 , 1, 3), (≤D. B. .−2), (y, 1, 3) (1) , (y, 1, 0) • (x, 0, 0) (1) , (x1 , 1, 0) (1) , (x1 , 1, 3), (≤D. B. .−2), (y, 1, 3) (1) , (y, 1, 0) (1) , (y, 0, 0) • (x, 0, 0) (1) , (x1 , 1, 0) (1) , (x1 , 1, 3), (≤D. B. .−2), (y, 1, 3) (1) , (y, 0, 3) • (x, 1, 0) (1) , (x, 1, 3), (≤D . . .B ), (y, 1, 3) (1) , (y, 1, 0) • (x, 1, 0) (1) , (s, 0, 0) (1) , (s, 0, 1), (≤D. B. .−1), (y, 1, 1) • (x, 1, 0) (1) , (s, 0, 0) (1) , (s, 0, 1), (≤D . . .B ), (y, 0, 1)
5
Compound graphs
Let Gi , i = 1, 2, be two graphs with degree ∆i and diameter Di . The basic compound graph G1 [G2 ] is constructed by replacing each vertex x of G2 by a copy Gx1 of G1 , and each edge xy ∈ G2 by one edge that joins one vertex of Gx1 with another vertex of Gy1 ; see [5]. J. Bond and C. Peyrat studied the vulnerability of the compound graphs G1 [G2 ] when G2 = Kn is a complete graph (D2 = 1) in [12]. They proved that, if G1 is a (∆, D1 , 2D1 + 2, 1) graph then G1 [Kn ] is a (∆, 2D1 + 1, 2D1 + 2, 1) graph. '
Gx
&
t t
$ ' t Bs
t % &
$ %
Figure 5: Construction of a graph G ∧ B. Other kinds of compound graphs have been presented, for instance, the compound graphs G ∧ B, also denoted by DQ∧ , (see [41]) and B0 ∇B1 (see [24]). For instance, the compound graph G ∧ B (see [43]) is constructed in the same way as a G1 [G2 ] graph, but in this case G2 = (V1 ∪ V2 , E) is a complete bipartite graph and each vertex x ∈ V1 is replaced by a copy Gx of a graph G, with order NG , degree ∆G and diameter DG , while each vertex 15
y ∈ V2 is replaced by a copy B y of a bipartite graph B = (VB , ∪UB , EB ) such that |VB | = |UB | = nB =
NB 2 ,
with
degree ∆B and diameter DB . Besides, each edge xy ∈ G2 is replaced by two edges according to Figure 5, in such a way that each vertex of a type of copy is adjacent to at least one vertex of a different type of copy. This graph has diameter D ≤ DG + DB + 1. Indeed, since each vertex of one kind of copy is adjacent to at least one vertex of the other kind of copy, it suffices to show that a path of length at most DG + DB exists between any vertex of G (let us say xG ) and any vertex of B (let us say xB ). From xG , and after ≤ DG steps we can reach a vertex of the same copy of xG which is adjacent to a vertex belonging to the same copy of vertex xB , which is at distance ≤ DB − 1 of xB . Hence, the distance between vertices xG and xB is d(xG , xB ) ≤ DG + 1 + DB − 1 = DG + DB If we take NG copies of B and
NB 2
copies G to construct G ∧ B, we can denote vertex s ∈ {0, 1, . . . , NG − 1} of
the copy t ∈ {0, 1, . . . , nB − 1} of the graph G by (s, 0, t). Similarly, vertex t ∈ {0, 1, . . . , nB − 1} of the copy s ∈ {0, 1, . . . , NG − 1} of the subset Vi , i = 0, 1, of the bipartite graph B is denoted by (t, 1, i, s). According to Figure 6, the adjacency rules are as follows: vertex (s, 0, t) is adjacent to vertices (t, 1, 0, s) and (t, 1, 1, s). Observe that Figure 6 does not show all the copies, but only Gt as a generic copy of G, and B s as a generic copy of B. The graph G ∧ B thus constructed has degree ∆ = max{∆G + 2, ∆B + 1} and order N = nB NG + 2nB NG = 3nB NG = 32 NB NG . ' $ t(t, 1, 0, s) tX (s, 0, t) XXX XXX Xt(t, 1, 1, s) & % & Bs
' Gt
$ %
Figure 6: Construction of a graph G ∧ B with order N = NG N2B + NG NB = 32 NB NG and degree ∆ = max{∆G + 2, ∆B + 1}. Although the G ∧ B graph is not bipartite, for vertices xG and xB in different copies d(xG , xB ) ≤ D − 1, where D is the diameter of G ∧ B. This property is used below to construct the graph G ∧1 B. By using the illustration of graph G ∧ B in Figure 6 we construct the graph G ∧1 B joining two copies of such graph according to the scheme shown in Figure 7. Notice that third digit of the vertices in copies of G (the forth in corresponding copies of B) denotes the copy of such graph G ∧ B. We remark that Figure 7 shows only a copy of G, G0,t , and another of B, B 0,s , for the first graph G ∧ B, and also a copy of G, G1,t , and another of B, B 1,s , for the second graph G ∧ B, together with the adjacencies between them. 16
$ ' (t, 1, 0, 0, s) ' $ t ((( (((( (s, 0, 0, t) ( th( hhhh hh @ S hh t (t, 1, 1, 0, s) &S@ % S@ & % S@ S @ S @ S @ B 1,s $ ' S @ G1,t (t, 1, 0, 1, s) ' $ t S @ ((( (((( S th ( (s, 0, 1, t) ( hhh hhhhS h St (t, 1, 1, 1, s) & % & % B 0,s
G0,t
Figure 7: Construction of a graph G ∧1 B
The graph G ∧1 B has degree ∆ = max{∆G + 5, ∆B + 3} and order N = 3NB NG . Reasoning as for the graph G ∧ B, it can easily be verified that the diameter of the graph G ∧1 B is ≤ DB + DG + 1. Theorem 9. The graph G ∧1 B is a (∆, D, D, 1)-graph. Proof. In order not to make this proof too long we assume that the deleted vertex is (z, 0, p, x), the proof for the other case (the deleted vertex is (t, 1, j, p, s)) being similar. The different situations are: 1. From (s, 0, p, x) to (t, 0, p, x) 2. From (s, 0, p, x) to (t, 0, r, y), y 6= x 3. From (s, 0, p, x) to (t, 1, j, r, n) 4. From (s, 0, r, y) to (t, i, j, q, n), y 6= x 5. From (s, 1, k, r, t) to (w, 1, j, q, n) Paths of length ≤ DG + DB + 1 for these cases, which do not contain the deleted vertex, are: 1. From vertex (s, 0, p, x) in one step according to Figure 7, we arrive at vertex (s, 0, p¯, x), which is at distance ≤ DG of vertex (t, 0, p¯, x), which is adjacent to the destination vertex (t, 0, p, x). For short we denote this path as: (s, 0, p, x) (1) , (s, 0, p¯, x), (≤D . . .G ), (t, 0, p¯, x) (1) , (t, 0, p, x), and use this notation for the remaining paths. 2. (s, 0, p, x) (1) , (x, 1, 0, 0, s), (≤D. B. .−1), (y, 1, DB − 1, 0, s) (1) , (s, 0, p, y), (≤D . . .B ), (t, 0, r, y) 3. (s, 0, r, x), (≤D . . .G ), (n, 0, r, y) (1) , (y, 1, j − DB − 1, n), (≤D. B. .−1), (t, 1, j, r, n) 17
4. (s, 0, r, y) (1) , (s, 0, r¯, y), (≤D . . .G ), (n, 0, r¯, y) (1) , (y, 1, j − DB − 1, n), (≤D. B. .−1), (t, 1, j, r, n) 5. (s, 1, k, r, t), (≤D. B. .−1), (w, 1, k + DB − 1, r, t) (1) , (t, 0, p¯, w), (≤D . . .G ), (n, 0, p¯, w) (1) , (w, 1, j, q, n) For instance, a particular case of this construction is the graph K7 ∧1 H7 which is a (11, 8, 8, 1)− graph with order N = 3 · 7 · 39216 = 823536. This is the largest known order for those parameters. Following the same interconnection scheme (Figure 7) applied to other G∧B graphs, we can derive new G∧1 B graphs which are also (∆, D, D, 1)-graphs. It is possible to modify the graph G ∧1 B of Figure 7 and obtain large (∆, D, D, 1)-graphs. For instance, Figure 8 illustrates a modification of the graph G ∧1 B. This graph results from the union of 2 subsets of NB /2 copies of G and 3 subsets of NG copies of B. Thus, the graph has order N = 2(NB /2)NG + 3NG NB = 4NB NG and degree ∆ = max{∆G + 7, ∆B + 3}. If DG ≥ 1 it can be verified (reasoning as in the proof of Theorem 9) that the graph is still a (∆, DG + DB + 1, DG + DB + 1, 1)–graph. For instance, if we use as G the graph K7 and as B the bipartite graph H9 the construction of Figure 8 provides a (13, 8, 8, 1)−graph with order N = 4 · 7 · 132860 = 3720080, whereas if we use as G the graph K9 and as B the bipartite graph H11 the construction of Figure 8 provides a (15, 8, 8, 1)−graph with order N = 4 · 9 · 354312 = 12755232. These are the largest known orders for such parameters. $ ' (t, 1, 0, 0, s) t t (t, 1, 1, 0, s) % & $ ' (t, 1, 0, 1, s) ' $ (((t ( ( ( ( ( (s, 0, 0, t) ( t hhhh h h h @ S ht (t, 1, 1, 1, s) h &S@ % S@ & % S @ S @ @ S S @ $ S' @ (t, 1, 0, 2, s) ' $ S (@ (t (((S ( ( ( t ( (s, 0, 1, t) h hhh hhhhS h St (t, 1, 1, 2, s) & % & %
Figure 8: Construction of a graph G ∧1 B modified 18
When NG is even, it is possible to construct a graph G∧B according to Figure 9 where now s ∈ {0, 1, . . . , NG /2− 1}. It is made up of NG /2 copies of the bipartite graph B and NB /2 copies of the bipartite graph G. Therefore, the graph has order N = NG NB , degree ∆ = max{∆G + 1, ∆B + 1}, and diameter D = DG + DB + 1. ' Gt
(s, 0, 0, t)
.
.
.
.
&
(s, 0, 1, t)
t
.
t
$ ' t(t, 1, 0, s) Bs
.
.
$
.
t(t, 1, 1, s) % &
%
Figure 9: Construction of a graph G ∧ B with order N = NB NG and degree ∆ = max{∆G + 1, ∆B + 1} . In addition, if the numbers of copies of G and B of the graph G ∧ B schematized in Figure 9 are even, we can associate each copy of G (B) of this graph G ∧ B with another copy of G (B). Now we modify the graph in Figure 9 by increasing the degree of each vertex in such a way that each vertex of a copy is adjacent to a vertex of the associated copy. The previous graph is the first type of graph G ∧2 B, and it has order N = NG NB , degree ∆ = max{∆G + 2, ∆B + 2} and diameter D = DG + DB + 1. Next we give the construction of the second type of graph G ∧2 B. Let us consider the graphs G ∧ B whose construction is shown in Figures 6 and 9, and we assume that the number of copies of G is even. As previously, we associate each copy of G of this graph G ∧ B with another copy of G, whereas we associate subset VB (UB ) of copy s of B with the subset UB (VB ) of copy s − 1 (s + 1) of B, where the latest computations are modulo the number of copies of B. As previously, we modify such graphs by increasing the degree of each vertex in such a way that each vertex of a copy G is adjacent to a vertex of the associated copy, but now each vertex of a subset of B is adjacent to a vertex of the associated subset of B. This graph is the second type of graph G ∧2 B. We can obtain more graphs G ∧2 B by duplicating, for instance, the copies of B. For example, the first type of abovementioned graph G ∧2 B that has degree ∆ = max{∆G + 2, ∆B + 2} and N = NG NB . In case where we duplicate the copies of B once the new graph G ∧2 B has degree ∆ = max{∆G + 3, ∆B + 2} and N = 32 NG NB . In the same way we can construct a graph G ∧2 B with degree ∆ = max{∆G + 5, ∆B + 2} and N = 52 NG NB . The graph G ∧2 B is not a (∆, D, D, 1)-graph in general. Fortunately, under certain conditions the graph G ∧2 B is a (∆, D, D, 1)-graph. This result is given in Theorem 10, whose proof is omitted because it is similar to the proof of Theorem 9; see also [23]. Let us consider the conditions: a) Even DB ≥ 4, NB is a multiple of 4, DG ≥ 2, ∆ ≥ ∆B + 2, and ∆ ≤ ∆G + 1 + 2α, α ∈ N b) Even DB ≥ 4, NB is a multiple of 4, and DG ≤ 1, ∆ ≥ ∆B + 2, and ∆ ≤ ∆G + 1 + 4α, α ∈ N, or even NG
19
or DG ≤ 2 (where α denotes the number of duplications of the copies of the bipartite graph B). Theorem 10. If conditions a) or b) are satisfied, then the graph G ∧2 B is a (∆, D, D, 1)-graph. For example, if we use as G the graph HS (the Moore graph for degree 7 and diameter 2 with 50 vertices) and as B the graph H7 (the bipartite Moore graph for degree 8 and diameter 6 with 39216 vertices), for the first type of graph G ∧2 B, where ∆ = max{∆G + 3, ∆B + 2} and N = 23 NG NB , we obtain a (10, 9, 9, 1)−graph with order N =
3 2 (50)39216
= 2941200. Moreover, if we use HS and H9 (the Moore graph for degree 10 and
diameter 6) for the first construction of graph G ∧2 B, where ∆ = max{∆G + 5, ∆B + 2} and N = we obtain a (10, 9, 9, 1)−graph with order N =
5 2 (50)132860
5 2 NG NB ,
= 16607500. The last example of graph G ∧2 B
we give is as follows: if G is Q′8 (a graph with degree 9, order 585 and diameter 3) and B is H9 , which has degree 10, diameter 6 and order 132860 (which is a multiple of 4), for the second type of graph G ∧2 B, where ∆ = max{∆G + 3, ∆B + 2}, we have a (11, 10, 10, 1)−graph with order N = 32 (585)132860 = 116584650,which, as the previous examples, appears in the Table of largest known (∆, D, D, 1)−graphs (Table 1). To construct the graph B0 ∇B1 [23, 24] we take some copies of two bipartite graphs Bi = (Vi ∪ Ui , Ei ), |Vi | = |Ui | = ni =
Ni 2 ,
and degree ∆i , i ∈ {0, 1}; and we join them in such a way that each vertex of a copy of
Bi , i ∈ {0, 1}, is adjacent to at least one vertex of a copy of the other bipartite graph, and there are (at least) four edges between different types of copies of the bipartite graphs, according to Figure 10. The graph B0 ∇B1 ' B0t ' $ ' t t t Q Q Q Q Q t Qt t & % & &
B1s $ $ t
t
% %
Figure 10: Construction of a graph B0 ∇B1 . has diameter D0 + D1 . For example, if the degree of B0 ∇B1 is ∆ = max{∆0 + 2, ∆1 + 2} then the graph B0 ∇B1 is composed by
N1 2
copies of B0 and
N0 2
copies of B1 . Therefore, its order is N = N0 N21 +
degree of B0 ∇B1 is ∆ = max{∆0 + 2, ∆1 + 1} and N1 is a multiple of 4, its order is N =
N0 2 N1
N0 N41
+
= N0 N1 . If the
N0 2 N1
= 43 N0 N1 .
Finally, if the degree of B0 ∇B1 is ∆ = max{∆0 + 1, ∆1 + 1} and N0 and N1 are multiple of 4, its order is N = 12 N0 N1 . Analogously to the construction of graph G ∧1 B, we can construct the graph B0 ∇1 B1 from two copies of B0 ∇B1 . It can be verified that B0 ∇1 B1 is a (∆, D, D, 1)-graph with D = D0 + D1 . As in the graph G ∧1 B, we can, for instance, duplicate the copies of B1 thereby obtaining a new (∆, D, D, 1)-graph. 20
For example, if take two copies of the graph B0 ∇B1 , with degree max{∆0 + 1, ∆1 + 1} and, therefore, order N0 N1 2 ,
to construct a graph B0 ∇1 B1 , we obtain (∆, D0 + D1 , D0 + D1 , 1)−graph with degree ∆ = max{∆0 +
3, ∆1 + 3} (recall that we join the two copies of B0 ∇B1 increasing the degree of each vertex in two units, one with a vertex of the same copy and other with a vertex of different copy) and order N = N0 N1 . For instance, if we use the bipartite graphs Q5 and H5 we obtain a (9, 10, 10, 1)−graph with order N = (312)7812 = 2437344, which is the largest known for such parameters. There are several large invulnerable graphs of type B0 ∇1 B1 constructed like the previous graph (where the order of B0 ∇B1 is
N0 N1 2 );
see Table 1. If we take now two copies
of the graph B0 ∇B1 with degree max{∆0 + 2, ∆1 + 1} and order
3 4 N0 N1
we obtain a graph B0 ∇1 B1 with order
N = 32 N0 N1 that is a (∆, D0 + D1 , D0 + D1 , 1)−graph, where ∆ = max{∆0 + 5, ∆1 + 3}. For example using the bipartite graphs P5 and H7 we have a (11, 9, 9, 1)−graph with order N =
3 2 (62)39216
= 3647088, which is the
largest known for such parameters. If the number of copies of B0 and B1 are even, the graph B0 ∇2 B1 can be constructed in the same way as we have presented the graph G ∧2 B. The graph B0 ∇2 B1 has the same order as the graph B0 ∇B1 and degree one unit more than the degree of B0 ∇B1 . However, the graph B0 ∇2 B1 is not a (∆, D, D, 1) graph in general. Fortunately, under certain conditions G ∧2 B is a (∆, D, D, 1)-graph. This result is given in Theorem 11, whose proof is omitted because it is similar to the proof of Theorem 9; see also [23]. Theorem 11. Let us consider the graph B0 ∇2 B1 composed by copies of two bipartite graphs Bi = (Vi ∪ Ui , Ei ), |Vi | = |Ui | = ni =
Ni 2 ,
and degree ∆i ,i ∈ {0, 1}. If a) D1 ≥ 5, b)N1 is a multiple of 8, and c1 ) N1 is a multiple
of 8 and D1 ≥ 2 or c2 ) N0 is multiple of 4 and D0 ≥ 3 or c3 ) N0 is multiple of 4 and ∆ = ∆0 + 1 + 2n, n ∈ N, then the graph G ∧2 B is a (∆, D, D, 1)-graph. As in the graph G ∧2 B, we can duplicate the copies of B1 obtaining another (∆, D, D, 1)-graph. For instance, if we use the graphs Q5 and H7 for the construction of B0 ∇B1 with degree max{∆0 +1, ∆1 +1} and order 21 N0 N1 , so that N0 and N1 are multiple of 4, we obtain a (10, 10, 10, 1)-graph. However, although the degree of the vertices of H7 is 8+1+1 = 10, the degree of the vertices of Q5 is 6+1+1 = 8. Hence, we can duplicate the
N0 4
copies of H7
twice. The degree of the vertices of Q5 is now 10 (it has increased one unit for each duplication of the copies of B), whereas the degree of the vertices of copies of H7 still keeps 10. Thus, we have a (10, 10, 10, 1)-graph with order N=
N0 N1 2
+ 2 N40 N1 = N0 N1 = 312(39216) = 12235392, which is the largest known for a (10, 10, 10, 1)-graph.
21
6
Some particular invulnerable graphs
In this section, we present four special graphs which have some similarities with the (∆, D) graphs presented in [46]. The reader can check that all of them are (∆, D, D, 1)-graphs. The graph 6 K1,3 is constructed by joining 6 copies of the K1,3 ; see Figure 11. t bi b1 b
b
" t i b"
"
"
t bi2
a
t bi0
Figure 11: Copy i of K1,3 graph The adjacency rules between copies are i
i+j
a ∼a
,
bik
j ∈ {1, −1, 2, −2};
∼
(
bi+j k
j ∈ {1, −1, 2, −2}
bi+3 k+l
l ∈ {1, −1}
The graph 6 K1,3 is a (7, 2, 2, 1) graph. The graph 17 K1,1 , is made up of 17 copies of an edge ai ∼ bi which are joined by the adjacency rules ai ∼ ai+j
bi ∼ bi+k
j ∈ {1, −1}
k ∈ {4, −4}
The graph 17 K1,1 is a (3, 5, 5, 1). This construction can be schematized as in Figure 12. HHt
±1
17 ×
t H H
±4
Figure 12: Graph 17K1,1 We use this representation in Figure 13 for the last two graphs. The graph 13K1,3 is a (3, 6, 6, 1) graph with 52 vertices and the graph 31K1,3 is a (3, 8, 8, 1) graph with 124 vertices.
Acknowledgment The authors wish to thank the anonymous referees for their valuable comments and helpful suggestions.
22
±1t
b
13 ×
@t "
±1t
±8
b
b
bt"
"
"
b
@t "
±7
b
b
31×
tH H
" bt"
"
tH H
±3
±6
Figure 13: Graphs 13K1,3 and 31K1,3
References [1] C. Balbuena, X. Marcote, and D. Ferrero, Diameter vulnerability of iterated line digraphs in terms of the girth, Networks 45 (2005), 49–54. [2] C.T. Benson, Minimal regular graphs of girth eight and twelve, Canad. J. Math. 18 (1966), 1091–1094. [3] J.-C. Bermond, J. Bond, M. Paoli, and C. Peyrat, “Graphs and interconnection networks, diameter and vulnerability,” Surveys in Combinatorics, London Math Soc Lecture Notes Ser, 82, Cambridge Univ Press, Cambridge, 1983, pp. 1–30. [4] J-C. Bermond, C. Delorme, and G. Fahri, Large graphs with given degree and diameter. II, J Comb Theory B 36 (1984), 32–48. [5] J.-C. Bermond, C. Delorme, and J.J. Quisquater, Grands graphes non dirig´es de degr´e et diam`etre fix´es, Ann Dicrete Math 17 (1982), 65–67. [6] J.-C. Bermond, N. Homobono, and C. Peyrat, Large fault-tolerant interconnection networks, Graphs Combin 5 (1989), 107–123. [7] N.L. Biggs, Algebraic graph theory, Cambridge University Press, Cambridge, 1974. [8] N.L. Biggs and D.H. Smith, On trivalent graphs, Bull London Math Soc 3 (1971), 155–158. [9] F. T. Boesch and A. P. Felzer, A general class of invulnerable graphs, Networks, 2 (2007), 261-283. [10] J. Bond, Constructions de grands r´eseaux d’interconnexion, Th`ese de 3-i`eme cycle, LRI, Universit´e de ParisSud, France, 1984. [11] J. Bond, Constructions de grands r´eseaux d’interconnexion, Th`ese d’´etat, LRI, Universit´e de Paris-Sud, France, 1987. 23
[12] J. Bond and C. Peyrat, Diameter vulnerability in networks, Graph Theory with Application to Algorithms and Computer Science, Wiley-Intersci Publ, Wiley, New York, 1985, pp. 123–149. [13] J. Bond and C. Peyrat, Diameter vulnerability of some large interconnection networks. Nineteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1988). Congr Numer 66 (1988), 267–282. [14] F. Cao, D-Z. Du, S. Han, D. Kim, and T. Yu, Line digraph iterations and diameter vulnerability, Taiwanese J Math 3 (1999), 281–290. [15] A. Clebsch, Ueber die Fl¨ achen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen, J Reine Angew Math 69 (1868), 142–184. [16] F.R.K. Chung and M.R. Garey, Diameter bounds for altered graphs, J Graph Theory 8 (1984), 511–534. [17] C. Delorme, personnal communication to J. G´omez and J.L.A. Yebra, 2009. [18] D.Z. Du, D.F. Hsu, and Y.D. Lyuu, On the diameter vulnerability of Kautz digraphs, Discrete Math 151 (1996), 81–85. [19] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach, Morgan Kaufmann, 2002. [20] D. Ferrero and C. Padr´ o, New bounds on the diameter vulnerability of iterated line digraphs, Discrete Math 233 (2001), 103–113. [21] M.A. Fiol, J.L.A. Yebra, and I. Alegre, Line digraph iterations and the (d, k) problem, IEEE Trans on Comp C-33, no. 5, (1984), 400-403. [22] A. Gewirtz, Graphs with maximal even girth, Canad J Math 21 (1969), 915–934. [23] J. G´omez, Di´ ametro y vulnerabilidad en redes de interconexi´on, PhD. dissertation, UPC, Barcelona, September 1986. [24] J. G´omez and M.A.Fiol, Dense compound graphs, Ars Combin 20-A (1985), 211–235. [25] J. G´omez and M. Miller, Two new families of large compound graphs, Networks 47 (2006), 140–146. [26] J. G´omez, P. Morillo, and C. Padr´ o, Large (d, D, D′ , s)-bipartite digraphs, Discrete Appl Math 59 (1995), 103–114.
24
[27] J. G´omez, I. Pelayo, and C. Balbuena, Diameter vulnerability of GC graphs, Discrete Appl Math 130 (2003), 395–416. [28] W.H. Haemers, Eigenvalue techniques in design and graph theory, Mathematical Centre Tracts 121, Mathematisch Zentrum, Amsterdam, 1980. [29] A.J. Hoffman and R.R. Singleton, On Moore graphs with diameter 2 and 3, IBM J Res Dev 4 (1960), 497–504. [30] W.H. Kautz, Design of optimal interconnection networks for multiprocessor, Architecture and Design of Digital Computer, Nato Advanced Summer Institute, 1969, pp. 249–272. [31] J.G. Kuhl. and S.M. Reddy, Fault-tolerance considerations in large multiprocessor systems, IEEE Computer (1986), 56–67. [32] A. Mamut and E. Vumar, Vertex vulnerability parameters of Kronecker products of complete graphs, Inform Process Lett 106 (2008), 258–262. ˇ an [33] M. Miller and J. Sir´ ˇ, Moore graphs and beyond: A survey of the degree/diameter problem, Electron J Combin DS 14 (2005), 1–61. [34] D. Moazzami, Vulnerability in graphs—a comparative survey, J Combin Math Combin Comput 30 (1999), 23–31. [35] P. Morillo, M.A. Fiol, and J. Guitart, On the (d, D, D, s)-Digraph Problem, Proc 5th International Conference AAECC-5, Menorca, Spain, 1987, pp. 334–340 [36] X. Mu˜ noz and J. G´omez, Asymptotically optimal (∆, D′ , s)-digraphs, Ars Combin 49 (1998), 97–111. [37] C. Padr´ o and P. Morillo, Diameter vulnerability of iterated line digraphs, Discrete Math 149 (1996), 189–204. [38] C. Padr´ o, P. Morillo, and E. Llobet, Diameter-vulnerability of large bipartite digraphs, Discrete Appl Math 64 (1996), 239–248. [39] C. Peyrat, Vuln´erabilit´e dans les r´eseaux d’interconnexion, Th`ese de 3-i`eme cycle, LRI, Universit´e Paris-Sud, 1984. [40] C. Peyrat, Diameter vulnerability of graphs, Discrete Appl Math (1984), 245–250. [41] C. Peyrat, Les r´eseaux d’interconnexion et leur vuln´erabilit´e, Th`ese d’´etat, LRI, Universit´e Paris-Sud, 1987. [42] J. Plesn´ık, Note on diametrically critical graphs, Recent advances in Graph Theory, Proc. 2nd Czechoslovak Symp., Academia Prague, 1975, pp. 455–465. 25
[43] J.J. Quisquater, Structures d’interconnexion: Constructions et applications, Th`ese d’´etat, LRI, Universit´e Paris-Sud, 1987. [44] E. Sim´o and J. L. A. Yebra, The vulnerability of the diameter of folded n-cubes, Discrete Math 174 (1997), 317–322. [45] J.L.A. Yebra, Largest invulnerable graphs, in preparation. [46] J.L.A. Yebra, M.A. Fiol, and I. Alegre, Some large graphs with given degree and diameter, J Graph Theory 110 (1986), 219-224. [47] J.L.A. Yebra, V.J. Rayward-Smith, and A.P. Revitt, The (∆, d, d′ , ∆ − 1)-problem with applications to computer networks, Journal of Oper Re 33 (1991), 113-124. [48] http://www-mat.upc.es/grup de grafs/grafs/taula delta d.html [49] http://moorebound.indstate.edu/index.php/The Degree/Diameter Problem
26
