Geodesic
On Eulerian irregularity in graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 391-408 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A closed walk in a connected graph G that contains every edge of G exactly once is an Eulerian circuit. A graph is Eulerian if it contains an Eulerian circuit. It is well known that a connected graph G is Eulerian if and only if every vertex of G is even. An Eulerian walk in a connected graph G is a closed walk that contains every edge of G at least once, while an irregular Eulerian walk in G is an Eulerian walk that encounters no two edges of G the same number of times. The minimum length of an irregular Eulerian walk in G is called the Eulerian irregularity of G and is denoted by EI(G). It is known that if G is a nontrivial connected graph of size m, then m+12≤ EI(G) ≤ 2 m+12. A necessary and sufficient condition has been established for all pairs k, m of positive integers for which there is a nontrivial connected graph G of size m with EI(G)=k. A subgraph F in a graph G is an even subgraph of G if every vertex of F is even. We present a formula for the Eulerian irregularity of a graph in terms of the size of certain even subgraph of the graph. Furthermore, Eulerian irregularities are determined for all graphs of cycle rank 2 and all complete bipartite graphs.
Keywords: Eulerian walks, Eulerian irregularity 
@article{DMGT_2014_34_2_a12,
     author = {Andrews, Eric and Lumduanhom, Chira and Zhang, Ping},
     title = {On {Eulerian} irregularity in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {391--408},
     year = {2014},
     volume = {34},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a12/}
}
TY  - JOUR
AU  - Andrews, Eric
AU  - Lumduanhom, Chira
AU  - Zhang, Ping
TI  - On Eulerian irregularity in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 391
EP  - 408
VL  - 34
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a12/
LA  - en
ID  - DMGT_2014_34_2_a12
ER  - 
%0 Journal Article
%A Andrews, Eric
%A Lumduanhom, Chira
%A Zhang, Ping
%T On Eulerian irregularity in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 391-408
%V 34
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a12/
%G en
%F DMGT_2014_34_2_a12
Andrews, Eric; Lumduanhom, Chira; Zhang, Ping. On Eulerian irregularity in graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 391-408. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a12/

[1] E. Andrews, G. Chartrand, C. Lumduanhom and P. Zhang, On Eulerian walks in graphs, Bull. Inst. Combin. Appl. 68 (2013) 12-26.

[2] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs: 5th Edition (Chapman & Hall/CRC, Boca Raton, FL, 2010).

[3] L. Euler, Solutio problematis ad geometriam situs pertinentis, Comment. Academiae Sci. I. Petropolitanae 8 (1736) 128-140.

[4] M.K. Kwan, Graphic programming using odd or even points, Acta Math. Sinica 10 (1960) 264-266 (in Chinese), translated as Chinese Math. 1 (1960) 273-277.