## 11 Badges

5 years, 152 days
changsha, China

## Filter out non-isomorphic graphs by cano...

Maple 2024

I would like to remove isomorphs from some graphs. That is to filter out non-isomorphic graphs.

```graph_list := [GraphTheory:-CompleteGraph(3), GraphTheory:-PathGraph(3),Graph({{a,b},{b,c},{c,a}})]:

# Create a table to store non-isomorphic graphs
non_isomorphic_graphs := table():

# Counter for indexing the table
counter := 1:

# Iterate over each graph and check if it is isomorphic to any of the stored graphs
for g in graph_list do
is_isomorphic := false:
for key in indices(non_isomorphic_graphs,'nolist') do
if GraphTheory:-IsIsomorphic(g, non_isomorphic_graphs[key]) then
is_isomorphic := true:
break:
end if:
end do:
if not is_isomorphic then
non_isomorphic_graphs[counter] := g:
counter := counter + 1:
end if:
end do:
op(non_isomorphic_graphs)
DrawGraph~(non_isomorphic_graphs,  layoutoptions = [neutral_color = "pink", initial = spring])
```

A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. I noticed that Maple has a function called CanonicalGraph. Can this function achieve the effect I want? I can easily achieve this by combining the  canonical form and property of sets  in  Sage.

```graph_list = [Graph([(0, "a"), ("a", 2), (2, 0)]),graphs.PathGraph(3), graphs.CompleteGraph(3)]
non_isomorphic_graphs_labels = {g.canonical_label().copy(immutable=True) for g in graph_list}```

An underlying motivation：My collaborators and I designed generation rules (algorithms) for 1-planar 4-trees；see https://arxiv.org/abs/2404.15663. Since the generating process is based on 1-planar embeddings, it will ultimately require filtering non-isomorphic graphs among a list of embeddings. I would be especially delighted to see that someone implement our algorithm in the future. Currently, I am stuck on handling some labeling details. It is somewhat similar to generating Apollonian networks (planar 3-trees). However, since its simplicial vertices are only two, the growth rate will not be too fast as the number of vertices increases.

## Something about the new function AllGrap...

Maple 2024

`AllGraphs` is a new function in Maple 2024. Good things！

However, it seems that most of its functionalities are already provided by `NonIsomorphicGraphs`, and its speed even lags behind that of `NonIsomorphicGraphs`

I'm curious about what truly sets this function apart from existing ones. It generates isomorphic graphs if `nonisomorphic=false`But I donot know what its application is. Supporting directed graphs is a new thing, but its speed is not well.

``````iterator := GraphTheory[AllGraphs](vertices = 6, edges =6..7, connected, nonisomorphic)
s:=[seq(p, p = iterator)]:
nops(s)
``````

Note that this function is suitable for generating non-isomorphic connected graphs with 6 vertices and either 6 or 7 edges. It doesn't hold an advantage in terms of speed， and`NonIsomorphicGraphs` also provides an iteration option.

## Finding induced subgraph isomorphism nee...

Maple 2023

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.

## Exporting Graphs to PDF Using Maple Code...

Maple 2023
The following code effectively converts the image to the JPG format.
```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.

```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):

```

## How can we convert between mtx-format an...

Maple 2023

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.

 1 2 3 4 5 6 7 Last Page 1 of 25
﻿