# [seqfan] Re: A conjecture concerning connected rooted strength 1 Eulerian graphs with n nodes

Max Alekseyev maxale at gmail.com
Fri Mar 13 07:29:55 CET 2009

Here are the definitions from the paper
Dan Gusfield "Computing the Strength of a Graph"
http://dx.doi.org/10.1137/0220040

DEFINITION. G( V, E) is a connected undirected graph with nonnegative
edge weight s(e) on each edge e. The weight s(e) will be called the
strength of the edge e.

DEFINITION. For a set of edges A\subset E, let k(A) be the number of
additional connected components created by deleting edges A from G.
That is, k(A) is one less than the total number of components in G-A.

DEFINITION. Let S(A) be the total strength of the edges in A, i.e.,
S(A)=\sum_{e\in A} s(e).

DEFINITION. The strength of graph G, denoted \sigma(G), is defined as
min(S(A)/k(A)) taken over all subsets of edges A such that k(A)>0.

Regards,
Max

On Thu, Mar 12, 2009 at 3:28 PM, Jim Nastos <nastos at gmail.com> wrote:
> A007126  Number of connected rooted strength 1 Eulerian graphs with n nodes.
>
> I can't find (online) any definition of this 'strength 1' measure of
> Eulerian graphs or any kind of graph.
> Can someone provide a definition?
>
> JN
>
>
> On Thu, Mar 12, 2009 at 8:16 AM, Vladeta Jovovic <vladeta at eunet.yu> wrote:
>>
>>
>> SeqFans,
>>
>> There is  Eric Weisstein's recent seq. A158007:  number of simple connected noneulerian graphs on n nodes.
>> Clearly  A158007(n) = A001349(n) - A003049(n).
>>
>> Interestingly, it appears that Euler transform of  A158007(n) gives A007126(n+1).
>>
>> Can someone clarify that connection?
>>
>> Regards,
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>