Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdos raised the problem of determining $f(n)$ (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). Given a graph $H$, what is the maximum number of edges of a graph with $n$ vertices not containing $H$ as a subgraph? This number is denoted $ex(n,H)$, and is known as the Turan number. Erdos conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\geq cn^{1+1/k}$(see P. Erdos, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , pp. 97--109, Academic Press, London, 1971). Haj\'{o}s conjectured that every simple even graph on $n$ vertices can be decomposed into at most $n/2$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236 ). We present the problems, conjectures related to these problems and we summarize the know results.

We introduce a homotopy theory of digraphs (directed graphs) and prove its basic properties, including the relations to the homology theory of digraphs constructed by the authors in previous papers. In particular, we prove the homotopy invariance of homologies of digraphs and the relation between the fundamental group of the digraph and its first homology group. The category of (undirected) graphs can be identified by a natural way with a full subcategory of digraphs. Thus we obtain also consistent homology and homotopy theories for graphs.

No abstract uploaded!

No abstract uploaded!

Let G=(V,E) be a locally finite graph. Firstly, using calculus of variations, including a direct method of variation and the mountain-pass theory, we get sequences of solutions to several local equations on G (the Schrödinger equation, the mean field equation, and the Yamabe equation). Secondly, we derive uniform estimates for those local solution sequences. Finally, we obtain global solutions by extracting convergent sequence of solutions. Our method can be described as a variational method from local to global.