On self-clique shoal graphs
Por:
Larrion, F., Pizana, M. A., Villarroel-Flores, R.
Publicada:
31 may 2016
Resumen:
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?{4,5,6} and G must be, depending on r, a locally H graph for some H?{P4,P2?P3,3P2}. The self-clique locally P4 graphs are easy to classify, but only a family of locally H self-clique graphs was known for H=P2?P3, and another one for H=3P2. We study locally P2?P3 graphs (i.e. shoal graphs). We show that all previously known shoal graphs were self-clique. We give a bijection from (finite) 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=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. © 2016 Elsevier B.V.
Filiaciones:
Larrion, F.:
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City 04510, DF, Mexico
Pizana, M. A.:
Univ Autonoma Metropolitana, Dept Ingn Elect, Ave San Rafael Atlixco 186 Col Vicentina Del Izta, Mexico City 09340, DF, Mexico
Villarroel-Flores, R.:
Univ Autonoma Estado Hidalgo, Ctr Invest Matemat, Carr Pachuca Tulancingo Km 4-5, Pachuca Hgo 42184, Mexico
|