[seqfan] Re: Multiplicative Graphs

[franktaw at netscape.net]

I agree with both corrections.

However, I get a(48) = 45.

Continuing, I get:

1,1,1,1,2,1,2,1,4,2,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,24,1,2,2,16,1,6,1,6,6,2,1,
45,2,6,2,6,1,19,2,16,2,2,1,36,1,2,6

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
1,1,1,1,2,1,2,1,4,2,2,1,6,...

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

and I get a(48) = 42

Andrew


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 
empty
>  graph, a(1) will be one larger.)
>
>  Since valence 1 nodes don't directly affect the product, we can look 
at
>  the graph that results when they are removed.  This will be a 
connected
>  graph, and labeling each node with its original valence, the product 
of
>  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 
graph
>  -- 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 
get:
>
>  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 
(2)
>  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/
>
>