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

[Valery Liskovets]

In A007126, strength-1 means being a simple graph (i.e. without multiple
edges and loops). Cf. the description of A002854 (number of Euler graphs);
and the initial 1, 0, 1, 1, 6 can be easily verified.

Btw, there is a simple bijective transformation of arbitrary n-graphs into
rooted Eulerian (n+1)-graphs: add an external root-vertex and connect it
with the odd-valent vertices.

Valery Liskovets

Max Alekseyev wrote:

> 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
> >