The (Induced) Subgraph Isomorphism computational problem is, given H and G, determine whether there is a (induced) subgraph isomorphism from H to G. See https://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem

In Maple, IsSubgraphIsomorphic(G1,G2)  returns true if G1 is isomorphic to some subgraph of G2. However, it does not provide options for induced subgraphs. For example, 

with(GraphTheory):
claw:=CompleteGraph(1,3);
g:=CompleteGraph(2,2,2,2):
DrawGraph(g);
IsSubgraphIsomorphic(claw,g) #true

So the graph g contains a claw as a subgraph. But every claw in graph g  is non-induced. So g does not contain any induced claw. Maple does not appear to have this feature to determine if a graph contains a induced subgraph isomorphic to another graph. It is unclear whether we can modify some code in IsSubgraphIsomorphic  to achieve this goal.

with(GraphTheory):
s:=DrawGraph(CompleteGraph(5),size=[250,250])
Export("D:\\s1.jpg",s)

But I would like to export it using PDF format. However, the modified code below seems to be quite unsuccessful. I am aware that Maple has export options in the front end, but I still prefer to use code for this purpose.

Export("D:\\s1.pdf",s)

Error, (in Export) invalid input: member received _ImportExport:-InfoTable["PDF"][4], which is not valid for its 2nd argument, s

There are two reasons for this.

• One is for batch conversion;
•  the second is the previously mentioned issue (see https://www.mapleprimes.com/questions/236142-How-To-Remove-The-Mosaic-Of-Vertices) that has not been resolved. I'm thinking that perhaps converting Tabulate to PDFs using codes  might remove the mosaic issue.

with(GraphTheory):
Graphs:=[NonIsomorphicGraphs(6,8,output=graphs,outputform = graph)]:
num_g:=nops(Graphs):
num:=ceil((num_g)/5.):
Matrix (num,5,(i,j)->`if`((i-1)*5+j<=num_g, DrawGraph(Graphs[(i-1)*5+j],size=[250,250] ,overrideoptions ,showlabels=false,style=planar, stylesheet =  [
 vertexcolor     = orange
,vertexfontcolor = black
,vertexborder    = false
,edgethickness   = 0.6
,edgecolor       = MidnightBlue
,vertexshape     =  "circle"
,vertexfont      = [Arial, 4],
vertexthickness=5], caption = cat(H__,5*(i-1)+j),captionfont=["ROMAN",7]),plot(x = 0 .. 1, axes = none))):
DocumentTools:-Tabulate (M1[1..5,.. ],widthmode=percentage ,width=80 , exterior =all):

There are various variants of graph coloring, such as when I want to compute the star chromatic number of a graph, Maple (or Mathematica) seems not to provide relevant functions.

Fortunately, the software ColPack   offers this functionality （Note: I just noticed that this software also uses greedy coloring instead of accuracy）. However, it supports the MTX format. So, the question is: 

•  How can I write a graph in MTX format?

And 

•  how can the MTX format be converted into a graph format?

Of course, I would like to perform these operations in Maple.  (SageMath may have something)

The following is an example (bcsstk01.mtx） in the directory `ColPack-master/Graphs directory` of the source code of ColPack.

bcsstk01.mtx.txt

./ColPack -f ../../Graphs/bcsstk01.mtx -m STAR
 Out: 11

But I do not know what the graph in the example is. On the contrary, I would like to compute the star chromatic number of the Petersen graph, and I also don't know how to convert it into the MTX format like the above.

with(GraphTheory):
with(SpecialGraphs):
P:=PetersenGraph()

I don't understand what the very long decimal numbers (like 2.8322685185200e+06) in the third column in the MTX-file. Will it affect the  imformation of the entire graph?

For MTX format, see https://math.nist.gov/MatrixMarket/formats.html.  For graphs, the numbers in the third column can all be considered as 1 (with the first two columns representing vertices, and their adjacency). Of course, this is my interpretation and may not necessarily be correct.

The following  question I asked a long time ago.

• How to determine the number of cycles of graph

The user Carl Love provided a nice answer regarding the counting of cycles. Back then, I was only interested in the number of cycles, but now I am also interested in finding out these cycles.

I noticed sand15's answer where he (or she) attempted to use the cycle basis to find all cycles. This approach is theoretically viable. However, it seems that his (her) implementation had some instances of missing cycles.  (mmcdara‘s answer is also missing some cycles)

So I brought up this question again to draw attention to it. The only distinction is that I may have specifically mentioned the use of a cycle basis method. Additionally, I may give another question:

• How do we generate all cycles with a specific length (by cycle basis)?

 However, I remain open-minded about alternatives that do not involve a cycle basis. 

The SageMath approach for that can be referred to the link, which is actually why I remembered this question. It feels like the function in linear algebra that generates all elements through a basis would be effective.

g=graphs.OctahedralGraph()
def gen_simple_cycles(G):
    C = [frozenset(tuple(sorted(e[:2])) for e in c) for c in G.cycle_basis(output='edge')]
    for S in Subsets(C):
        T = set()
        for c in S:
            T = T.symmetric_difference(c)
        H = Graph(T, format='list_of_edges')
        if H.is_eulerian() and max(H.degree(),default=0)==2:
            yield H.eulerian_circuit(return_vertices=True)[1]
list(gen_simple_cycles(g))

[[0, 4, 2, 0],
 [0, 4, 3, 0],
 [0, 4, 5, 1, 0],
 [2, 5, 4, 2],
 [3, 5, 4, 3],
 [0, 3, 1, 0],
 [0, 2, 1, 0],
 [0, 3, 4, 2, 0],
 [0, 2, 4, 5, 1, 0],
 [0, 4, 5, 2, 0],
 [0, 4, 2, 1, 0],
 [0, 3, 4, 5, 1, 0],
 [0, 4, 5, 3, 0],
 [0, 4, 3, 1, 0],
 [0, 4, 2, 5, 1, 0],
 [0, 4, 3, 5, 1, 0],
 [0, 4, 5, 1, 3, 0],
 [0, 4, 5, 1, 2, 0],
 [2, 5, 3, 4, 2],
 [0, 3, 1, 2, 0],
 [0, 3, 4, 5, 2, 0],
 [0, 3, 5, 4, 2, 0],
 [0, 2, 4, 3, 1, 0],
 [0, 3, 4, 2, 1, 0],
 [0, 2, 5, 1, 0],
 [0, 2, 4, 3, 5, 1, 0],
 [0, 3, 1, 5, 4, 2, 0],
 [1, 5, 4, 2, 1],
 [0, 4, 3, 5, 2, 0],
 [0, 4, 5, 2, 1, 0],
 [0, 4, 2, 1, 3, 0],
 [0, 3, 4, 2, 5, 1, 0],
 [0, 3, 5, 1, 0],
 [1, 5, 4, 3, 1],
 [0, 3, 4, 5, 1, 2, 0],
 [0, 4, 2, 5, 3, 0],
 [0, 4, 5, 3, 1, 0],
 [0, 4, 3, 1, 2, 0],
 [0, 4, 2, 5, 1, 3, 0],
 [0, 4, 3, 5, 1, 2, 0],
 [0, 3, 5, 2, 0],
 [0, 2, 5, 4, 3, 1, 0],
 [0, 3, 4, 5, 2, 1, 0],
 [0, 2, 4, 5, 3, 1, 0],
 [0, 3, 5, 4, 2, 1, 0],
 [1, 3, 4, 2, 1],
 [0, 3, 1, 5, 2, 0],
 [1, 5, 2, 1],
 [1, 5, 3, 4, 2, 1],
 [0, 4, 3, 5, 2, 1, 0],
 [0, 4, 5, 2, 1, 3, 0],
 [1, 5, 2, 4, 3, 1],
 [1, 5, 3, 1],
 [0, 3, 5, 1, 2, 0],
 [0, 4, 2, 5, 3, 1, 0],
 [0, 4, 5, 3, 1, 2, 0],
 [0, 4, 3, 1, 5, 2, 0],
 [0, 4, 2, 1, 5, 3, 0],
 [0, 2, 5, 3, 1, 0],
 [0, 3, 5, 2, 1, 0],
 [1, 3, 4, 5, 2, 1],
 [1, 3, 5, 4, 2, 1],
 [1, 3, 5, 2, 1]]

Total: 63 cycles.

A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that occur after v in the order form a clique.  A graph is chordal if and only if it has a perfect elimination ordering.

I  use IsChordal  to test whether the lexicographic product of  two graphs g1,g2 is a chordal graph. It returned true and provided a perfect elimination sequence 1, 2, ..., 30. However, vertices of s  are "1:1", "1:2", ..., "10:3", rather than using Arabic numerals. Therefore, it is difficult for me to extract useful information from the perfect elimination sequence.

Download ischordgraph.mw