On optimization problems for graphs and~security of digital communications

V. A. Ustimenko

Trudy Instituta matematiki, Tome 18 (2010) no. 1, pp. 116-122.

Résumé

The most developed field of the classical Extremal Graph Theory studies the maximal size of simple graphs without certain cycles. We discuss resent results on the evaluation of the maximal size of digraphs without certain commutative diagrams that satisfy certain restrictions on the number of inputs and outputs (balanced digraphs or regular directed graphs). These studies are connected with problems of constructing LDPS Codes in Coding Theory and graph based stream ciphers and graph based public keys in Cryptography. Finally we show that the combinatorial optimization problems above can be formulated in the language of integer linear programming.

Bibliographie

[1] C.T. Benson, “Minimal regular graphs of girth eight and twelve”, Canadien Journal of Mathematics, 18 (1966), 1091–1094 | DOI | MR | Zbl

[2] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978 | MR | Zbl

[3] J.A. Bondy, M. Simonovits, “Cycles of even length in graphs”, J. Combin. Theory, Ser. B, 16 (1974), 87–105 | DOI | MR

[4] W.G. Brown, “On graphs that do not contain Thomsen graph”, Canad. Math. Bull., 9:3 (1966), 281–285 | DOI | MR | Zbl

[5] P. Erdös', A. R'enyi, V.T. S'oc, “On a problem of graph theory”, Studia. Sci. Math. Hungar., 1 (1966), 215–235 | MR | Zbl

[6] P. Erdös', M. Simonovits, “Compactness results in extremal graph theory”, Combinatorica, 2:3 (1982), 275–288 | DOI | MR | Zbl

[7] W. Faudree, M. Simonovits, “On a class of degenerate extremal graph problems”, Combinatorica, 3:1 (1983), 83–93 | DOI | MR | Zbl

[8] F. Lazebnik, V.A. Ustimenko, A.J. Woldar, “A New Series of Dense Graphs of High Girth”, Bull (New Series) of AMS, 32:1 (1995), 73–79 | DOI | MR

[9] F. Lazebnik, V.A. Ustimenko, A.J. Woldar, “Polarities and $2k$-cycle-free graphs”, Discrete Mathematics, 197/198 (1999), 503–513 | MR | Zbl

[10] F. Lazebnik, V.A. Ustimenko, A.J. Woldar, “Properties of certain families of $2k$-cycle free graphs”, J. Combin. Theory, ser B, 60:2 (1994), 293–298 | DOI | MR | Zbl

[11] R. Ore, Graph Theory, Wiley, London, 1971

[12] T. Shaska, V. Ustimenko, “On some applications of graph theory to cryptography and turbocoding”, Proceedings of the NATO Advanced Studies Institute “New challenges in digital communications” (May 2008, University of Vlora), Albanian Journal of Mathematics, 2, no. 3, 2008, 249–255 | MR | Zbl

[13] V.A. Ustimenko, “Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography”, Journal of Mathematical Sciences, 140:3 (2007), 412–434 | DOI | MR

[14] V.A. Ustimenko, “On the extremal graph theory for directed graphs and its cryptographical applications”, Advances in Coding Theory and Cryptography, Series on Coding Theory and Cryptology, 3, eds. T. Shaska, W. C. Huffman, D. Joener and V. Ustimenko, World Scientific, 2007 | MR

[15] V.A. Ustimenko, “On the cryptographical properties of extremal algebraic graphs”, Algebraic Aspects of Digital Communications, NATO Science for Peace and Security Series - D: Information and Communication Security (Vlora, 2008), Lectures of Advanced NATO Institute “New Challenges in Digital Communications”, 24, 2009 | MR | Zbl

[16] V. Ustimenko, J. Kotorowicz, On the Properties of Stream Ciphers Based on Extremal Directed Graphs, Cryptography Research Perspective, ed. Roland E. Chen, Nova Science Publishers, USA, 2009 | MR

[17] V.A. Usimenko, “On the extremal regular directed graphs without commutative diagrams and their applications”, Coding Theory and Cryptography, Proc. of the Int. Conference, Albanian J. of Mathematics, 11, no. 4, 2007

[18] V.A. Ustimenko, “On the Even Circuit Theorem for balanced or directed graphs and its applications”, Doklady Acad of Sci (to appear) (in Russian)

[19] V.A. Ustimenko, “On some results of Extremal Digraph Theory and their applications to Information Security”, Proceedings of the 9th Central European Conference on Cryptology, Trebic, 2009 (to appear)