# [seqfan] Re: Multiplicative Graphs

Andrew Weimholt andrew at weimholt.com
Fri Oct 23 03:06:18 CEST 2009

```I am also tempted to conjecture that the only odd terms are a(p)=1, for prime p

Andrew

On 10/22/09, Andrew Weimholt <andrew at weimholt.com> wrote:
> 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.
>  >
>  >
>  >
>  >  _______________________________________________
>  >
>  >  Seqfan Mailing list - http://list.seqfan.eu/
>  >
>  >
>

```