lcz

1004 Reputation

11 Badges

5 years, 94 days
changsha, China

MaplePrimes Activity


These are replies submitted by lcz

@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.😊

@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.

 

 

@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

@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.

@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.

@tomleslie Indeed, I noticed that the starting point inIsChordal 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.

@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.

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

@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.

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

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

@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)

 
 

@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.

@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