# On eulerian irregularity in graphs

Eric Andrews; Chira Lumduanhom; Ping Zhang

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 2, page 391-408
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topEric Andrews, Chira Lumduanhom, and Ping Zhang. "On eulerian irregularity in graphs." Discussiones Mathematicae Graph Theory 34.2 (2014): 391-408. <http://eudml.org/doc/268048>.

@article{EricAndrews2014,

abstract = {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 [...] . 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},

author = {Eric Andrews, Chira Lumduanhom, Ping Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Eulerian walks; Eulerian irregularity},

language = {eng},

number = {2},

pages = {391-408},

title = {On eulerian irregularity in graphs},

url = {http://eudml.org/doc/268048},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Eric Andrews

AU - Chira Lumduanhom

AU - Ping Zhang

TI - On eulerian irregularity in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 2

SP - 391

EP - 408

AB - 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 [...] . 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

LA - eng

KW - Eulerian walks; Eulerian irregularity

UR - http://eudml.org/doc/268048

ER -

## References

top- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.