Does there exist a function analogous to isisomorphic for isodominant graphs?

346 Views Asked by At

I have two graphs G1 and G2, possibly with colored nodes and edges. Does there exist a function (either MatLab or some other program) that answers the following question:

  • Does there exist an isomorphism of G1, say f(G1), such that f(G1) is greater than or equal to (element-wise dominance)G2?

I am aware of the function isisomorphic introduced in R2016B. This checks answers the question: Given two graphs G1 and G2, possibly with colored nodes and edges, are G1 and G2 isomorphic? One method would be to enumerate all isomorphisms of G1 and check the above condition. For larger graphs this seems like it would take too long.

Edit: An answer to this question might be to modify the isomorphism function in MatLab -- we could replace conditions of the form f(G1) == G2 with f(G1) >= G2. The isomorphism function in the @graph toolbox first re-orders the graphs for efficient computation later, then it calls the isomorphism function in the @biograph toolbox. This consequently calls the graphisomorphism function, which then calls the Mex files graphalgs, which appears to be a version of the nauty Trace package, see here. So, in short, it would seem that to answer this question I would need to modify the nauty package.

0

There are 0 best solutions below