M. A. Pizaña's

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 defensive alliances and strong global offensive alliances
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
Ars Combinatoria 142 (2019) 27-53.
Author version: [ ps | pdf ]
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.

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-divergence is not first-order expressible for the class of finite graphs
Ars Combinatoria 152 (2020) 3-11.
Author version: [ pdf ]
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
Discrete Applied Mathematics 281 (2020) 261-267.
Author version: [ pdf ]
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
Discrete Applied Mathematics 281 (2020) 2-5.
Author version: [pdf]
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: complexity of recognition and further nonexistence results
Discrete Mathematics 344 (2021) 112369.
Author version: [ pdf ]
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.

C. Cedillo, M.A. Pizaña.
Simulating digital circuits with clique graphs
Matemática Contemporânea 46 (2019) 185-193.
Author version: [ pdf ]
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$. Clearly, we can iterate the operator to obtain iterated clique graphs: $K^{n+1}(G)=K(K^{n}(G))$. The clique graph operator and the iterated clique graphs have been studied extensively. The discrete dynamics generated by the clique operator when applied iteratively to graphs, has shown to be very rich and complex. This complexity has fascinated experts in the field of graph dynamics as well as it has defeated every endeavor to characterize the clique behavior of graphs. Indeed, it has been suspected since 2001 (by J. Meidanis in The clique operator) that the clique operator is actually Turing-complete. Motivated by this problem we have started simulating digital circuits using clique graphs, with the aim to explore the computational power of the clique operator. Here we report our advances.

Marisa Gutierrez, Bernardo Llano, Miguel Pizaña, Silvia Tondato.
Diclique digraphs
Discrete Applied Mathematics 344 (2024) 197-210.
Author version: [ pdf ]
Abstract
Given a digraph $D$, a diclique is a maximal pair of vertex sets $(X,Y)$ satisfying $x\in X, y\in Y \implies x\rightarrow y$. The diclique digraph of $D$, $\overrightarrow{K}(D)$, has the dicliques of $D$ as vertices two of them being adjacent, $(X,Y)\rightarrow (X',Y')$, if and only if $Y\cap X' \neq \varnothing$. Iterated diclique digraphs are defined by $\overrightarrow{K}^0(D)=D$ and $\overrightarrow{K}^n(D)= \overrightarrow{K}(\overrightarrow{K}^{n-1}(D))$. Here we study the diclique operator $\overrightarrow{K}$ from the perspective of graph dynamics [Prisner, Graph Dynamics, 1995] and hence we are interested in $\overrightarrow{K}$-divergence ($|\overrightarrow{K}^n(D)|\rightarrow \infty$), $\overrightarrow{K}$-convergence ($\overrightarrow{K}^n(D)\cong \overrightarrow{K}^m(D)$ for some $n\lt m$), $\overrightarrow{K}$-invariance ($\overrightarrow{K}(D)\cong D$) and similar properties. In particular, we provide here the first examples of simple digraphs which are $\overrightarrow{K}$-divergent.

Ariadna Juárez-Valencia, Miguel Pizaña.
On 4-regular square-complementary graphs of large girth
Matemática Contemporânea 48 (2022) 84-93.
Author version: [ pdf ]
Abstract
A square-complementary graph is a graph such that its square and its complement are isomorphic. Here, we provide a computer-assisted proof showing that there are no 4-regular squco graphs of girth greater than 4, thus solving in the negative an open problem in Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 5 (1994) 43-48. and also in Discrete Mathematics 327 (2014) 62-75.

F. Larrión, M.A. Pizaña, R. Villarroel-Flores.
Graph homotopy and clique graphs
Submitted.
Author version: [ pdf ]
Abstract
We study graph homotopy, which was introduced by Dochtermann in 2009. Among other characterizations we show that the homotopy congruence is the finest one that makes invertible the graph morphisms in certain families, and also the finest one that identifies some endomorphisms with identity maps. On the homotopy category the clique graph operator becomes a functor. This sheds more light into the dynamical behavior of clique graphs and a new unexplored panorama emerges. We introduce a new technique, based on unbounded morphisms, which enables us to prove results on clique divergence that could not be afforded by previously existing methods.

Miguel Pizaña, Ismael Robles.
Finding graphs with exponential clique-growth using genetic algorithms
Matemãtica Contemporânea 55 (2023) 114-123.
Author version: [ pdf ]
Abstract
The clique graph $K(G)$ is the intersection graph of the set of all the (maximal) cliques of $G$. The iterated clique graphs of $G$ are defined inductively by $K^0(G)=G$ and $K^{n+1}(G)=K(K^n(G))$. An open problem is to determine whether there is a graph $G$, with exponential clique-growth rate, i.e. such that $|K^n(G)|=\Theta(t^n)$, for some $t>1$. In this work we report the use of genetic algorithms to find a candidate for such a graph. The circulant $G=C_m(1,3,6,7,8)$ shows an experimental clique-growth rate of $|K^n(G)|=\Theta \left( \sqrt{3}^{n}\right)$. Further preliminary theoretical results (beyond the scope of this paper) also suggest that this graph has indeed the desired property, but the open problem still remains to be settled.

G. Araujo-Pardo, C. De la Cruz, M. Matamala, M.A. Pizaña.
Weighted Cages
Submitted.
Author version: [ pdf ]
Abstract
Cages ($r$-regular graphs of girth $g$ and minimum order) and their variants have been studied for over seventy years. Here we propose a new variant, weighted cages. We characterize their existence; for cases $g=3,4$ we determine their order; we give Moore-like bounds and present some computational results.