×

On Eulerian irregularity in graphs. (English) Zbl 1290.05091

Summary: 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+1}\choose2}\leq EI(G)\leq2{{m+1}\choose2}\). 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.

MSC:

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C81 Random walks on graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[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.; · Zbl 0143.41904
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.