My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 29th, 2011, 06:01 PM   #1
Senior Member
 
Joined: Apr 2011
From: Recife, BR

Posts: 352
Thanks: 0

Graph theory and number theory

(Self-proposed) Given a graph with n vertices, assign a positive integer greater than one to each vertex, such that the integers are consecutive. Draw an edge connecting two vertices iff the numbers assigned to them and relatively prime. Is it possible for such a graph be planar for all ?

For n = 6 just choose the numbers 11, 12, 13, 14, 15, 16. I couldn't find a possibility for n = 7 (haven't tried much though).

Any ideas?
proglote is offline  
 
October 30th, 2011, 01:09 AM   #2
Senior Member
 
Joined: Sep 2008

Posts: 150
Thanks: 5

Re: Graph theory and number theory

It is certainly not possible for any n. A very bad bound would be:

It is not possible, if n is bigger than .

If n is that big, one can easily find a complete graph with 5 vertices, which is contained (and known to be not planar).

Here is how it works: Take k to be the smallest number in your numbering of the vertices, that is divisible by 2,3, and 5. Then the numbers k+1, k+2, k+3, k+5 and k+7 occure as numbers of vertices. However, the difference of two of them is at most 6, so only the primes 2,3, and 5 could divide two of them, but that is absurd, as 2 divids only k+2, 3 divides only k+3 and 5 divides only k+5. It follows, that these numbers are pairwise coprime, showing the assertion.

I'm sure one can improve this bound easily, and exspect the bound to be in the area of 10. May be the 3-3 graph is even easier to find.

rgds
Peter
Peter is offline  
October 30th, 2011, 08:49 AM   #3
Senior Member
 
Joined: Apr 2011
From: Recife, BR

Posts: 352
Thanks: 0

Re: Graph theory and number theory

Thanks for the bound, Peter. I see by Turán we can have at most edges. Is there a similar theorem for complete bipartite subgraphs such as ? Because for n = 8 we need less than 24 edges, and if we choose (48 -> 55) we have 19 edges but I still think it's not planar!
proglote is offline  
October 30th, 2011, 04:20 PM   #4
Senior Member
 
Joined: Apr 2011
From: Recife, BR

Posts: 352
Thanks: 0

Re: Graph theory and number theory

I will show that

Let be the set of n consecutive numbers. If , then there is a number such that and , which follows because given seven consecutive numbers, one of them, k, must be congruent to 2, 8 or 11 mod 15, thus given 13 consecutive numbers

Consider the vertices to which k, k+1, k+2, k+3, k+5 and k+6 are assigned. Separate them in two groups : k, k+2, k+6 and k+1, k+3, k+5. There is an edge connecting (k, k+1), (k+1,k+2), (k+2,k+3) and (k+5,k+6) because they are consecutive. If k is not divisible by 3, there is an edge (k, k+3) and (k+3,k+6). If k is not divisible by 5, there is an edge (k,k+5). If k is not congruent to 1 modulo 3, there is an edge (k+2, k+5). If k is not congruent to 4 modulo 5, there is an edge connecting (k+1,k+6). Then these two groups form a complete bipartite graph, hence the graph is not planar.

Putting the restrictions above together, we need k to be congruent to 2 modulo 3 and k to be congruent to 1, 2 or 3 modulo 5, thus if there is a k congruent to 2, 8 or 11 mod 15, then the graph is not planar, which is the case for as proven above.

I am still not sure about n = 8, 9, 10, 11, 12 though.
proglote is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
graph, number, theory



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Edge chromatic number question (Graph theory) Ecllipsers Applied Math 0 February 9th, 2014 03:46 PM
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 06:03 AM
Graph Theory sulonski Applied Math 1 August 2nd, 2012 10:03 AM
graph theory - social networks and reverting the graph johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM
Graph Theory davy89 Applied Math 1 November 30th, 2008 01:05 PM





Copyright © 2017 My Math Forum. All rights reserved.