In graph theory, the lexicographic product  or graph composition G ∙ H of graphs G and H is a graph such that

 - the vertex set of G ∙ H is the cartesian product V(G) × V(H); 
 - and any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Given two graphs, it is easy to obtain their lexicographic product. However the inverse process does not look so easy. 

I read the book "Handbook of product graphs" and wiki, that say that the recognition complexity of lexicographic products is polynomially equivalent to the graph isomorphism problem. 

For the lexicographic product, I know that there is some algorithm without codes to implement the decomposition of the lexicographic products of a graph.

• Feigenbaum, J.; Schäffer, A. A. (1986), "Recognizing composite graphs is equivalent to testing graph isomorphism", SIAM Journal on Computing, 15 (2): 619–627, doi:10.1137/0215045 (https://www.cs.yale.edu/homes/jf/FS-SICOMP86.pdf)

However, I did not understand the algorithm process mentioned in the article, nor did I see the program implementation of this algorithm. About 5 months ago, I asked similar questions on multiple platforms, but did not receive any feedback.

The potential algorithm can help us discover some theorems, so I am very interested in the implementation of the algorithm in the above article.

PS:We also know that there are already polynomial algorithms for the decomposition of the cartesian product of a graph. A polynomial time algorithm for finding the prime factors of Cartesian-product graphs", Discrete Applied Mathematics, 12 (2): 123–138, doi:10.1016/0166-218X(85)90066-6, MR 0808453 and we can find the java codes for implementation of finding the prime factors of Cartesian-product graphs.

This question stems from a previous question that has been perfectly resolved by acer and Carl Love, but as Carl Love mentioned the foldl function, today I attempted to experience its functionality (In order to understand the foldl or foldr function). But I encountered a small issue. 

s:="[ (0, 1), (1, 2), (1, 10), (2, 3), (3, 4), (4, 5),
(4, 9), (5, 6), (6, 7), (7, 8),(8, 9), (10, 11), (11, 12),
(11, 16), (12, 13), (13, 14), (14, 15), (15, 16)]";
with(StringTools):
L1:= "()[]": L2:= "{}{}":
X:=foldl(SubstituteAll,s,op([L1[1],L2[1]]),op([L1[2],L2[2]]),op([L1[3],L2[3]]),op([L1[4],L2[4]]));

Error, (in StringTools:-SubstituteAll) expecting 3 arguments, but got 2

I find it strange that foldl doesn't recognize SubstituteAll with three arguments. 

Isn't s and op([L1[i], L2[i]]) providing three arguments? Of course, s is constantly changing.

The goal is to replace the above string with:

{ {0, 1}, {1, 2}, {1, 10}, {2, 3}, {3, 4}, {4, 5},

    {4, 9}, {5, 6}, {6, 7}, {7, 8},{8, 9}, {10, 11}, {11, 12},

    {11, 16}, {12, 13}, {13, 14}, {14, 15}, {15, 16}}

I previously asked the following question, and a primes member dharr  provided a perfect answer. The question I asked today is slightly different.

• https://www.mapleprimes.com/questions/235430-Find-All-Minimal-Edge-Cuts-Of-A-Graph
• https://www.mapleprimes.com/posts/219618-Minimal-Edge-Cuts-Of-A-Graph-Using-Fundamental

An edge cut of a graph G induced by a partition of G's vertices into sets X and Y is the set of all edges with one endpoint in X and another endpoint in Y.

An edge separator is a set of edges whose removal will increase the number of connected components in the graph.

Note that these are two distinct concepts and cannot be considered equivalent.

An edge separator is not necessarily an edge cut. For example, for the complete bipartite graph K3,3, a set of any seven edges of K3,3 is an edge separator, but a set of any seven edges of K3,3 is not an edge cut.

It is easy to determine whether a set of edges is an edge separator.

with(GraphTheory):
with(combinat):
G:=CompleteGraph(3,3);
edge:=choose(Edges(G), 7):
seq(nops(ConnectedComponents(DeleteEdge(G,s,inplace= false))),s in edge) 

4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

For another exmaple,

In  the left  figure,  the brown edges highlighted represent an edge-separating set, but it is not an edge cut. The set of brown edges on the right is an edge cut.

But how to determine if a set of edges is an edge cut of a graph? I don't have a good idea yet, but I have a rough idea which is to color the set of vertex-ends of edges under consideration and then see if a partition as defined by the edge cut can be found.

IndependencePolynomial returns the independence polynomial for the graph G in the variable x.

For the following example, its calculation took over 20 minutes and still hasn't produced a result, and what's fatal is that it  has consumed 4G  memory.

with(GraphTheory):
G:=ConvertGraph("W|tNHEpCKoh`@@Po_WHB@CKC?WGO{G?KKCB`?OMG?_y_?Sn");
G1:=LineGraph(G);
IndependencePolynomial(G1, x) # be careful

I use  codes in  the link https://github.com/pernici/hobj.

It produced results quickly (It takes approximately 5 seconds.). So I think the built-in function " IndependencePolynomial " should be able to be improved. (Of course we are usually very concerned about their coefficients) 

Their coefficients of the independent polynomial of G1 are as follows.

[340649, 12329124, 68797662, 140606548, 139481127, 77027880, 25546428, 5303544, 700911, 58580, 2982, 84, 1]

It tells me the total number of independence sets with size 12 is 340649. 

Edits: In fact it is a set partition problem.

I have the following subsets: 

s:={"a","b","c","d","e","f"}:

I want to divide the set into 2 groups such that each group has exactly 3 elements. We want to generate all solutions. Note that we treat ({"a", "b", "c"}|{"d", "e", "f"}) and ({"d", "e", "f"}|{"a", "b", "c"}) as the same solution.

So first I used the choose function to generate all 3-subsets and then filtered for duplicate solutions.

with(combinat):
M:=[op(choose({"a","b","c","d","e","f"},3))]:
l:=[ListTools:-Categorize((x,y)-> is(x =`minus`(s, y)),M)]:
seq(l[i][1],i=1..10)

{"a", "b", "c"}, {"a", "b", "d"}, {"a", "b", "e"}, {"a", "b", "f"}, {"a", "c", "d"}, {"a", "c", "e"}, {"a", "c", "f"}, {"a", "d", "e"}, {"a", "d", "f"}, {"a", "e", "f"}

But I feel like the solution is a bit inefficient. In fact, we only need half of all 3-subsets. I wonder if we can only keep one representative member of the same  solutions when generating the 3-subsets. 

gengcuts.mw

 In fact, the problem can be generalized as follows: given a list of n elements, divide it into m groups and generate all solutions. Similarly,  the same solution is generated only once.