M. A. Pizaña

**The Icosahedron is Clique Divergent.**

Discrete Mathematics**262**(2003) 229-239.

Author version: [ ps | pdf ]**Abstract**

A clique of a graph $G$ is a maximal complete subgraph. The clique graph $k\left( G\right) $ is the intersection graph of the set of all cliques of $G$. The iterated clique graphs are defined recursively by $k^{0}\left( G\right) =G$ and $k^{n+1}\left( G\right) =k\left( k^{n}\left( G\right) \right) $. A graph $G$ is said to be clique divergent (or $k-$divergent) if $\lim_{n\rightarrow \infty }\left| V\left( k^{n}\left( G\right) \right) \right| =\infty $. The problem of deciding whether the icosahedron is clique divergent or not was (implicitly) stated in \cite{Neu2}(1981) and cited in \cite{Neu3}(1991) and \cite{Lar2}(1999). This paper proves the clique divergence of the icosahedron among other results of general interest in clique divergence theory.F. Larrión, V. Neumann-Lara, M.A. Pizaña.

**Whitney Triangulations, Local Girth and Iterated Clique Graphs.**

Discrete Mathematics**258**(2002) 123-135.

Author version: [ ps | pdf ]**Abstract**

We study the dynamical behaviour of surface triangulations under the iterated application of the clique graph operator $k$, which transforms each graph $G$ into the intersection graph $kG$ of its (maximal) cliques. A graph $G$ is said to be $k$*-divergent*if the sequence of the orders of its iterated clique graphs $o(k^{n}G)$ tends to infinity with $n$. If this is not the case, then $G$ is*eventually*$k$*-periodic,*or $k$*-bounded*: $k^{n}G\cong k^{m}G$ for some $m>n$. The case in which $G$ is the underlying graph of a regular triangulation of some closed surface has been previously studied under the additional (Whitney) hypothesis that every triangle of $G$ is a face of the triangulation: if $G$ is regular of degree $d$, it is known that $G$ is $k$-bounded for $d=3$ and $k$-divergent for $d=4$ , $5$ and $6$. We will show that $G$ is $k$-bounded for all $d\geq 7$, thus completing the study of the regular case. Our proof works in the more general setting of graphs with local girth at least $7$. As a consequence we obtain also the $k$-boundedness of the underlying graph $G$ of any triangulation of a compact surface (with or without border) provided that any triangle of $G$ is a face of the triangulation and that the minimum degree of the interior vertices of $G$ is at least $7$.F. Larrión, V. Neumann-Lara,M.A. Pizaña.

**Clique Divergent Clockwork Graphs and Partial Orders.**

Discrete Applied Mathematics**141**(2004) 195-207.

Author version: [ ps | pdf ]**Abstract**

S. Hazan and V. Neumann-Lara proved in 1996 that every finite partially ordered set whose comparability graph is clique null has the fixed point property and they asked whether there is a finite poset with the fixed point property whose comparability graph is clique divergent. In this work we answer that question by exhibiting such a finite poset. This is achieved by developing further the theory of clockwork graphs. We also show that there are polynomial time algorithms that recognize clockwork graphs and decide whether they are clique divergent.M.A. Pizaña.

**Distances and Diameters on Iterated Clique Graphs.**

Discrete Applied Mathematics**141**(2004) 255-261.

Author version: [ ps | pdf ]**Abstract**

If $G$ is a graph, its clique graph, $k(G)$, is the intersection graph of all its (maximal) cliques. Iterated clique graphs are then defined recursively by: $k^{0}(G)=G$ and $k^{n}\left( G\right) =k\left( k^{n-1}\left( G\right) \right) $. We study the relationship between distances in $G$ and distances in $k^{n}\left( G\right) $. Then we apply these results to Johnson graphs to give a shorter and simpler proof of Bornstein and Szwarcfiter's theorem \cite{Bor2}: For each $n$ there exist a graph $G$ such that $\mathrm{diam}\left( k^{n}\left( G\right) \right) = \mathrm{diam}\left( G\right)+n$. In the way, a new family of graphs with increasing diameters under the clique operator is shown.F. Larrión, C.P. de Mello, A. Morgana, V. Neumann-Lara, M.A. Pizaña.

**The Clique Operator on Cographs and Serial Graphs.**

Discrete Mathematics**282**(2004) 183-191.

Author version: [ ps | pdf ]**Abstract**

The*clique graph*of a graph $G$ is the intersection graph $K(G)$ of the (maximal) cliques of $G$. The iterated clique graphs $K^{n}(G)$ are defined by $K^{0}(G)=G$ and $K^{i}(G)=K(K^{i-1}(G))$, $i>0$ and $K$ is the clique operator. A*cograph*is a graph with no induced subgraph isomorphic to $P_{4}$. In this article we describe the $K$-behaviour of cographs and give some partial results for the larger class of serial (i.e. complement-disconnected) graphs.F. Larrión, V. Neumann-Lara, M.A. Pizaña.

**On the Homotopy Type of the Clique Graph.**

Journal of The Brazilian Computer Society**7**No.3 (2002) 69-73.

Author version: [ ps | pdf ]**Abstract**

If $G$ is a graph, its clique graph $K(G)$ is the intersection graph of all its (maximal) cliques. The complex $G^{\uparrow }$ of a graph $G$ is the simplicial complex whose simplexes are the vertex sets of the complete subgraphs of $G$.

Here we study a sufficient condition for $G^{\uparrow }$ and $K(G)^{\uparrow }$ to be homotopic. Applying this result to Whitney triangulations of surfaces, we construct an infinite family of examples which solve in the affirmative Prisner's open problem 1 in*Graph Dynamics*(Longman, Harlow, 1995): Are there finite connected graphs $G$ that are periodic under $K$ and where the second modulo $2$ Betti number is greater than $0$?F. Larrión, V. Neumann-Lara, M.A. Pizaña.

**Clique Convergent Surface triangulations.**

Matemática Contemporânea**25**(2003) 135-143.

Author version: [ ps | pdf ]**Abstract**

We show that almost all closed surfaces admit a Whitney triangulation whose underlying graph is clique convergent. The possible exceptions are the sphere, the projective plane, the torus and the Klein bottle. We also prove that any Whitney triangulation of the disk is clique null, provided that the degree of each interior vertex is at least 6.F. Larrión, V. Neumann-Lara, M.A. Pizaña, T.D. Porter.

**Self-Clique Graphs with Prescribed Clique-Sizes.**

Congressus Numerantium**157**(2002) 173-182.

Author version: [ ps | pdf ]**Abstract**

The clique graph of a graph $G$ is the intersection graph $K(G)$ of the (maximal) cliques of $G$. A graph $G$ is called self-clique whenever $G \cong K(G)$. This paper gives various constructions of self-clique graphs. In particular, we employ $(r,g)$-cages to construct self-clique graphs whose set of clique-sizes is any given finite set of integers greather than 1.M.E. Frías-Armenta, V. Neumann-Lara, M.A. Pizaña.

**Dismantlings and Iterated Clique Graphs.**

Discrete Mathematics**282**(2004) 263-265.

Author version: [ ps | pdf ]**Abstract**

Given a graph $G$ and two vertices $x,y \in V(G)$, we say that $x$ is dominated by $y$ if the closed neighbourhood of $x$ is contained in that of $y$. Here we prove that if $x$ is a dominated vertex, then $G$ and $G-\{x\}$ have the same dynamical behaviour under the iteration of the clique operator.F. Larrión, V. Neumann-Lara, M.A. Pizaña, T.D. Porter.

**A Hierarchy of Self-Clique Graphs.**

Discrete Mathematics**282**(2004) 193-208.

Author version: [ ps | pdf ]**Abstract**

The clique graph $K(G)$ of $G$ is the intersection graph of all its (maximal) cliques. A connected graph $G$ is self-clique whenever $G\cong K(G) $. Self-clique graphs have been studied in several papers. Here we propose a hierarchy of self-clique graphs: Type 3 $\subsetneq $ Type 2 $\subsetneq $ Type 1 $\subsetneq $ Type 0. We give characterizations for classes of Type 3, 2 and 1, and several new constructions. It is shown that all (but one) previously published examples of self-clique graphs are of Type 2. As applications, we give a characterization of the self-clique graphs such that at most $3$ cliques have more than two vertices (they are all of Type 2) and a description of the diamond-free graphs of Type 2.F. Larrión, V. Neumann-Lara, M.A. Pizaña, T.D. Porter.

**Recognizing Self-Clique Graphs.**

Matemática Contemporânea**25**(2003) 125-133.

Author version: [ ps | pdf ]**Abstract**

The*clique graph*$K(G)$ of a graph $G$ is the intersection graph of all the (maximal) cliques of $G$. A connected graph $G$ is*self-clique*if $G\cong K(G)$. Self-clique graphs have been studied since 1973. We proposed recently a hierarchy of self-clique graphs: Type 3 $\subsetneq $ Type 2 $\subsetneq $ Type 1 $\subsetneq $ Type 0. Here we study the computational complexity of the corresponding recognizing problems. We show that recognizing graphs of Type 0 and Type 1 is polynomially equivalent to the graph isomorphism problem. Partial results for Types 2 and 3 are also presented.F. Larrión, V. Neumann-Lara, M.A. Pizaña.

**Graph Relations, Clique Divergence and Surface Triangulations.**

Journal of Graph Theory**51**(2006) 110-122.

Author version: [ ps | pdf ]**Abstract**

This work has two aims: First, we introduce a powerful technique for proving clique divergence when the graph satisfies a certain symmetry condition. Second, we prove that each closed surface admits a clique divergent triangulation. By definition, a graph is clique divergent if the orders of its iterated clique graphs tend to infinity, and the clique graph of a graph is the intersection graph of its maximal complete subgraphs.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**Posets, Clique Graphs and their Homotopy Type.**

European Journal of Combinatorics**29**(2008) 334-342.

Author version: [ ps | pdf ]**Abstract**

Given a finite poset $P$ we associate to it two graphs which we denote by $\Omega$ and $\mho$ ($=\Omega[P^{\mathrm{op}}]$). Several standard constructions can be seen as $\Omega$ or $\mho$ for suitable posets $P$, including the comparability graph of a poset, the clique graph of a graph and the $1$-skeleton of a simplicial complex. We interpret graphs and posets as simplicial complexes using complete subgraphs and chains as simplices. Then we study and compare the homotopy types of $\Omega$, $\mho$ and $P$. As our main application we obtain a theorem, stronger than those previously known, giving sufficient conditions for a graph to be homotopy equivalent to its clique graph. We also introduce a new graph operator $H$ that preserves clique--Hellyness and dismantlability and is such that $H(G)$ is homotopy equivalent to both its clique graph and the graph $G$.F. Larrión, M.A. Pizaña.

**On Hereditary Clique Helly Self-Clique Graphs.**

Discrete Applied Mathematics**156**(2008) 1157-1167.

Author version: [ ps | pdf ]**Abstract**

A graph is*clique-Helly*if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is*hereditary clique-Helly*(abbreviated HCH) if its induced subgraphs are clique-Helly. The*clique graph*of a graph $G$ is the intersection graph of its cliques, and $G$ is*self-clique*if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of its constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to*involutive*HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.F. Larrión, V. Neumann-Lara, M.A. Pizaña.

**On Expansive Graphs.**

European Journal of Combinatorics**30**(2009) 372-379.

Author version: [ ps | pdf ]**Abstract**

The clique graph $K(G)$ of a graph $G$ is the intersection graph of its (maximal) cliques, and $G$ is*$K$-divergent*if the orders of its iterated clique graphs $K(G), K^2(G), K^3(G), \ldots$ tend to infinity. A*coaffine*graph has a symmetry that maps each vertex outside of its closed neighbourhood. For these graphs we study the notion of expansivity, which implies $K$-divergence.**Introduction**

This article presents results on expansive graphs that Víctor Neumann-Lara obtained in the late 1970's and reported mostly without proofs in \cite{Neu78} and \cite{Neu81}. The untimely death of Víctor left us to complete this project, which had started in~\cite{LNP06}. We had at hand \cite{Neu78,Neu81} and the manuscript \cite{Neu-YY} that, using his old notebooks, Víctor wrote with one of us in 1995. The original material has been thoroughly rewritten and recast in the setting of \cite{LNP06}. This allowed for a clearer and more natural presentation. Some shortcuts were found, and applications added. [...]F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**Equivariant Collapses and the Homotopy Type of Iterated Clique Graphs.**

Discrete Mathematics**308**(2008) 3199-3207.

Author version:[ ps | pdf ]**Abstract**

The clique graph $K(G)$ of a simple graph $G$ is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by $K^{0}(G)=G$, $K^{n+1}(G)=K(K^{n}(G))$. We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results it can be easily inferred that $K^{n}(G)$ is homotopy equivalent to $G$ for every $n$ if $G$ belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper we show two infinite classes of clique-divergent graphs that satisfy $G\simeq K^{n}(G)$ for all $n$, moreover $K^n(G)$ and $G$ are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**The Clique Operator on Matching and Chessboard Graphs.**

Discrete Mathematics**309**(2009) 85-93.

Author version: [ ps | pdf ]**Abstract**

Given positive integers $m,n$, we consider the graphs $G_{n}$ and $G_{m,n}$ whose simplicial complexes of complete subgraphs are the well-known matching complex $M_{n}$ and chessboard complex $M_{m,n}$. Those are the*matching*and*chessboard*graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph $G_{m,n}$ in terms of $m$ and $n$, and show that $G_{m,n}$ is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph $G_{n}$.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**Contractibility and the Clique Graph Operator**

Discrete Mathematics**308**(2008) 3461-3469.

Author version: [ ps | pdf ]**Abstract**

To any graph $G$ we can associate a simplicial complex $\Delta (G)$ whose simplices are the complete subgraphs of $G$, and thus we say that $G$ is*contractible*whenever $\Delta (G)$ is so. We study the relationship between contractibility and $K$-nullity of $G$, where $G$ is called $K$*-null*if some iterated clique graph of $G$ is trivial. We show that there are contractible graphs which are not $K$-null, and that any graph whose clique graph is a cone is contractible.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**Small Locally $nK_2$ Graphs**

Ars Combinatoria**102**(2011) 385-391.

Author version: [ ps | pdf ]**Abstract**

A locally $nK_{2}$ graph $G$ is a graph such that the set of neighbors of any vertex of $G$ induces a subgraph isomorphic to $nK_{2}$. We show that a locally~$nK_{2}$ graph $G$ must have at least $6n-3$ vertices, and that a locally $nK_{2}$ graph with $6n-3$ vertices exists if only if $n\in\{1,2,3,5\}$, and in these cases the graph is unique up to isomorphism. The case $n=5$ is surprisingly connected to a classic theorem of algebraic geometry: The adjacency relation among the vertices of the only locally $5K_2$ graph on $6n-3=27$ vertices is the same as the incidence relation among the $27$ straight lines on any nonsingular complex, projective cubic surface.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**The Fundamental Group of the Clique Graph**

European Journal of Combinatorics**30**(2009) 288-294.

Author version: [ ps | pdf ]**Abstract**

Given a finite connected bipartite graph $B=(X,Y)$ we consider the simplicial complexes of complete subgraphs of the square $B^{2}$ of $B$ and of its induced subgraphs $B^{2}[X]$ and $B^{2}[Y]$. We prove that these three complexes have isomorphic fundamental groups. Among other applications, we conclude that the fundamental group of the complex of complete subgraphs of a graph $G$ is isomorphic to that of the clique graph $K(G)$, the line graph $L(G)$ and the total graph $T(G)$.M.C. Dourado, L. Faria, M.A. Pizaña, D. Rautenbach, J.L. Szwarcfiter.

**On Alliances and Anti-Alliances in Graphs**

Discrete Applied Mathematics**163**(2014) 136-141.

Author version: [ ps | pdf ]**Abstract**

We consider complexity issues and upper bounds for defensive alliances and strong global offensive alliances in graphs. We prove that it is NP-complete to decide for a given $6$-regular graph $G$ and a given integer $a$, whether $G$ contains a defensive alliance of order at most $a$. Furthermore, we prove that determining the strong global offensive alliance number $\gamma_{\hat{o}}(G)$ of a graph $G$ is APX-hard for cubic graphs and NP-hard for chordal graphs. For a graph $G$ of minimum degree at least $2$, we prove $\gamma_{\hat{o}}(G)\leq 3n(G)/4$, which improves previous results by Favaron et al. and Sigarreta and Rodr\'{i}guez. Finally, we prove $\gamma_{\hat{o}}(G)\leq \left(\frac{1}{2}+(1+o(\delta(G)))\frac{\ln (\delta(G)+1)}{\delta(G)+1}\right)n(G).$F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**Discrete morse theory and the homotopy type of clique graphs**

Annals of Combinatorics**17**(2013) 743-754.

Author version: [ ps | pdf ]**Abstract**

We attach topological concepts to a simple graph by means of the simplicial complex of its complete subgraphs. Using Forman's discrete Morse theory we show that the strong product of two graphs is homotopic to the topological product of the spaces of their complexes. As a consequence, we enlarge the class of clique divergent graphs known to be homotopy equivalent to all its iterated clique graphs.M.E. Frías-Armenta, F. Larrión, V. Neumann-Lara, M.A. Pizaña.

**Edge contraction and edge removal on iterated clique graphs**

Discrete Applied Mathematics**161**(2013) 1427-1439.

Author version: [ ps | pdf ]**Abstract**

The clique graph $K(G)$ of a graph $G$ is the intersection graph of all its (maximal) cliques. We explore the effect of operations like edge contraction, edge removal and others on the dynamical behaviour of a graph under the iteration of the clique operator $K$. As a consequence of this study, we can now prove the clique divergence of graphs for which no previously known technique would yield the result. In particular, we prove that every clique divergent graph is a spanning subgraph of a clique divergent graph with diameter two.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**The clique behavior of circulants with three small jumps**

Ars Combinatoria**113A**(2014) 147-160.

Author version: [ ps | pdf ]**Abstract**

The clique graph $K(G)$ of a graph $G$ is the intersection graph of all its (maximal) cliques, and $G$ is said to be*clique divergent*if the order of its $n$-th iterated clique graph $K^n(G)$ tends to infinity with $n$. In general, deciding whether a graph is clique divergent is not known to be computable. We characterize the dynamical behavior under the clique operator of circulant graphs of the form $C_n(a,b,c)$ with $0<a<b<c<\frac{n}{3}$: Such a circulant is clique divergent if and only if it is not clique-Helly. Owing to the Dragan-Szwarcfiter Criterion to decide clique-Hellyness, our result implies that the clique divergence of these circulants can be decided in polynomial time. Our main difficulty was the case $C_n(1,2,4)$, which is clique divergent but no previously known technique could be used to prove it.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**Iterated clique graphs and bordered compact surfaces**

Discrete Mathematics**313**(2013) 508-516.

Author version: [ ps | pdf ]**Abstract**

The clique graph $K(G)$ of a graph $G$ is the intersection graph of all its (maximal) cliques. A graph $G$ is said to be*$K$-divergent*if the sequence of orders of its iterated clique graphs $|K^n(G)|$ tends to infinity with $n$, otherwise it is*$K$-convergent*. $K$-divergence is not known to be computable and there is even a graph on $8$ vertices whose $K$-behaviour is unknown. It has been shown that a regular Whitney triangulation of a closed surface is $K$-divergent if and only if the Euler characteristic of the surface is non-negative. Following this remarkable result, we explore here the existence of $K$-convergent and $K$-divergent (Whitney) triangulations of compact surfaces and find out that they do exist in all cases except (perhaps) where previously existing conjectures apply: It was conjectured that there is no $K$-divergent triangulation of the disk, and that there are no $K$-convergent triangulations of the sphere, the projective plane, the torus and the Klein bottle. Our results seem to suggest that the topology still determines the $K$-behaviour in these cases.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**On the clique behavior of graphs with small constant link**

To appear in Ars Combinatorics.**Abstract**

Given a finite simple graph $G$, we define $K(G)$ as the intersection graph of the (maximal) cliques of $G$, and inductively we define $K^{n}(G)$ as $G$ if $n=0$, and as $K(K^{n-1}(G))$ if $n>0$. We say that a graph $G$ is clique divergent if the sequence of orders $\{|K^{n}(G)|\}$ is unbounded, and clique convergent otherwise. Two graphs $G_{1}$, $G_{2}$ have the same clique behavior if both are clique divergent or both are clique convergent. Given a graph $L$, if there is a finite graph $G$ such that the neighbors of any vertex of $G$ induce a graph isomorphic to $L$, then we say that $L$ is a link graph and that $G$ is a locally~$L$ graph. In this paper we show that if~$L$ has at most six vertices and $G_{1}$, $G_{2}$ are finite locally~$L$ graphs, then $G_{1}$ and $G_{2}$ have the same clique behavior. Moreover with only one possible exception, where the clique behavior is still unknown, we show that for $|L|\leq 6$, any locally~$L$ graph $G$ is clique divergent if and only if $L$ contains some induced $n$-cycle for some $n=4,5$ or $6$. A broad spectrum of techniques for deciding $K$-behavior of graphs is demonstrated in this work.E. Pérez-Cortés, M.A. Pizaña.

**A replacement for the pumping lema.**

Submitted.**Abstract**

The well known Pumping Lemma for Regular Languages is known to be a difficult subject for Computer Science students. We present here a replacement for the Pumping Lemma, which is much simpler and much easier to prove and use and hence, valuable from the educational point of view.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**On self-clique graphs with triangular cliques**

Discrete Matematics**339**(2016) 457-459.

Author version: [ pdf]**Abstract**

A graph is an $\{r,s\}$-graph if the set of degrees of their vertices is $\{r,s\}$. A*clique*of a graph is a maximal complete subgraph. The*clique graph*$K(G)$ of a graph $G$ is the intersection graph of all its cliques. A graph $G$ is*self-clique*if $G$ is isomorphic to $K(G)$. We show the existence of self-clique $\{5,6\}$-graphs whose cliques are all triangles, thus solving a problem posed by Chia and Ong in \cite{CO12}.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**On self-clique shoal graphs**

Discrete Applied Mathematics**205**(2016) 86-100.

Author version: [ pdf ]**Abstract**

The*clique graph*of a graph $G$ is the intersection graph $K(G)$ of its (maximal) cliques, and $G$ is*self-clique*if $K(G)$ is isomorphic to $G$. A graph $G$ is*locally $H$*if the neighborhood of each vertex is isomorphic to $H$. Assuming that each clique of the regular and self-clique graph $G$ is a triangle, it is known that $G$ can only be $r$-regular for $r\in \{4,5,6\}$ and $G$ must be, depending on $r$, a locally $H$ graph for some $H\in \{P_4,P_2\cup P_3,3P_2\}$. The self-clique locally $P_4$ graphs are easy to classify, but only a family of locally $H$ self-clique graphs was known for $H=P_2\cup P_3$, and another one for $H=3P_2$. We study locally $P_2\cup P_3$ graphs (i.e.*shoal graphs*). We show that all previously known shoal graphs were self-clique. We give a bijection from shoal graphs to 2-regular digraphs without directed 3-cycles. Under this translation, self-clique graphs correspond to self-dual digraphs, which simplifies constructions, calculations and proofs. We compute the numbers, for each $n\leq 28$, of self-clique and non-self-clique shoal graphs of order $n$, and also prove that these numbers grow at least exponentially with $n$.F. Larrión, M.A. Pizaña, R. Villarroel-Flores.

**On Strong Graph Bundles**

Discrete Matematics**340**(2017) 3073-3080.

Author version: [ pdf ]**Abstract**

We study*strong graph bundles*: a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs $E$, $B$ and $F$ and a projection $p:E\rightarrow B$ with fiber $F$ (i.e. $p^{-1}(x) \cong F$ for all $x\in V(B)$) such that the preimage of any edge $xy$ of $B$ is trivial (i.e. $p^{-1}(xy)\cong K_2\boxtimes F$). Here we develop a framework to study which subgraphs $S$ of $B$ have trivial preimages (i.e. $p^{-1}(S)\cong S\boxtimes F$) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves*triangular graph bundles*(strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.C. Cedillo, M.A. Pizaña.

**Clique-convergence is undecidable for automatic graphs**

Submitted.**Abstract**

The*clique operator*transforms a graph $G$ into its*clique graph*$K(G)$, which is the intersection graph of all the (maximal) cliques of $G$.*Iterated clique graphs*are then defined by: $K^{n}(G)=K(K^{n-1}(G))$, $K^0(G)=G$. If there are some $n\neq m$ such that $K^n(G)\cong K^m(G)$ then we say that $G$ is*clique-convergent*. The clique graph operator and iterated clique graphs have been studied extensively, but no characterization for clique-convergence has been found so far.*Automatic graphs*are (not necessarily finite) graphs whose vertices and edges can be recognized by finite automata. Automatic graphs (and*automatic structures*) have strong decidability properties inherited from the finite automata defining them. Here we prove that clique-convergence is algorithmically undecidable for the class of automatic graphs. Moreover, the problem remains undecidable, if we reduce the class to contain only quasi clique-Helly and bounded degree graphs. As a consequence, it follows that clique-convergence for automatic graphs is not first-order expressible.C. Cedillo, M.A. Pizaña.

**Clique-divergence is not first-order expressible for the class of finite graphs**

To appear in Ars Combinatoria.**Abstract**

The*clique graph*, $K(G)$, of a graph $G$ is the intersection graph of its (maximal) cliques. The*iterated clique graphs*of $G$ are then defined by: $K^0(G)=G$ and $K^{n}(G)=K(K^{n-1}(G))$. We say that $G$ is*clique-divergent*if the set of orders of its iterated clique graphs, $\{|K^n(G)|: n \in \mathbb{N}\}$ is unbounded. Clique graphs and iterated clique graphs have been studied extensively, but no characterization for clique-divergence has been found so far. Recently, it was proved that the clique-divergence is undecidable for the class of (not necessarily finite) automatic graphs \cite{CP-YY}, which implies that clique-divergence is not first-order expressible for the same class. Here we strengthened the latter result by proving that the clique-divergence property is not first-order expressible even for the class of finite graphs. Logic expressibility has strong relations with complexity theory and consequently, new avenues of research are opened for clique graph theory.M.A. Pizaña, I.A. Robles.

**On bicliques and the second clique graph of suspensions**

To appear in Discrete Applied Mathematics.**Abstract**

The*clique graph $K(G)$*of a graph $G$ is the intersection graph of the set of all (maximal) cliques of $G$. The*second clique graph $K^2(G)$ of $G$*is defined as $K^2(G)=K(K(G))$. The main motivation for this work is to attempt to characterize the graphs $G$ that maximize $|K^2(G)|$, as has been done for $|K(G)|$ by Moon and Moser in \cite{MM65}. The*suspension*$S(G)$ of a graph $G$ is the graph that results from adding two non-adjacent vertices to the graph $G$, that are adjacent to every vertex of $G$. Using a new*biclique*operator $B$ that transforms a graph $G$ into its*biclique graph*$B(G)$, we found the characterization $K^2(S(G)) \cong B(K(G))$. We also found a characterization of the graphs $G$, that maximize $|B(G)|$. Here, a biclique $(X,Y)$ of $G$ is an ordered pair of subsets of vertices of $G$ (not necessarily disjoint), such that every vertex $x \in X$ is adjacent or equal to every vertex $y \in Y$, and such that $(X,Y)$ is maximal under component-wise inclusion. The biclique graph $B(G)$ of the graph $G$, is the graph whose vertices are the bicliques of $G$ and two vertices $(X,Y)$ and $(X',Y')$ are adjacent, if and only if $X \cap X' \neq \varnothing$ or $Y \cap Y' \neq \varnothing$.L. Alcón, M.A. Pizaña, G. Ravenna.

**Two infinite families of critical clique-Helly graphs**

Submitted.**Abstract**

A graph is*clique-Helly*if any family of pairwise intersecting (maximal) cliques has non-empty total intersection. Dourado, Protti and Szwarcfiter conjectured that every clique-Helly graph contains a vertex whose removal maintains it as a clique-Helly graph. We present here two infinite families of counterexamples to this conjecture.Ratko Darda, Martin Milanič, Miguel Pizaña.

**Searching for square-complementary graphs: non-existence results and complexity of recognition**

Submitted.**Abstract**

A graph is*square-complementary*(*squco*, for short) if its square and complement are isomorphic. We prove that there are no squco graphs with girth 6, that every bipartite graph is an induced subgraph of a squco bipartite graph, that the problem of recognizing squco graphs is graph isomorphism complete, and that no nontrivial squco graph is both bipartite and planar. These results resolve three of the open problems posed in Discrete Math.**327**(2014) 62--75.