[Nauty] Fwd: Re: select C5-free graphs

[sterten at posteo.de]

-------- Originalnachricht --------
Betreff: Re: [Nauty] select C5-free graphs
Datum: 03.10.2023 16:23
Von: sterten at posteo.de
An: lczhangmath <lczhangmath at 163.com>

hi Licheng,

I thought, I had posted this to the mailing list ...
We probably discussed it there in 2005.
As I remember, it worked well, compiled with old gcc


http://magictour.free.fr/geng-.c
http://magictour.free.fr/geng-.o
http://magictour.free.fr/geng-.exe (old 16-bit windows command-line 
version)
linked with some other nauty*.o files
forbid.sub contains the adjacency-matrices without cr/lf , one graph per 
line
here an example from 2016 - I don't remember, what it was
http://magictour.free.fr/forbid.sub

regards, Guenter Stertenbrink


Am 03.10.2023 15:53 schrieb lczhangmath:
> Sorry. I miss the information: generates all graphs which have none of
> the graphs in file forbid.sub as a vertex-induced subgraph
> 
> I am very interested in your file. And if you give me the source
> codes, it would be more nice (as some complied file cannot run in
> different computer)
> 
> Thanks
> 
> Best wishes.
> 
> Licheng.
> 
> ---- Replied Message ----
> 
> 		From
> 		sterten<sterten at posteo.de>
> 
> 		Date
> 		10/03/2023 21:35
> 
> 		 To
> 		lczhangmath <lczhangmath at 163.com>
> 
> 		Subject
> 		Re: [Nauty] select C5-free graphs
> 
> I had made a version geng-.c , geng-.o , geng-.exe in 2005 , which I
> can
> upload if there is interest
> 
> usage:geng- [-cCmtfbd#D#] [-uygsnh] [-lvq] [-x#X#] n [mine[:maxe]]
> [res/mod] [file]
>  generates all graphs which have none of the graphs in file forbid.sub
> 
>  as a vertex-induced subgraph
> 
>  n : the number of vertices (1..32)
>  mine:maxe : a range for the number of edges
>  #:0 means '# or more' except in the case 0:0
>  res/mod : only generate subset res out of subsets 0..mod-1
> 
>  -c : only write connected graphs
>  -C : only write biconnected graphs
>  -t : only generate triangle-free graphs
>  -f : only generate 4-cycle-free graphs
>  -b : only generate bipartite graphs
>  (-t, -f and -b can be used in any combination)
>  -d# : a lower bound for the minimum degree
>  -D# : a upper bound for the maximum degree
>  -v : display counts by number of edges
>  -l : canonically label output graphs
>  -u : output all graphs, else just generate and count them
>  See geng.c for much more information.
> 
> Am 02.10.2023 08:22 schrieb lczhangmath:
>> Hello everyone,
>> 
>> 
>> I would like to know if nauty offers an option to select C5-free
>> graphs. (whether induced or not). Although I know it includes
> C3-free
>> and C4-free options (-T0 and -W0). Using some external scripts, for
>> example Python can also do it, or use SageMath:
>> 
>> 
>> sage: C5 = graphs.CycleGraph(5)
>> sage: good_graphs = [g for g in graphs(6, property=lambda G: not
>> C5.is_subgraph(G,induced=False, up_to_isomorphism=True ),
>> augment="edges") if g.is_connected()]
>> 
>> 
>> But how should I write the C version? I would like to learn how
> nauty
>> filters graphs. Of course, I prefer more general options such as
>> subgraph-free (or induced subgraph-free), although they are NP-hard
> in
>> terms of algorithms.
>> 
>> 
>> 
>> 
>> Best wishes.
>> Licheng Zhang
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> https://mailman.anu.edu.au/mailman/listinfo/nauty