[seqfan] Re: Multiplicative Graphs
Andrew Weimholt
andrew at weimholt.com
Fri Oct 23 03:05:02 CEST 2009
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/
>
>
More information about the SeqFan
mailing list