✦ LIBER ✦

Constructions of bipartite graphs from finite geometries

✍ Scribed by Keith E. Mellinger; Dhruv Mubayi

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 99 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20059

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n × n bipartite graphs provide constructions of C~6~‐free graphs with Ω(n^4/3^ edges, C~10~‐free graphs with Ω(n^6/5^) edges, and Θ(7,7,7)‐free graphs with Ω(n^8/7^) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005

📜 SIMILAR VOLUMES

A generalized construction of chromatic

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Michael Plantholt 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 378 KB

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap

Constructions of small regular bipartite

Constructions of small regular bipartite graphs of girth 6

✍ G. Araujo-Pardo; Camino Balbuena 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB 👁 1 views

Constructing a bipartite graph of maximu

Constructing a bipartite graph of maximum connectivity with prescribed degrees

✍ Asano, Takao 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB 👁 3 views

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and

New Constructions of Bipartite Graphs on

New Constructions of Bipartite Graphs on m, n Vertices with Many Edges and Without Small Cycles

✍ F. Lazebnik; V.A. Ustimenko; A.J. Woldar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 293 KB

A Geometric Construction of Partial Geom

A Geometric Construction of Partial Geometries with a Hermitian Point Graph

✍ Elisabeth Kuijken 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 73 KB

In 1998 Mathon constructed algebraically a class of partial geometries pg(q -1, (q 2 -1)/2, (q -1)/2), where q is an even power of 3. The point graph of these partial geometries is the Hermitian graph constructed by Taylor. In this paper a geometric construction of Mathon's partial geometries is giv

On Parameters of Some Graphs from Finite

On Parameters of Some Graphs from Finite Fields

✍ I.E. Shparlinski 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 79 KB

We generalize the construction of F. R. Chung of graphs from finite fields and estimate their parameters with the help of a new bound of exponential sums due to G. I. Perel'muter and the author.