Name
Abstract | ||
|---|---|---|
Let q be a prime power and k¿2 be an integer. Lazebnik et al. (Rutcor Research Report RRR 99-93, 1993; Bull. AMS 32 (1) (1995) 73) determined that the number of components of certain graphs D(k,q) introduced by Lazebnik and Ustimenko (Discrete Appl. Math. 60 (1995) 275) is at least qt-1 where t=¿(k+2)/4¿. This implied that these components (most often) provide the best-known asymptotic lower bound for the greatest number of edges in graphs of their order and girth. Lazebnik et al. (Discrete Math. 157 (1996) 271) showed that the number of components is (exactly) qt-1 for q odd, but the method used there failed for q even. In this paper we prove that the number of components of D(k,q) for even q4 is again qt-1 where t=¿(k+2)/4¿. Our proof is independent of the parity of q as long as q4. Furthermore, we show that for q=4 and k¿4, the number of components is qt. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.disc.2003.08.003 | Discrete Mathematics |
Keywords | Field | DocType |
algebraic constructions,dense graphs,connectivity,high girth,finite field,vector space,lower bound | Graph theory,Integer,Discrete mathematics,Graph,Combinatorics,Upper and lower bounds,Parity (mathematics),Connectivity,Prime power,Mathematics,Dense graph | Journal |
Volume | Issue | ISSN |
277 | 1 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.61 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Felix Lazebnik | 1 | 353 | 49.26 |
| Raymond Viglione | 2 | 28 | 2.61 |