A clique is a maximal complete subgraph (other texts use maxclique for this concept). It is common to identify induced subgraphs of a graph with their vertex sets; accordingly, a clique in YAGS is actually a set of vertices of a graph such that any two vertices in the clique are adjacent in the considered graph.
The clique graph, K(G), of a graph G is the intersection graph of all the cliques of G: Each clique of G is a vertex of K(G), two of them are adjacent in K(G) if and only if they have a non-empty intersection.
A number of YAGS's features concerning cliques and clique graphs are described in this chapter.
You can get the set of all the cliques of a graph by means of Cliques (B.3-7); if you want to know the completes of given order (maximal or not) you may use CompletesOfGivenOrder (B.3-14) instead.
gap> g:=SunGraph(4);; gap> Cliques(g); [ [ 2, 4, 6, 8 ], [ 2, 3, 4 ], [ 1, 2, 8 ], [ 4, 5, 6 ], [ 6, 7, 8 ] ] gap> CompletesOfGivenOrder(g,3); [ [ 1, 2, 8 ], [ 2, 3, 4 ], [ 2, 4, 6 ], [ 2, 4, 8 ], [ 2, 6, 8 ], [ 4, 5, 6 ], [ 4, 6, 8 ], [ 6, 7, 8 ] ] gap> CompletesOfGivenOrder(g,4); [ [ 2, 4, 6, 8 ] ]
Note that CompletesOfGivenOrder uses a simple, straightforward backtracking algorithm, whereas Cliques uses the Bron-Kerbosch algorithm [4] which in our experience is the best algorithm for finding all cliques of a graph in practice. In particular, Cliques is much faster than CompletesOfGivenOrder (when comparable).
In YAGS all graphs are immutable, that is, once created, all graphs always remain exactly the same graph. If you need to modify a graph, you actually construct a new graph by copying the first graph and (for example) adding or deleting some edges (all of this in a single atomic step) therefore creating a new immutable graph. All graph-modifying operations in YAGS (e.g. AddEdges, RemoveEdges, etc.) work in this way. This is time-consuming if your work involves many frequent graph editions. On the other hand, this design decision allows us to meaningfully store all computed graph attributes within the graph itself: Since the graph is not going to change ever, it will always have the same order, size, clique number, etc. YAGS does exactly this with all graph attributes and properties. This means that no attribute is ever computed twice for the same graph and in particular it has a very clear effect on computing time:
gap> g:=RandomGraph(200);; gap> Cliques(g);;time; 5784 gap> Cliques(g);;time; 0
The clique number, ω(G), is the order of a maximum clique (all cliques are maximal, but they may be of several different orders). On the other hand, the number of cliques, is simply the cardinality of the set of all cliques.
gap> g:=SunGraph(4);; gap> CliqueNumber(g); 4 gap> NumberOfCliques(g); 5
For random graphs with edge probability p and taking b:=1/p, it is known [2] that the distribution of the clique number has a very concentrated peak around 2\log_{b}n-2\log_{b}\log_{b}n +2\log_{b}(\frac{e}{2}):
gap> GraphAttributeStatistics([10,20..70],1/2,CliqueNumber); [ [ [ 3, 29 ], [ 4, 61 ], [ 5, 9 ], [ 6, 1 ] ], [ [ 4, 5 ], [ 5, 64 ], [ 6, 31 ] ], [ [ 5, 5 ], [ 6, 64 ], [ 7, 29 ], [ 8, 2 ] ], [ [ 6, 20 ], [ 7, 72 ], [ 8, 8 ] ], [ [ 7, 55 ], [ 8, 42 ], [ 9, 3 ] ], [ [ 7, 17 ], [ 8, 75 ], [ 9, 7 ], [ 10, 1 ] ], [ [ 8, 66 ], [ 9, 32 ], [ 10, 2 ] ] ] gap> List([10,20..70],n->2*Log2(Float(n)) > -2*Log2(Log2(Float(n))) + 2*Log2(FLOAT.E/2)); [ 4.0652, 5.3059, 6.10955, 6.70535, 7.17974, 7.57437, 7.91252 ]
Not so much the distribution of the number of cliques:
gap> GraphAttributeStatistics([10,20..70],1/2,NumberOfCliques); [ [ [ 7, 4 ], [ 8, 4 ], [ 9, 18 ], [ 10, 23 ], [ 11, 23 ], [ 12, 13 ], [ 13, 8 ], [ 14, 5 ], [ 16, 1 ], [ 17, 1 ] ], [ [ 36, 1 ], [ 40, 2 ], [ 41, 3 ], [ 42, 1 ], [ 43, 4 ], [ 44, 4 ], [ 45, 2 ], [ 46, 4 ], [ 47, 1 ], [ 48, 5 ], [ 49, 2 ], [ 50, 1 ], [ 51, 5 ], [ 52, 6 ], [ 53, 6 ], [ 54, 5 ], [ 55, 6 ], [ 56, 4 ], [ 57, 5 ], [ 58, 7 ], [ 59, 4 ], [ 60, 2 ], [ 61, 3 ], [ 62, 3 ], [ 63, 4 ], [ 64, 3 ], [ 66, 3 ], [ 67, 1 ], [ 68, 1 ], [ 72, 1 ], [ 77, 1 ] ], [ [ 130, 1 ], [ 133, 1 ], [ 135, 1 ], [ 137, 1 ], [ 142, 1 ], --- many more lines here --- [ 4626, 1 ], [ 4629, 1 ] ] ]
Whenever we have a graph G, we can compute its clique graph K(G), which is the intersection graph of the cliques of G. Much work has been done on clique graphs [29][24][20] and they have even been applied to Loop Quantum Gravity [26][25][27]. It is know that deciding whether a given graph is a clique graph (G≅ K(H) for some H) is NP-complete [1].
Computing the clique graph of a graph is clearly an exponential time operation in the worst case as the maximum number of cliques of a graph of order n is \alpha\times 3^{\frac{n-\alpha}{3}}= \Theta(3^{\frac{n}{3}}) [21] (here α it taken such that α ∈ {2,3,4} and n≡ α mod 3). However, very often the number of cliques in a graph is much smaller; the following experiment shows that the number of cliques of a graph on 50 vertices is likely between 700 and 1300 instead of the maximum possible which is 2×3^16=86093442.
gap> GraphAttributeStatistics(50,1/2,NumberOfCliques); [ [ 756, 1 ], [ 762, 1 ], [ 770, 1 ], [ 795, 1 ], [ 826, 2 ], [ 832, 1 ], [ 834, 1 ], [ 835, 1 ], [ 856, 1 ], [ 860, 1 ], [ 861, 1 ], [ 867, 2 ], [ 870, 1 ], [ 871, 2 ], [ 872, 1 ], [ 886, 1 ], [ 887, 1 ], [ 891, 1 ], [ 896, 1 ], [ 897, 2 ], [ 898, 1 ], [ 905, 1 ], [ 911, 1 ], [ 916, 2 ], [ 920, 2 ], [ 923, 2 ], [ 934, 1 ], [ 938, 1 ], [ 940, 1 ], [ 942, 1 ], [ 943, 1 ], [ 944, 1 ], [ 949, 1 ], [ 953, 1 ], [ 963, 1 ], [ 965, 1 ], [ 966, 1 ], [ 967, 2 ], [ 970, 1 ], [ 971, 1 ], [ 972, 1 ], [ 973, 2 ], [ 975, 1 ], [ 978, 1 ], [ 985, 1 ], [ 986, 1 ], [ 988, 1 ], [ 993, 1 ], [ 994, 2 ], [ 997, 1 ], [ 998, 1 ], [ 999, 2 ], [ 1002, 1 ], [ 1008, 1 ], [ 1015, 1 ], [ 1020, 2 ], [ 1022, 1 ], [ 1025, 1 ], [ 1026, 1 ], [ 1028, 1 ], [ 1029, 1 ], [ 1034, 1 ], [ 1047, 1 ], [ 1049, 1 ], [ 1054, 1 ], [ 1062, 1 ], [ 1067, 1 ], [ 1069, 1 ], [ 1071, 1 ], [ 1075, 1 ], [ 1077, 1 ], [ 1087, 1 ], [ 1088, 1 ], [ 1097, 1 ], [ 1098, 1 ], [ 1102, 1 ], [ 1135, 1 ], [ 1139, 1 ], [ 1154, 1 ], [ 1159, 2 ], [ 1165, 1 ], [ 1187, 1 ], [ 1191, 1 ], [ 1192, 1 ], [ 1203, 1 ], [ 1217, 1 ], [ 1236, 1 ] ] gap> 2*3^16; 86093442
Therefore, we can often compute cliques and clique graphs in practice, despite the worst case exponential time. Also, CliqueGraph is an attribute of graphs (as most operations in YAGS) and hence, the result is stored within the graph in order to prevent unnecessary recalculation:
gap> g:=RandomGraph(80);; gap> kg:=CliqueGraph(g);;time; 26499 gap> kg2:=CliqueGraph(g);;time; 0 gap> kg2=kg; true
Note that the last line in the previous example is not testing for isomorphism, it only tests whether both adjacency matrices are equal. It remains possible, however, that the graph at hand is one of those with a huge number of cliques. We can limit the maximum number of cliques to be computed in Cliques and CliqueGraph using the optional extra parameter maxNumCli: With this extra parameter, the computation is aborted when the number of computed cliques reaches maxNumCli.
gap> g:=OctahedralGraph(3);; gap> CliqueGraph(g,1000); Graph( Category := SimpleGraphs, Order := 8, Size := 24, Adjacencies := [ [ 2, 3, 4, 5, 6, 7 ], [ 1, 3, 4, 5, 6, 8 ], [ 1, 2, 4, 5, 7, 8 ], [ 1, 2, 3, 6, 7, 8 ], [ 1, 2, 3, 6, 7, 8 ], [ 1, 2, 4, 5, 7, 8 ], [ 1, 3, 4, 5, 6, 8 ], [ 2, 3, 4, 5, 6, 7 ] ] ) gap> g:=OctahedralGraph(30);; #this has 2^30=1073741824 cliques. gap> CliqueGraph(g,1000); fail
Alternatively we can use the InfoLevel mechanism (B.24-3) to be informed about the progress of clique-related operations in YAGS. This way we can abort the calculation (by typing Ctr-C) in case we see that it will take eons to finish.
In YAGS the vertices of a graph are always [1, 2, ..., Order(G)], but often they also have some names. This names depend on the way in which the graph is constructed and reflect the origin of the graph. We can get the names of the vertices by using VertexNames (B.22-3). In the case of clique graphs, the vertex names are the corresponding cliques of the original graph.
gap> g:=SunGraph(4); Graph( Category := SimpleGraphs, Order := 8, Size := 14, Adjacencies := [ [ 2, 8 ], [ 1, 3, 4, 6, 8 ], [ 2, 4 ], [ 2, 3, 5, 6, 8 ], [ 4, 6 ], [ 2, 4, 5, 7, 8 ], [ 6, 8 ], [ 1, 2, 4, 6, 7 ] ] ) gap> kg:=CliqueGraph(g); Graph( Category := SimpleGraphs, Order := 5, Size := 8, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4 ], [ 1, 2, 5 ], [ 1, 2, 5 ], [ 1, 3, 4 ] ] ) gap> VertexNames(kg); [ [ 2, 4, 6, 8 ], [ 2, 3, 4 ], [ 1, 2, 8 ], [ 4, 5, 6 ], [ 6, 7, 8 ] ] gap> Cliques(g); [ [ 2, 4, 6, 8 ], [ 2, 3, 4 ], [ 1, 2, 8 ], [ 4, 5, 6 ], [ 6, 7, 8 ] ]
Hence, in the previous example, vertex 1 of kg is (the one corresponding to) the clique [ 2, 4, 6, 8 ] of g, and vertex 2 is [ 2, 3, 4 ] etc.
Iterated clique graphs are obtained by applying the clique operator several times. As before, we may wonder which vertices of K^3(g) constitute the clique corresponding to some vertex of K^4(g) and this can be settled using VertexNames as explained in Section 3.2. But what if we want to know which vertices of g constitute some vertex of K^4(g)? This could be done using VertexNames at level K^4(g) and then transforming each of the obtained vertices (in K^3(g)) using VertexNames of K^3(g) and so on... but YAGS already has an operation that does exactly that. The basement of a vertex x of an iterated clique graph K^n(g) with respect to some previous iterated clique graph K^m(g) (with m≤ n) is, roughly speaking, the set of vertices of K^m(g) that constitute the vertex x, that is, the set of vertices of K^m(g) which are needed for x to exist (see Basement (B.2-3) for a formal definition).
gap> K:=CliqueGraph; <Attribute "CliqueGraph"> gap> g:=Icosahedron;;Order(g); 12 gap> kg:=K(g);;Order(kg); 20 gap> k2g:=K(kg);;Order(k2g); 32 gap> k3g:=K(k2g);;Order(k3g); 92 gap> k4g:=K(k3g);;Order(k4g); 472 gap> VertexNames(kg)[1];VertexNames(kg)[3]; [ 1, 2, 3 ] [ 1, 3, 4 ] gap> Basement(g,kg,1);Basement(g,kg,3); [ 1, 2, 3 ] [ 1, 3, 4 ] gap> VertexNames(k4g)[2];VertexNames(k4g)[9]; [ 1, 2, 55, 72, 73, 74, 80, 81, 82, 83, 84, 85, 88, 89, 90 ] [ 1, 2, 3, 4, 10, 16, 81, 82, 85, 87, 88, 89 ] gap> Basement(k3g,k4g,2);Basement(k3g,k4g,9); [ 1, 2, 55, 72, 73, 74, 80, 81, 82, 83, 84, 85, 88, 89, 90 ] [ 1, 2, 3, 4, 10, 16, 81, 82, 85, 87, 88, 89 ] gap> Basement(k2g,k4g,9); [ 1, 2, 3, 4, 5, 6, 7, 17, 19, 24, 25, 27, 28, 29, 30, 31 ] gap> Basement(kg,k4g,9); [ 1, 2, 3, 4, 5, 7, 8, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ] gap> Basement(g,k4g,9); [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]
Basements where introduced (with a different name) in [3] and used again in [23]. They have been useful to study distances and diameters on iterated clique graphs. They are also useful when dealing with stars and neckties.
Stars and neckties are useful in understanding the structure of iterated clique graphs.
Let G be a graph and x∈ G. Let us define x^*:={q∈ K(G) : x∈ q}. We say that x^* is the star of x. Observe that x^* is (induces) a complete subgraph of K(G), and may or may not be a clique of K(G) (i.e. a vertex of K^2(G)) depending on whether the star of x is a maximal complete subgraph or not.
On the other hand, a vertex in K^2(G) is of the form Q:={q_1,q_2,...,q_r} where each q_i is a clique of G (i.e. a vertex of K(G)). We say that such clique of cliques Q is a star if there is some vertex x∈ G such that x∈ q_i for all q_i∈ Q; equivalently Q is a star if the total intersection of its cliques is non-empty (i.e. ∩ Q ≠ ∅). When Q is not a star (i.e. when ∩ Q = ∅), we say it is a necktie. It is easy to show that a clique of cliques Q is a star if and only if its basement at G is exactly the closed neighborhood of a vertex N[x].
Clearly, a star is also the star of some vertex and any star of a vertex which is a clique of cliques is a star. On the other hand, if the star of a vertex x^* is not a clique of cliques, it is surely contained in some clique of cliques Q∈ K^2(G). If for each vertex x we pick such a fixed clique of cliques *(x):=Q∈ K^2(G) with x^*⊆ Q, we get the star morphism *:G→ K^2(G).
A very remarkable feature of the second iterated clique graph K^2(G) of G is that the star morphism is often injective and even an isomorphism onto its image.
gap> g:=Icosahedron;; gap> kg:=K(g);;k2g:=K(kg);; gap> ClosedNeighborhood:=function(g,x) > return Union(Adjacency(g,x),[x]); end; function( g, x ) ... end gap> closNeighs:=List(Vertices(g),x->ClosedNeighborhood(g,x)); [ [ 1 .. 6 ], [ 1, 2, 3, 6, 9, 10 ], [ 1, 2, 3, 4, 10, 11 ], [ 1, 3, 4, 5, 7, 11 ], [ 1, 4, 5, 6, 7, 8 ], [ 1, 2, 5, 6, 8, 9 ], [ 4, 5, 7, 8, 11, 12 ], [ 5, 6, 7, 8, 9, 12 ], [ 2, 6, 8, 9, 10, 12 ], [ 2, 3, 9, 10, 11, 12 ], [ 3, 4, 7, 10, 11, 12 ], [ 7 .. 12 ] ] gap> stars:=Filtered(Vertices(k2g), > Q->Basement(g,k2g,Q) in closNeighs); [ 1, 3, 5, 8, 10, 12, 15, 18, 21, 24, 27, 30 ] gap> h:=InducedSubgraph(k2g,stars);; gap> IsIsomorphicGraph(g,h); true
Hence K^2(G) is the union of two subgraphs (with some extra edges between them): One composed entirely of stars and the other composed entirely of neckties. The one composed entirely of stars is very similar to G and often even isomorphic to G.
A graph is clique-Helly when every family of pairwise intersecting cliques has a non-empty total intersection. Evidently, if G is clique-Helly, then every vertex of K^2(G) is a star. Escalante [6] showed that in the clique-Helly case, K^2(G) is isomorphic to a subgraph of G, namely, the ParedGraph (B.16-4) of G (which just removes dominated vertices) and hence the star morphism in the clique-Helly case is an isomorphism exactly when G does not have dominated vertices.
gap> g:=BoxTimesProduct(CycleGraph(4),PathGraph(4));;Order(g); 16 gap> IsCliqueHelly(g); true gap> k2g:=K(K(g));;pg:=ParedGraph(g);;Order(pg); 8 gap> IsIsomorphicGraph(k2g,pg); true gap> k4g:=K(K(k2g));;p2g:=ParedGraph(pg);;Order(p2g); 4 gap> IsIsomorphicGraph(k4g,p2g); true gap> DominatedVertices(k4g); [ ] gap> IsIsomorphicGraph(k4g,K(K(k4g))); true
When we have a graph G and its iterated clique graphs K(G), K^2(G), K^3(G), ... a natural question is: Are all the graphs in the sequence non-isomorphic to each other? The answer is "no" if and only if K^n(G)≅ K^m(G) for some n≠ m if and only if there is a finite bound for the sequence of orders of the iterated clique graphs |K^n(G)|. When this happens, we say that G is clique convergent and otherwise, we say that it is clique divergent. To determine the clique behavior of a graph consist in deciding whether it is clique convergent or clique divergent. It is an open problem whether the clique behavior is algorithmically decidable or not [15] and Meidanis even asked if the clique operator has the computing power needed to simulate any Turing Machine, see http://www.ic.unicamp.br/~meidanis/research/clique/ (fetched in 2001), but that does not prevent us from trying to determine clique behavior for specific graphs.
The first thing to try when determining the clique behavior of a graph is simply to iterate the clique operator on it and check for the orders, if we see the order stabilizes, we have a candidate where we can check for isomorphism.
gap> g:=TimesProduct(Icosahedron,CompleteGraph(3));;Order(g); 36 gap> g1:=K(g);;Order(g1); 120 gap> g2:=K(g1);;Order(g2); 156 gap> g3:=K(g2);;Order(g3); 120 gap> IsIsomorphicGraph(g1,g3); true
Often however, the orders just keep growing. But then the second thing to try (or even the first!) is to take the CompletelyParedGraph (B.3-12) of G since it is known that the clique behavior is invariant under removal of dominated vertices [8]. In the following example g is clique convergent because h is so, even if a direct calculation of the iterated clique graphs of g just ends in memory overflow.
gap> cp7:=ComplementGraph(PathGraph(7));; gap> g:=ComplementGraph(TimesProduct(cp7,cp7));;Order(g); 49 gap> g1:=K(g);;Order(g1); 204 gap> g2:=K(g1);;Order(g2); 7193 gap> g3:=K(g2);;Order(g3); --- user interrupt or recursion trap here --- brk> quit; gap> h:=CompletelyParedGraph(g);;Order(h); 1 gap> IsIsomorphicGraph(h,K(h)); true
It is even advisable construct the combined operator PK (compute the clique graph and then take the completely pared graph) and to compute the sequence of graphs under the iterated application of the PK operator: (PK)^n(G) is clique convergent (for any n) if and only if G is clique convergent.
gap> g:=WheelGraph(4,4);;Order(g); 17 gap> g1:=K(g);;Order(g1); 28 gap> g2:=K(g1);;Order(g2); 37 gap> g3:=K(g2);;Order(g3); 60 gap> g4:=K(g3);;Order(g4); 185 gap> g5:=K(g4);;Order(g5); 2868 gap> #too many cliques to continue in this way. gap> PK:=function(g) return CompletelyParedGraph(K(g)); end; function( g ) ... end gap> h1:=PK(g);;Order(h1); 24 gap> h2:=PK(h1);;Order(h2); 25 gap> h3:=PK(h2);;Order(h1); 24 gap> h3:=PK(h2);;Order(h3); 16 gap> h4:=PK(h3);;Order(h4); 13 gap> h5:=PK(h4);;Order(h5); 8 gap> h6:=PK(h5);;Order(h6); 1 gap> IsIsomorphicGraph(h6,K(h6)); true
If a graph is clique convergent, it must also be convergent under the PK operator; It is an open problem to determine whether the opposite is also true.
If G is clique convergent, then in principle we can determine that by computer (although there are sometimes insufficient memory or time) but that is not so for clique divergent graphs. Determining clique divergence for graphs can be quite challenging and there is even a graph on eight vertices (the SnubDisphenoid) which seems to be divergent but nobody has a proof of it yet [17].
gap> g:=SnubDisphenoid; Graph( Category := SimpleGraphs, Order := 8, Size := 18, Adjacencies := [ [ 2, 3, 4, 5, 8 ], [ 1, 3, 6, 7, 8 ], [ 1, 2, 4, 6 ], [ 1, 3, 5, 6 ], [ 1, 4, 6, 7, 8 ], [ 2, 3, 4, 5, 7 ], [ 2, 5, 6, 8 ], [ 1, 2, 5, 7 ] ] ) gap> g1:=K(g);;Order(g1); 12 gap> g2:=K(g1);;Order(g2); 20 gap> g3:=K(g2);;Order(g3); 56 gap> g4:=K(g3);;Order(g4); 1076
The fifth iterated clique graphs of the SnubDisphenoid has at least 7.37× 10^9 vertices, but it is estimated that the number is more likely around 10^22.
How to proceed then? Well there are many studied families of graphs whose clique behavior have been settled (including: the octahedral graphs, cographs, regular locally cyclic graphs (like the Icosahedron and the locally C_6 graphs), some circulants, clockworkgraphs, some comparability graphs, locally colorable graphs) and some techniques that may be applicable (including: retractions, covering maps, expansivity, rank-divergence, dismantlings, local cutpoints).
Two of these techniques have been successful more often than others:
(1) If your graph G has a non-trivial automorphism f:G→ G that sends each vertex outside of its closed neighborhood (f(x)not\in N[x]), then there are chances that you can apply the rank-divergence techniques [17][18].
(2) If your graph G is more like a random graph, then there are good chances that it has a retraction to a d-dimensional octahedron with at least 6 vertices, which implies the divergence of G [22]. In our experience, a good way to look up for such a retraction is to find the cliques of G and then try to see if any of the cliques extends in G to an induced octahedral graph (OctahedralGraph (B.15-1)) of at least 6 vertices. The existence of an induced octahedral subgraph with one of its faces being a clique of G is sufficient to prove the existence of a retraction from G to the octahedral subgraph [11][19].
We plan to incorporate soon an operation that applies the known techniques for clique divergence and convergence to a given graph in order to try to determine its clique behavior.
generated by GAPDoc2HTML