Geodesic
Self-diclique circulant digraphs
Mathematica Bohemica, Tome 140 (2015) no. 3, pp. 361-367

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let $D=(V,A)$ be a reflexive digraph (or network). Consider $X$ and $Y$ (not necessarily disjoint) nonempty subsets of vertices (or nodes) of $D$. A disimplex $K(X,Y)$ of $D$ is the subdigraph of $D$ with vertex set $X\cup Y$ and arc set $\{(x,y)\colon x\in X,\ y\in Y\}$ (when $X\cap Y\neq \varnothing $, loops are not considered). A disimplex $K(X,Y)$ of $D$ is called a diclique of $D$ if $K(X,Y)$ is not a proper subdigraph of any other disimplex of $D$. The diclique digraph $\overrightarrow {k}(D)$ of a digraph $D$ is the digraph whose vertex set is the set of all dicliques of $D$ and $( K(X,Y),K(X',Y'))$ is an arc of $\overrightarrow {k}(D)$ if and only if $Y\cap X'\neq \varnothing $. We say that a digraph $D$ is self-diclique if $\overrightarrow {k}(D)$ is isomorphic to $D$. In this paper, we provide a characterization of the self-diclique circulant digraphs and an infinite family of non-circulant self-diclique digraphs.
We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let $D=(V,A)$ be a reflexive digraph (or network). Consider $X$ and $Y$ (not necessarily disjoint) nonempty subsets of vertices (or nodes) of $D$. A disimplex $K(X,Y)$ of $D$ is the subdigraph of $D$ with vertex set $X\cup Y$ and arc set $\{(x,y)\colon x\in X,\ y\in Y\}$ (when $X\cap Y\neq \varnothing $, loops are not considered). A disimplex $K(X,Y)$ of $D$ is called a diclique of $D$ if $K(X,Y)$ is not a proper subdigraph of any other disimplex of $D$. The diclique digraph $\overrightarrow {k}(D)$ of a digraph $D$ is the digraph whose vertex set is the set of all dicliques of $D$ and $( K(X,Y),K(X',Y'))$ is an arc of $\overrightarrow {k}(D)$ if and only if $Y\cap X'\neq \varnothing $. We say that a digraph $D$ is self-diclique if $\overrightarrow {k}(D)$ is isomorphic to $D$. In this paper, we provide a characterization of the self-diclique circulant digraphs and an infinite family of non-circulant self-diclique digraphs.
DOI : 10.21136/MB.2015.144401
Classification : 05C20, 68R10
Keywords: circulant digraph; diclique; diclique operator; self-diclique digraph; graph dynamics 
Frick, Marietjie; Llano, Bernardo; Zuazua, Rita. Self-diclique circulant digraphs. Mathematica Bohemica, Tome 140 (2015) no. 3, pp. 361-367. doi: 10.21136/MB.2015.144401
@article{10_21136_MB_2015_144401,
     author = {Frick, Marietjie and Llano, Bernardo and Zuazua, Rita},
     title = {Self-diclique circulant digraphs},
     journal = {Mathematica Bohemica},
     pages = {361--367},
     year = {2015},
     volume = {140},
     number = {3},
     doi = {10.21136/MB.2015.144401},
     mrnumber = {3397263},
     zbl = {06486945},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144401/}
}
TY  - JOUR
AU  - Frick, Marietjie
AU  - Llano, Bernardo
AU  - Zuazua, Rita
TI  - Self-diclique circulant digraphs
JO  - Mathematica Bohemica
PY  - 2015
SP  - 361
EP  - 367
VL  - 140
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144401/
DO  - 10.21136/MB.2015.144401
LA  - en
ID  - 10_21136_MB_2015_144401
ER  - 
%0 Journal Article
%A Frick, Marietjie
%A Llano, Bernardo
%A Zuazua, Rita
%T Self-diclique circulant digraphs
%J Mathematica Bohemica
%D 2015
%P 361-367
%V 140
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144401/
%R 10.21136/MB.2015.144401
%G en
%F 10_21136_MB_2015_144401

[1] Bang-Jensen, J., Gutin, G. Z.: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics Springer, London (2009). | MR | Zbl

[2] Bermond, J.-C., Comellas, F., Hsu, D. F.: Distributed loop computer networks: A survey. J. Parallel Distrib. Comput. 24 (1995), 2-10. | DOI

[3] Figueroa, A. P., Llano, B.: An infinite family of self-diclique digraphs. Appl. Math. Lett. 23 (2010), 630-632. | DOI | MR | Zbl

[4] Greenberg, H. J., Lundgren, J. R., Maybee, J. S.: Extensions of graph inversion to support an artificially intelligent modeling enviroment. Ann. Oper. Res. 21 (1989), 127-142. | DOI

[5] Haralick, R. M.: The diclique representation and decomposition of binary relations. J. Assoc. Comput. Mach. 21 (1974), 356-366. | DOI | MR | Zbl

[6] Palla, G., Farkas, I. J., Pollner, P., Derényi, I., Vicsek, T.: Directed network modules. New J. Phys. 9 (2007), Article No. 186, 14 pages. | DOI

[7] Prisner, E.: A Journey through intersection graph county. http://eprisner.de/Journey/Rahmen.html (1999).

[8] Prisner, E.: Graph Dynamics. Pitman Research Notes in Mathematics Series 338 Longman Group, Harlow (1995). | MR | Zbl

[9] Zelinka, B.: On a problem of E. Prisner concerning the biclique operator. Math. Bohem. 127 (2002), 371-373. | MR | Zbl

Cité par Sources :