The History of Degenerate (Bipartite) Extremal Graph Problems Page 1 BOLYAI SOCIETY
Erdos Centennial MATHEMATICAL STUDIES, 25 pp. 169–264. The History of Degenerate (Bipartite) …

Let G=(V, E) be an undirected weighted graph with| V|= n and| E|= m. Let k≥ 1 be an
integer. We show that G=(V, E) can be preprocessed in O (kmn 1/k) expected time …

Let $ k\geq 1$ be an odd integer, ${t=\left\lfloor {\tfrac {{k+ 2}}{4}}\right\rfloor} $, and q be a
prime power. We construct a bipartite, q-regular, edge-transitive graph $ CD (k, q) $ of order …

Let k⩾ 3 be a positive odd integer and 1 be a power of a prime. In this paper we give an
explicit construction of a q-regular bipartite graph on v= 2qk vertices with girth g⩾ k+ 5. The …

Spanners, emulators, and approximate distance oracles can be viewed as lossy
compression schemes that represent an unweighted graph metric in small space, say …

The Chromatic Number of Graph Powers Page 1 Combinatorics, Probability and Computing
(2002) 11, 1–10. c 2002 Cambridge University Press DOI: 10.1017/S0963548301004965 …

The paper is devoted to the study of a linguistic dynamical system of dimension n≥ 2 over
an arbitrary commutative ring K, ie, a family F of nonlinear polynomial maps f α: K n→ K n …

We study the graphs D (k, q) of [4] with particular emphasis on their connected components
when q is odd. In [6] the authors proved that these components (most often) provide the best …

Let C2k be the cycle on 2k vertices, and let ex (v, C2k) denote the greatest number of edges
in a simple graph on v vertices which contains no subgraph isomorphic to C2k. In this paper …

We have been investigating the cryptographical properties of in nite families of simple
graphs of large girth with the special colouring of vertices during the last 10 years. Such …