Ask Your Question
1

Help with graphs

asked 2018-08-06 09:45:32 +0100

glavuncho gravatar image

updated 2018-09-17 21:08:08 +0100

tmonteil gravatar image

I am trying to find the set of (surjective) homomorphic images of the Groetzsch Graph - G. I have two ideas, but I am stuck at both. Help with either would be very much appreciated.

1.I try narrowing down the candidate homomorphic images to graphs with chromatic number at least 4 and number of vertices at most 10 in house of graphs. Then i get a graph6 file and try to check if each of those graphs is a homomorphic image of G. This doesn't work because I don't know how exactly to import the graph6 file into sage.

  1. Find the independent sets of G and find all the ways I can combine them into homomorphic images. I' ve heard that this is possible, but seems like a rather daunting task for me because I am very new with sage.
edit retag flag offensive close merge delete
add a comment

1 Answer

Sort by ยป oldest newest most voted
0

answered 2018-08-06 15:42:21 +0100

tmonteil gravatar image

updated 2018-08-06 15:47:42 +0100

Let me answer your first point:

If s is a graph6-string representation of some graph, you can transform it into a Sage graph as follows:

sage: s = 'Jsa@IchDIS_'       # this is the graph6 representation of the GroetzschgGraph
sage: G = Graph(s)
sage: G
Graph on 11 vertices

You can check:

sage: H = graphs.GrotzschGraph()
sage: G == H
True

To go further, you shoud provide an explicit sample of a graph6 file, so that we can understand how to load it.

Regarding your secnod point, since your graph is small, you can get the list of independent sets as follows:

  • put a boolean (0 or 1) variable on each vertex
  • add the constraint that for each edge, the sum of the values iof the vertices defining the edge is at most 1

You get a polytope whose integer points are the independent sets of your graph. In Sage, you can do this:

sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(binary=True)
sage: for a,b in G.edges(labels=False):
....:     p.add_constraint(x[a]+x[b]<=1)
sage: P = p.polyhedron()
sage: L = P.integral_points() ; L
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
 (0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0),
 (0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
 (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
 (0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0),
 (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0),
 (0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0),
 (0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0),
 (0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0),
 (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1),
 (0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0),
 (0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1),
 (0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0),
 (0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1),
 (0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0),
 (0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0),
 (0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0),
 (0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0),
 (0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0),
 (0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0),
 (0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0),
 (0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0),
 (0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0),
 (0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0),
 (0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0),
 (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1),
 (0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0),
 (0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0),
 (0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1),
 (0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0),
 (0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0),
 (0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0),
 (0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0),
 (0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0),
 (0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0),
 (0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1),
 (0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0),
 (0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1),
 (0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0),
 (0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0),
 (0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0),
 (0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0),
 (0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0),
 (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0),
 (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0),
 (0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1),
 (0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0),
 (0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0),
 (0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1),
 (0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0),
 (0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0),
 (0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0),
 (0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0),
 (0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1),
 (0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0),
 (0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1),
 (0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0),
 (0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0),
 (0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0),
 (0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0),
 (0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0),
 (0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0),
 (0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0),
 (0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0),
 (0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0),
 (0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0),
 (0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1),
 (0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0),
 (0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0),
 (0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1),
 (0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0),
 (0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
 (0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0),
 (0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
 (0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0),
 (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
 (1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
 (1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
 (1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
 (1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0),
 (1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
 (1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
 (1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
 (1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
 (1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0))
sage: len(L)
103

So, you have a list of 103 independent sets.

edit flag offensive delete link more

Comments

I understand this and I have reached that point.

However in the first question, I can't write every single graph, I need something that aoutomatically reads all ~100 graphs that are in the graph6 file. Moreover some of the graphs sage doesn't read at all - it gives errors because of certain symbols in the string of the graph.

For the second question finding the independent sets is ok, but then I need an algorithm which contracts the independent sets into new smaller graphs, so that I find hom G.

glavuncho gravatar imageglavuncho ( 2018-08-06 16:31:53 +0100 )edit
add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

subscribe to rss feed

Stats

Asked: 2018-08-06 09:45:32 +0100

Seen: 802 times

Last updated: Aug 06 '18

Related questions

How can I compute the minimal fixing set?

Determining Complete Bipartite Graphs

Determining Complete Multipartite Graphs (Specifically Tripartite)

Iterating over all non isomorphic connected graphs of given order

Graphs from inside a function

Model of polynomial with integer coefficients

Non-orientable genus of a graph

Typeset latex in SMC

I keep losing my node labels on graph export

Compute perfect matchings in a graph

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59