- Tytuł:
- On Eulerian irregularity in graphs
- Autorzy:
-
Andrews, Eric
Lumduanhom, Chira
Zhang, Ping - Tematy:
-
Eulerian walks
Eulerian irregularity - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/31232740.pdf Link otwiera się w nowym oknie
- Opis:
- 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 \(\binom{m+1}{2} \le EI(G) \le 2 \binom{m+1}{2}\). 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł