Ask Your Question

Determining Complete Multipartite Graphs (Specifically Tripartite)

asked 2011-09-14 17:41:08 +0200

acacost1 gravatar image

updated 2011-09-14 19:17:12 +0200

Mike Hansen gravatar image

I have been reading the Sage References, and it does not seem that complete multipartite graphs are defined in Sage yet. I have tried to critique the following two lines of code to see if it would work for complete multipartite graphs.

def is_complete_multipartite(p):
    return p.is_multipartite() and p.num_edges() == mul(map(len, g.multipartite_sets()))

dd = filter(is_complete_multipartite, d)

I get a "graph attribute needed" error. I just wanted to verify that this is the case. Thanks again for the help!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2011-09-14 19:16:41 +0200

Mike Hansen gravatar image

You're getting that error because there is no is_multipartite method on graphs in Sage, nor is there a multipartite_sets method. You can use the coloring method to get what you need since a tripartite graph is 3-colourable. Thus, you could do something like the following: (To simplify things, I'll just consider the m > 1 case.)

def is_complete_multipartite(m):
    assert m > 1
    def is_complete_m_partite(g):
        coloring = g.coloring()
        if coloring is None: #empty graph
            return False
        return len(coloring) == m and g.num_edges() == mul(map(len, coloring))
    return is_complete_m_partite

Then, you'd use it like

dd = filter(is_complete_multipartite(3), d)

to test for complete tripartiteness.

edit flag offensive delete link more


Thanks! I'll give it try.

acacost1 gravatar imageacacost1 ( 2011-09-15 16:28:43 +0200 )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

1 follower


Asked: 2011-09-14 17:41:08 +0200

Seen: 982 times

Last updated: Sep 14 '11