Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
circulant digraph; diclique; diclique operator; self-diclique digraph; graph dynamics
circulant digraph; diclique; diclique operator; self-diclique digraph; graph dynamics
Summary:
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.
References:
[1] Bang-Jensen, J., Gutin, G. Z.: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics Springer, London (2009). MR 2472389 | Zbl 1170.05002
[2] Bermond, J.-C., Comellas, F., Hsu, D. F.: Distributed loop computer networks: A survey. J. Parallel Distrib. Comput. 24 (1995), 2-10. DOI 10.1006/jpdc.1995.1002
[3] Figueroa, A. P., Llano, B.: An infinite family of self-diclique digraphs. Appl. Math. Lett. 23 (2010), 630-632. DOI 10.1016/j.aml.2010.01.026 | MR 2602423 | Zbl 1214.05041
[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 10.1007/BF02022096
[5] Haralick, R. M.: The diclique representation and decomposition of binary relations. J. Assoc. Comput. Mach. 21 (1974), 356-366. DOI 10.1145/321832.321834 | MR 0472598 | Zbl 0293.94020
[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 10.1088/1367-2630/9/6/186
[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 1379114 | Zbl 0848.05001
[9] Zelinka, B.: On a problem of E. Prisner concerning the biclique operator. Math. Bohem. 127 (2002), 371-373. MR 1931321 | Zbl 1003.05048
Search
Partner of
