[seqfan] Re: Number of Euler graphs: A002854 or something else?

[franktaw at netscape.net]

"Eulerian graph" and "Euler graph" may be two different things.  
"Eulerian numbers" and "Euler numbers" certainly are (not that either 
of those has anything to do with the graphs).

Franklin T. Adams-Watters

-----Original Message-----
From: Brendan McKay <bdm at cs.anu.edu.au>

I did a quick survey of graph theory books on my shelves (about
a dozen) and found that ALL of them defined an "Eulerian graph"
to be a graph with an Eulerian tour ( = Eulerian circuit).

So while I am quite familiar with the definition that only requires
all degrees to be even (and used it myself at least once), it is
certainly not accepted as a standard. Also, the definition "having
an Eulerian tour" is the one that makes the most historical sense.

Interestingly, I found about 5 books with the following "theorem":
  A graph is Eulerian (i.e., has an Eulerian tour) iff it is connected
  and every vertex has even degree.
This is FALSE, since a graph remains Eulerian (by the definition in
those books) if isolated vertices are added.

Max's edits to Wikipedia need to be replaced by a discussion of the
variations of definition in the literature.  And OEIS should state
the definition being used for A002854.

Cheers, Brendan.


> Message: 4
> Date: Thu, 28 Jan 2010 11:59:58 -0500
> From: "N. J. A. Sloane" <njas at research.att.com>
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
>   else?
> To: seqfan at list.seqfan.eu
> Cc: njas at research.att.com
> Message-ID: <201001281659.o0SGxwrn005682 at prim.research.att.com>
> Content-Type: text/plain; charset=us-ascii
>
> Max,  I think you have misunderstood the definition of Euler graph.
> An Euler graph is a graph with every node having even degree.
>
> I will add a comment to A002854 to clarify this.
>
> References for this definition are
>
> 1. the "classic" paper which underlies A002854, namely
>
> %D A002854 C. L. Mallows and N. J. A. Sloane, Two-graphs, switching 
classes
and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 
876-880.
>
> (did you look at it?)
>
> and 2. the earlier references that it cites.
>
> Your definition :
>
> > Let us assume the conventional definition of Euler graphs:
> > a graph is Euler if there exists an Euler cycle, i.e., a cycle that
> > goes through every edge in the graph exactly once.
>
> is not right.
>
> As you say, one should be very careful before changing the classic 
sequences!
>
> Neil
>
> ------------------------------
>
> Message: 5
> Date: Thu, 28 Jan 2010 13:04:27 -0500
> From: Max Alekseyev <maxale at gmail.com>
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
>   else?
> To: njas at research.att.com
> Cc: seqfan at list.seqfan.eu
> Message-ID:
>   <d3dac271001281004l1a6cd180o7badd1b1547f650a at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> On Thu, Jan 28, 2010 at 11:59 AM, N. J. A. Sloane 
<njas at research.att.com>
wrote:
> > Max, ?I think you have misunderstood the definition of Euler graph.
>
> I've just followed the definitions given in MathWorld and Wikipedia.
> In particular, MathWorld defines Eulerian Graph as "a graph containing
> an Eulerian cycle."
> http://mathworld.wolfram.com/EulerianGraph.html
>
> That's especially confusing since MathWorld and A002854
> cross-reference each other.
>
> > An Euler graph is a graph with every node having even degree.
> >
> > I will add a comment to A002854 to clarify this.
>
> That settles things up. Thanks!
>
> > Your definition :
> >
> >> Let us assume the conventional definition of Euler graphs:
> >> a graph is Euler if there exists an Euler cycle, i.e., a cycle that
> >> goes through every edge in the graph exactly once.
> >
> > is not right.
>
> Well, at least I did not invent this definition.
>
> Regards,
> Max
>
> ------------------------------
>
> Message: 6
> Date: Thu, 28 Jan 2010 13:32:29 -0500
> From: Max Alekseyev <maxale at gmail.com>
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
>   else?
> To: njas at research.att.com
> Cc: seqfan at list.seqfan.eu
> Message-ID:
>   <d3dac271001281032q79fb9ba8s9a4b0f19cf8d6831 at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> On Thu, Jan 28, 2010 at 11:59 AM, N. J. A. Sloane 
<njas at research.att.com>
wrote:
>
> > References for this definition are
> >
> > 1. the "classic" paper which underlies A002854, namely
> >
> > %D A002854 C. L. Mallows and N. J. A. Sloane, Two-graphs, switching 
classes
and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 
876-880.
>
> I've corrected the definition given in Wikipedia article and cited
> this reference there.
> http://en.wikipedia.org/wiki/Eulerian_path
> Further improvements are welcome. In particular, there is still a
> confusing definition of semi-Eulerian graphs.
>
> Regards,
> Max


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/