Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
Author Message
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
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
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

 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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Mon Mar 18, 2019 5:38 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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