ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 16 Oct 2022 16:24:36 +0200Finding all non-isomorphic $C_5$-free connected planar graphs of order 11.https://ask.sagemath.org/question/64468/finding-all-non-isomorphic-c_5-free-connected-planar-graphs-of-order-11/Let us say that a graph is $H$-free if it does not contain $H$ as a subgraph (whether induced or not). We denote $C_5$ as a cycle with 5 vertices. Then I would like to find all the $C_5$ free planar connected graphs of order 11. (I can't estimate the number of them, hope it's not too many.) I tried to write the following code.
def C5free(g):
test=not graphs.CycleGraph(5).is_subgraph(g,induced=False)
return test
First, to check that the code will be executed correctly, I tried to filter out the 6 vertex $C_5$ free connected planar graphs. But the following code does not seem to filter the desired ones very well. Because 179 is the total number.
g6a=[g for g in graphs.planar_graphs(6,minimum_connectivity=1) if C5free(g)==True];
len(g6a) #179
g6b=[g for g in graphs.planar_graphs(6,minimum_connectivity=1)];
len(g6b) #179
However, obviously the graph with 6 vertices below is not $C_5$-free.
g=Graph([(0,1),(1,2),(2,3),(3,4),(4,0),(0,5)])
![image description](/upfiles/1665930384756148.png)
In addition, among these graphs, there may be some graphs being isomorphic to each other. Because we can see from the sequence about conencted planar graphs from https://oeis.org/A003094/list. It tells us that 99 is the number of non-isomorphic connected planar graphs on 6 vertices.lichengSun, 16 Oct 2022 16:24:36 +0200https://ask.sagemath.org/question/64468/iterate over all directed acyclic graphs (DAGs) on n verticeshttps://ask.sagemath.org/question/56190/iterate-over-all-directed-acyclic-graphs-dags-on-n-vertices/Is there a simple way to iterate over all DAGs on n vertices?
So far, I do this via posets and gray code like shown below, but is it an overkill?
**UPDATE.** The code is corrected, thanks to *tmonteil*.
from sage.combinat.gray_codes import product as gc_product
def Dags0(n):
for P in Posets(n):
H = P.hasse_diagram()
E = list( set(H.transitive_closure().edges(labels=False)) - set(H.edges(labels=False)) )
G = H.copy()
C = G.canonical_label()
CC = set(C.dig6_string())
yield C
for e,d in gc_product([2]*len(E)):
if d>0:
G.add_edge(E[e])
else:
G.delete_edge(E[e])
C = G.canonical_label()
dig6 = C.dig6_string()
if dig6 not in CC:
CC.add(dig6)
yield CMax AlekseyevTue, 16 Mar 2021 21:23:41 +0100https://ask.sagemath.org/question/56190/Adding edges to a graphhttps://ask.sagemath.org/question/52261/adding-edges-to-a-graph/This is my first time using this forum so please let me know if more information is needed
I am trying to some basic conjecture testing, so I'm not too concerned about runtime. I am trying to count graphs which are "maximal triangle-free and 3-colorable", ie triangle-free and 3-colorable, and adding any missing edge breaks one of those 2 properties. But I don't know how to test that property about adding edges to a graph, since I don't know how to add edges to a graph. I'm mainly using the Sage page on undirected graphs. My rudimentary code so far is below:
> n = 5
> list = []
> for i in range(1, n):
> list.append([])
> for g in graphs(i):
> if g.is_triangle_free() and g.chromatic_number() <= 3:
> list[i-1].append(g)
listbottled-capsMon, 29 Jun 2020 20:55:59 +0200https://ask.sagemath.org/question/52261/How to get all digraphs with loopshttps://ask.sagemath.org/question/35736/how-to-get-all-digraphs-with-loops/ I'm trying to count all of the directed graphs on n vertices which have fixed in/out degree, up to isomorphism. I would like to allow loops, though not multiple edges. I can't figure out how to tell the digraphs iterrator to include the ones with loops, though i see this is an option in the graphs iterator. I would appreciate suggestions to get around this/explanations why it is not an option.BillyFri, 25 Nov 2016 10:30:55 +0100https://ask.sagemath.org/question/35736/Using a lambda expression in digraphs fails for len(G.sinks())?https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/I'm gathering digraphs that have exactly one sink.
This list comprehension works fine to find the 6 such digraphs of order 3 & put them in a list:
[G for G in digraphs(3) if len(G.sinks()) == 1]
However, I need this to work in a lambda expression to make it part of a larger calculation. However,
digraphs(3,lambda G: len(G.sinks()) == 1)
creates an iterator that returns no entries.
Creating a lamba expression creates the same unexpected zero-length iterator in digraphs, but that same iterator correctly finds the 6 single-sink digraphs if used in a for expression:
sage: property = lambda G: len(G.sinks()) == 1
sage: T = digraphs(3, property)
sage: print(list(T))
[]
sage: for H in digraphs(3):
....: print property(H)
....:
False
False
False
True
False
False
False
False
True
True
True
True
False
True
False
False
So, what's the right way to generate the one-sink digraphs of order N directly in the digraphs() generator?
jim_snydergrantThu, 12 May 2016 17:05:40 +0200https://ask.sagemath.org/question/33384/Why the function graphs() can't generate graphs?https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/ sage: L = list(graphs(5, lambda G: max(G.degree()) >= 2))
sage: len(L)
0
sage: L = list(graphs(5, lambda G: max(G.degree()) < 2))
sage: len(L)
3
sage: L = list(graphs(5))
sage: len(L)
34
dannyFri, 19 Sep 2014 01:34:45 +0200https://ask.sagemath.org/question/24199/