[seqfan] Re: Counting simple graphs with node degree >=2

Georgi Guninski guninski at guninski.com
Wed Sep 16 14:01:44 CEST 2015


On Mon, Sep 14, 2015 at 01:34:07PM +0200, Richard J. Mathar wrote:
> Is the number of simple (loopless, undirected, no multi-edges, connected,
> unlabelled) graphs on n nodes in the OEIS, counting only graphs where
> each node has at least degree 2 (or simpler: where each edge is part
> of at least one circuit)?
> 
> My manual count proposes this starts a(3)=1, a(4)=3, a(5)>=8, a(6)>=13.

In sage with nauty package, from 3 to 9 I get:
1 , 3 , 11 , 61 , 507 , 7442 , 197772

So far this appears
A004108 Number of n-node unlabeled connected graphs without endpoints. 

sage code, you can run it in a browser in the cloud:


def mathar1():
	"""
	sage code
	requires optional package nauty
	"""
	for n in [ 3 .. 9]:
		cou=0
		for g in graphs.nauty_geng("%s -c -d2"%n): 
		#-c means connected, -d \delta=2
			cou += 1
		print cou,",",
		sys.stdout.flush()





More information about the SeqFan mailing list