Author 
Message 
Rob science forum beginner
Joined: 20 Jun 2005
Posts: 44

Posted: Fri Feb 03, 2006 1:52 am Post subject:
Embedding Graphs in Boolean Graphs



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

Posted: Sat Feb 04, 2006 2:41 am Post subject:
Re: Embedding Graphs in Boolean Graphs



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

Posted: Sun Feb 05, 2006 5:55 pm Post subject:
Re: Embedding Graphs in Boolean Graphs



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

Posted: Fri Feb 10, 2006 4:06 am Post subject:
Re: Embedding Graphs in Boolean Graphs



Thanks much!
Rob 

Back to top 


Google


Back to top 



The time now is Mon Feb 19, 2018 10:04 pm  All times are GMT

