[seqfan] Re: Number of Euler graphs: A002854 or something else?
Brendan McKay
bdm at cs.anu.edu.au
Fri Feb 5 01:56:38 CET 2010
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
More information about the SeqFan
mailing list