Ask Your Question
1

Adding edges to a graph

asked 2020-06-29 20:55:59 +0100

bottled-caps gravatar image

updated 2020-07-01 17:49:37 +0100

tmonteil gravatar image

This is my first time using this forum so please let me know if more information is needed

I am trying to some basic conjecture testing, so I'm not too concerned about runtime. I am trying to count graphs which are "maximal triangle-free and 3-colorable", ie triangle-free and 3-colorable, and adding any missing edge breaks one of those 2 properties. But I don't know how to test that property about adding edges to a graph, since I don't know how to add edges to a graph. I'm mainly using the Sage page on undirected graphs. My rudimentary code so far is below:

> n = 5 
> list = [] 
> for i in range(1, n):
>     list.append([])
>     for g in graphs(i):
>         if g.is_triangle_free() and g.chromatic_number() <= 3:
>             list[i-1].append(g)

list

edit retag flag offensive close merge delete

Comments

Like this

  sage: G = Graph()
  sage: G.add_edge((1,2))
  sage: G
  Graph on 2 vertices
FrédéricC gravatar imageFrédéricC ( 2020-07-01 12:55:23 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2020-07-01 17:49:15 +0100

tmonteil gravatar image

updated 2020-07-02 16:06:57 +0100

Your loop for g in graphs(i): iterates over all graphs of size i, which is a big waste of time. The graphs() generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter during the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.

Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.

Hence graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3) will generate all graphs of size n with that property, see graphs? for more details.

So, here is a possible way to construct the maximal graphs you are looking for:

def maximal_graphs(n):
    mg = []
    for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
        maximal=True
        for e in G.complement().edges():
            H = copy(G)
            H.add_edge(e)
            if H.is_triangle_free() and H.chromatic_number() <= 3:
                maximal=False
                break
        if maximal:
            mg.append(G)
    return mg

You can use that function to count the graphs you ar looking for:

sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]

You can then search in the OEIS, in case something is known about such sequence:

sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.

sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)

Unfortunately, the next term differs:

sage: len(maximal_graphs(11))
60

So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.

You can see the following answers to get more details about generation of graphs satisfying an hereditary property:

edit flag offensive delete link more

Comments

wow this exactly anticipates what I was going to do next, thanks so much for the thorough answer!

bottled-caps gravatar imagebottled-caps ( 2020-07-01 20:11:40 +0100 )edit

.^_^ .

tmonteil gravatar imagetmonteil ( 2020-07-01 23:04:48 +0100 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2020-06-29 20:55:59 +0100

Seen: 1,261 times

Last updated: Jul 02 '20