M. A. Pizaña's

Abstracts of Publications



Last modified: Apr/30/2016.     Back to main page


  1. 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.

  2. 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$.

  3. 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.

  4. 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.

  5. 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.

  6. 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$?

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. 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$.

  14. 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.

  15. 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. [...]

  16. 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.

  17. 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}$.

  18. 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.

  19. 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.

  20. 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)$.

  21. 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).$

  22. 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.

  23. 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.

  24. 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.

  25. 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.

  26. F. Larrión, M.A. Pizaña, R. Villarroel-Flores.
    On the clique behavior of graphs with small constant link
    Submitted
    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.

  27. 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.

  28. 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}.

  29. 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$.

  30. F. Larrión, M.A. Pizaña, R. Villarroel-Flores.
    On Strong and Triangular Graph Bundles
    Submitted
    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.




Valid HTML 4.01! Made with emacs Linux Powered Powered by Apache

Micro$oft Free Site