[seqfan] Re: graphs with odd degrees
Georgi Guninski
guninski at guninski.com
Thu Apr 5 12:34:37 CEST 2012
On Wed, Apr 04, 2012 at 09:03:09AM -0700, Tanya Khovanova wrote:
> Hello all,
>
> Me and my student are working on a project where we encountered graphs with all odd degrees. I couldn't find the sequence in the OEIS. Will someone like to generate it?
>
>
> We submitted two sequences:
> A210345 The number of degree sequences of simple graphs with n vertices with all even degrees.
> and
> A210346 The number of degree sequences of simple graphs with 2n vertices with all odd degrees.
>
> The sequences need more terms. And I do not know how to enumerate graphs themselves.
>
> Tanya
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
For enumerating non-isomorphic I use naytu [1] geng.
You can parse the graphs in whatever language, but since nauty is
optional package for sage I use it from sage.
Attached is a sample sage implementation which agrees with your terms to
a(9).
[1] http://cs.anu.edu.au/~bdm/nauty/
-------------- next part --------------
def tanya2():
"""
A210345 The number of degree sequences of simple graphs with n vertices with all even degrees.
"""
an=[]
MAXN=9
for n in xrange(1,MAXN+1):
gn=graphs.nauty_geng("%s"%n)
cac={}
for G in gn:
d=G.degree_sequence()
d.sort()
d=tuple(d)
v=uniq([i%2 for i in d])
if v==[0]:
cac[d]=1
a=len(cac.keys())
print 'a(%s)=%s'%(n,a)
an += [a]
return an
an=tanya2()
an
More information about the SeqFan
mailing list