Atlas home || Conferences | Abstracts | about Atlas

International Conference on Interdisciplinary Mathematical and Statistical Techniques - IMST 2008 / FIM XVI
May 16-18, 2008
University of Memphis
Memphis, TN, USA

Organizers
Sat Gupta, M.L. Aggarawal, James Jamison

View Abstracts
Conference Homepage

Largest number of edges in a given graph without a path of length 3
by
Gyula O.H. Katona
Renyi Institute, Budapest
Coauthors: Dezso Miklos

Let [n] be an n-element set, ([n] || k) the family of its k element subsets. G is the bipartite graph with the vertex set ([n] || (n/2))∪([n] || (n/2+1)) and two vertices are adjacent iff one (properly) includes the other one. We give a construction containing ( 1- o(1))(number of vertices) edges of this graph without a path of three edges. The problem is closely related to perfect codes and dominating sets in graphs.

Date received: March 20, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caxa-18.