FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Embedding Graphs in Boolean Graphs
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Rob
science forum beginner


Joined: 20 Jun 2005
Posts: 44

PostPosted: Fri Feb 03, 2006 1:52 am    Post subject: Embedding Graphs in Boolean Graphs Reply with quote

Prove the following:

Every finite graph can be viewed as an induced subgraph of some graph
on the powerset of a set X, where two vertices A and B are connected if
and only A intersect B = empty.

Apparantly, this is easy to prove, but I cant see it. Any help would
be appreciated.

TY

Rob
Back to top
Robert Sheskey
science forum beginner


Joined: 21 Oct 2005
Posts: 39

PostPosted: Sat Feb 04, 2006 2:41 am    Post subject: Re: Embedding Graphs in Boolean Graphs Reply with quote

In article <1138931570.602248.167520@g47g2000cwa.googlegroups.com>, robertborgersen@gmail.com says...
Quote:


Prove the following:

Every finite graph can be viewed as an induced subgraph of some graph
on the powerset of a set X, where two vertices A and B are connected if
and only A intersect B = empty.

Apparantly, this is easy to prove, but I cant see it. Any help would
be appreciated.

TY

Rob



Let G be your graph, G' its complement. Let X be the set of edges of G'
and associate with vertex A the set of edges of G' incident with A.



Robert Sheskey
Back to top
Peter Allen
science forum beginner


Joined: 17 Nov 2005
Posts: 29

PostPosted: Sun Feb 05, 2006 5:55 pm    Post subject: Re: Embedding Graphs in Boolean Graphs Reply with quote

Rob wrote:
Quote:
Prove the following:

Every finite graph can be viewed as an induced subgraph of some graph
on the powerset of a set X, where two vertices A and B are connected
if and only A intersect B = empty.

Assuming you don't have any restrictions on X...

Let X = (V(G))^{(2)} - E(G) (i.e. the places where an edge isn't, in G).

If V(G)={v_1,...} then let V_1 be the subset of X whose members contain v_1,
et cetera.

Then in the Boolean graph, V_i, V_j are connected iff V_i intersect V_j is
empty iff v_i, v_j are connected.

Peter
Back to top
Rob
science forum beginner


Joined: 20 Jun 2005
Posts: 44

PostPosted: Fri Feb 10, 2006 4:06 am    Post subject: Re: Embedding Graphs in Boolean Graphs Reply with quote

Thanks much!

Rob
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Thu Aug 24, 2017 2:56 am | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Help with Boolean Algebra Questions!!! mcbivens@umes.edu Math 0 Thu Sep 14, 2006 6:58 pm
No new posts Help with Boolean Algebra Questions!!! mcbivens@umes.edu Math 0 Thu Sep 14, 2006 6:58 pm
No new posts embedding problem winshum Undergraduate 0 Sat Jul 15, 2006 5:24 pm
No new posts Call for Papers: Graphs, Mappings and Combinatorics at th... EdV Undergraduate 0 Thu Jul 06, 2006 2:07 am
No new posts Call for Papers: Graphs, Mappings and Combinatorics at th... EdV Research 0 Wed Jul 05, 2006 1:46 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0179s ][ Queries: 20 (0.0035s) ][ GZIP on - Debug on ]