On eulerian irregularity in graphs

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