|
|
| Author |
Message |
William McWorter
science forum beginner
Joined: 13 Sep 2005
Posts: 6
|
 Posted: Wed Sep 14, 2005 2:58 pm Post subject:
Existence of 4-cycles
|
|
|
I can prove:
If G is an undirected graph on 14 vertices without loops or multiple edges
containing 29 edges, then G contains a 4-cycle.
Is there a general theorem on existence of 4-cycles? |
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Sep 18, 2005 1:40 am Post subject:
Re: Existence of 4-cycles
|
|
|
William McWorter wrote:
| Quote: | I can prove:
If G is an undirected graph on 14 vertices without loops or multiple edges
containing 29 edges, then G contains a 4-cycle.
Is there a general theorem on existence of 4-cycles?
|
Yes. There exists a function f(n) such that for every n >= 4, if G is
an undirected graph on n vertices with at least f(n) edges, then G
contains a 4-cycle (and there is a graph with n vertices and f(n)-1
edges which does not contain a 4-cycle). You've shown that f(14) <= 29.
Unfortunately, I don't know of any constructive results for this
function, right off the bat. I do remember that if you're looking for
3-cycles, Turan proved that
f(n) = n^2/4 works. I'll have to do some looking around ...
(Half an hour later) Didn't find anything. You may have to search
MathSciNet ( http://ams.rice.edu/mathscinet/search/ ) for articles in
journals; try using "Turan" as one of the search terms.
--- Christopher Heckman |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jan 09, 2009 10:44 pm | All times are GMT
|
|
Mobile Phone | Mobile Phone | Bankruptcy | Mortgage | MPAA
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
