论文标题
单向签名图中的圆形流
Circular flows in mono-directed signed graphs
论文作者
论文摘要
在本文中，引入了单向签名的图形$（g，σ）$中圆形$ r $ $ $ $ $ $ $ r $的概念。那是一对$（d，f）$，其中$ d $是$ g $ and $ f：e（g）\ to（-r，r）$的方向，满足每个正缘$ e $ e $ e $ e $ and $ e $ e $ and $ | f（e $ e $ and $ | f（e）$的$ | f（e）| [\ frac {r} {2} +1，r）$ $ $ $，$ e $，总流量等于每个顶点处的总流量。签名图$（g，σ）$的圆流索引，没有正桥，表示为$φ_c（g，σ）$，是最小$ r $ $ r $，使得$（g，σ）$允许循环$ r $ $ flow。这是圆形着色和圆形色素的双重概念，这些图表最近在[圆形色的符号图中引入了符号图。 R. Naserasr，Z。Wang和X. Zhu。 Electronic of Combinatorics，28（2）（2021），\＃P2.44]，与文献中研究的符号图相关的双向图中的圆形流的概念不同。我们给出了几个等效的定义，研究单向签名图中圆形流的基本特性，探索与图中流的关系，并关注$ g $的边缘连接性上的$φ_C（g，σ）$上的上限。 Meanwhile, we note that for the particular values of $r_{_k}=\frac{2k}{k-1}$, and when restricted to two natural subclasses of signed graphs, the existence of a circular $r_{_k} $-flow is strongly connected with the existence of a modulo $k$-orientation, and in case of planar graphs, based on duality, with同构为$ c _ { - k} $。
In this paper the concept of circular $r$-flows in a mono-directed signed graph $(G, σ)$ is introduced. That is a pair $(D, f)$, where $D$ is an orientation on $G$ and $f: E(G)\to (-r,r)$ satisfies that $|f(e)|\in [1, r-1]$ for each positive edge $e$ and $|f(e)|\in [0, \frac{r}{2}-1]\cup [\frac{r}{2}+1, r)$ for each negative edge $e$, and the total in-flow equals the total out-flow at each vertex. The circular flow index of a signed graph $(G, σ)$ with no positive bridge, denoted $Φ_c(G,σ)$, is the minimum $r$ such that $(G, σ)$ admits a circular $r$-flow. This is the dual notion of circular colorings and circular chromatic numbers of signed graphs recently introduced in [Circular chromatic number of signed graphs. R. Naserasr, Z. Wang, and X. Zhu. Electronic Journal of Combinatorics, 28(2)(2021), \#P2.44], and is distinct from the concept of circular flows in bi-directed graphs associated to signed graphs studied in the literature. We give several equivalent definitions, study basic properties of circular flows in mono-directed signed graphs, explore relations with flows in graphs, and focus on upper bounds on $Φ_c(G,σ)$ in terms of the edge-connectivity of $G$. Meanwhile, we note that for the particular values of $r_{_k}=\frac{2k}{k-1}$, and when restricted to two natural subclasses of signed graphs, the existence of a circular $r_{_k} $-flow is strongly connected with the existence of a modulo $k$-orientation, and in case of planar graphs, based on duality, with the homomorphisms to $C_{-k}$.
