[seqfan] Re: Multiplicative Graphs

franktaw at netscape.net franktaw at netscape.net
Fri Oct 23 07:04:51 CEST 2009

I agree with both corrections.

However, I get a(48) = 45.

Continuing, I get:


with a(64) being the next term to be computed.

I'd still like for somebody with some graph generation software to 
compute these mechanically, preferably on to larger values.

Franklin T. Adams-Watters

-----Original Message-----
From: Andrew Weimholt <andrew at weimholt.com>

Hi Franklin,

nice idea for a sequence!
Your sequence is missing either a(9) or a(10)
>  1,1,1,1,2,1,2,1,4,2,1,6
should be

Also, by hand, I get a(36) = 24, not 23.

and I get a(48) = 42


On 10/22/09, franktaw at netscape.net <franktaw at netscape.net> wrote:
> For a given graph, suppose we take the product of the valences of the
>  vertices.
>  The question is how many graphs have a given product.  To avoid
>  infinities, we will consider only one-component graphs; that is,
>  connected graphs excluding the empty graph.  (If we allow the the 
>  graph, a(1) will be one larger.)
>  Since valence 1 nodes don't directly affect the product, we can look 
>  the graph that results when they are removed.  This will be a 
>  graph, and labeling each node with its original valence, the product 
>  the labels will be the original product.  Each node must be labeled
>  with at least its valence, and at least 2.  Furthermore, each such
>  labeling, up to graph equivalence, uniquely defines the original 
>  -- so this gives us a way to compute the sequence.
>  For a given n, we need only look at connected graphs with at most
>  BigOmega(n) (A001222) nodes.  In particular, if n is prime, a(n) = 1,
>  and if n is a semiprime, a(n) = 2.
>  Hand-calculating, and starting with n = 0 (the one-point graph), I 
>  1,1,1,1,2,1,2,1,4,2,1,6,1,2,2,8,1,6,1,6,2,2,1,16,
>  2,2,4,6,1,8,1,16,2,2,2,23,1,2,2,16,1,6,1,6,6,2,1
>  I don't know what a(48) is.
>  I would appreciate it if someone could (1) verify these values, and 
>  compute some more.  Anything else anyone can contribute about the
>  sequence would also be welcome.
>  Franklin T. Adams-Watters
>  _______________________________________________
>  Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list