Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems |
| |
Authors: | Zhiwei Guo Xueliang Li Chuandong Xu Shenggui Zhang |
| |
Institution: | 1. Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, PR China;2. Center for Combinatorics, Nankai University, Tianjin 300071, PR China;3. School of Mathematics and Statistics, Xidian University, Xi’an, Shaanxi 710071, PR China |
| |
Abstract: | A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system over a graph defines a set of transitions over . A compatible Eulerian circuit of an Eulerian graph with a generalized transition system is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by . In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively. |
| |
Keywords: | Eulerian (di)graph (Weakly) Generalized transition system Compatible Eulerian circuit |
本文献已被 ScienceDirect 等数据库收录! |
|