## 1004 Reputation

5 years, 152 days
changsha, China

## @Carl Love Thank you for telling me...

@Carl Love Thank you for telling me. I understand now. I remember you mentioned it to me before, but I forgot the specific post where it was.😊

## What does op(4,G) represent?...

@Carl Love Nice. What does `op(4,G)` represent? It seems not to be an edge list after relabeling.

For example,

`op(4,CanonicalGraph(GraphTheory:-PathGraph(3)))`

it shows me:

Vector[row](3, [{3}, {3}, {1, 2}])

Now, I don't want to classify them; I would like to obtain the final set of non-isomorphic graphs.

## Great...

@dharr Great! I wonder why SageMath only provides a version for directed graphs and not for undirected graphs. Perhaps it is also based on the same (or similar) algorithm due to Tarjan.

```g = graphs.OctahedralGraph()
undirected_cycles = [ c for c in g.to_directed().all_simple_cycles() if len(c)>=4 and c[1]<c[-2] ]
len(undirected_cycles)
```

63

## the design of op(4,inputgraph)...

@Carl Love I'm not just referring to that. I mean the design of `op(4,inputgraph)`, which doesn't care about the vertex label of the input graph but instead uses `i `to correspond to the i-th vertex of `op(3,inputgraph)` , i.e.,` Vertices(inputgraph)`​​​​​​​.

I did not see any explanation of `op(4,inputgraph)` in the Maple help documentation.

## Great...

@Carl Love I have looked at many graphs, and the rules are indeed like this. I don't know if the Maple help documentation mentions anything related to this.

## You are correct....

@tomleslie Indeed, I noticed that the starting point in`IsChordal` may  reconstruct  the input graph. However, for the readability of the output of `IsChordal` , I believe it should return the vertex labels of the input graph in the end.

`print(IsChordal)`

proc (G::GRAPHLN, { eliminationordering::truefalse := false,

usecached::truefalseFAIL := FAIL }, ` \$`)::truefalse; local

ischordal, L, A; A := op(4, G); ischordal, L := MaximumCardin\

alitySearchImpl(A, true); if eliminationordering then return

ischordal, L else return ischordal end if end proc

Moreover, this isomorphism mapping seems to be determined at the beginning. Otherwise, searching for it through the isomorphism function at the end may not be efficient.

## NP-complete...

@Carl Love You are right!  The goal of efficiency is unrealistic for a general graph. The DOMINATING SET problem in an undirected graph G is the problem of determining, for a given positive integer k, whether G has a dominating set D in G satisfying |D|≤ k. This is a well-known NP-complete problem.

•  A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).
• M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976) 237-267.

Which article are you referring to when you mentioned the algorithm for finding the domination number of triangle-free graphs? Recently, I saw a new interesting monograph on domination sets. I would be happy to recommend it.

• Domination in Graphs: Core Concepts (Teresa W. Haynes, Stephen T. Hedetniemi, Michael A. Henning) Springer.

## Good!...

@vlineze In fact, your use of "break" twice here is equivalent to using `break i`. See the answer by Rouben Rostamian

## I know...

@Rouben Rostamian  Thank you very much. I'm aware of this command `break`. ( In fact, I copied codes from there.) I was just curious. As for Carl Love's statement about the inefficiency (in terms of execution time?) of "goto," it goes against my intuition as well.  As  sursumCorda mentioned, in many programming languages, "goto" is actually efficient. However, it is not recommended for use due to its detrimental effect on code readability and logical structure.

## undocumented....

@Axel Vogt The "goto" statement does not appear to be documented in the help documentation.

## Thank you!...

@Carl Love Indeed, the previous title was too cumbersome. I have simplified it.

## very cool!...

@Carl Love Your code is very cool!  Although I can't understand right away why it can find a minimum dominating set (the underlying principles behind it), one method I know of for finding a minimum dominating set (or the domination number) is to convert it into an integer programming problem.

See page 450 of the  book "Computational Mathematics with SageMath" ( http://dl.lateralis.org/public/sagebook/sagebook-ba6596d.pdf)

## Great...

@dharr That's great. I didn't notice there was a similar question before. I still accept the length. However, it would be best to return a shortest closed  spanning walk for checking.  The length you give is exaclty Hamiltonian number.

## hope clarification...

@vs140580 To be honest, I didn't understand the requirements of your original post, especially, the second one:

•  ii) An edge in  the list H will occur exactly twice only in the entire list of graphs

I think it's best to ask a question with a small example.

See this link and tomleslie gave a maple solution.

Or use `is_subgraph` in sagemath (maybe more efficient).

```G = graphs.PetersenGraph()
H = Graph({1: [2, 3, 4]})
L = list(G.subgraph_search_iterator(H, induced=False))
len(L)
```

60

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