# [seqfan] Re: Multiplicative Graphs

Andrew Weimholt andrew at weimholt.com
Fri Oct 23 09:34:20 CEST 2009

```Perhaps I write a program this weekend, if someone else doesn't beat me to it.
I've written some graph generation programs before, so I've got some
code lying around that can easily be adapted for computing this
sequence. I'd do it sooner, but I'm swamped with work until the
weekend.

Andrew

On Thu, Oct 22, 2009 at 10:04 PM,  <franktaw at netscape.net> wrote:
> 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.
>
>
> -----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.
>>
>>
>>
>>  _______________________________________________
>>
>>  Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
>
>
>
>
>
>

```