Circular flows in mono-directed signed graphs

DOI10.1002/JGT.23092arXiv2212.10757MaRDI QIDQ6421176FDOQ6421176

Xuding Zhu, Zhouningxin Wang, Jiaao Li, Reza Naserasr

Publication date: 20 December 2022

Abstract: In this paper the concept of circular $r$-flows in a mono-directed signed graph $(G,sigma)$ is introduced. That is a pair $(D,f)$, where $D$ is an orientation on $G$ and $f:E(G)o(-r,r)$ satisfies that $|f(e)|in[1,r-1]$ for each positive edge $e$ and $|f(e)|in[0,fracr2-1]cup[fracr2+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,sigma)$ with no positive bridge, denoted $Ph{i}_c(G,sigma)$, is the minimum $r$ such that $(G,sigma)$ 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 $Ph{i}_c(G,sigma)$ in terms of the edge-connectivity of $G$. Meanwhile, we note that for the particular values of $r_{{}_k}=frac2kk-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}$.

Mathematics Subject Classification ID

Flows in graphs (05C21) Signed and weighted graphs (05C22)

Recommendations

• On \(\varepsilon\)-representations 👍 👎
• Holomorphic mappings of complex manifolds 👍 👎
• Eine Bemerkung zum Satz von Vitali über Konvergenz von Funktionenfolgen: Dem stets hilftsbereiten Herrn Kollegen H. L. Schmid, gewidmet 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Circular flows in mono-directed signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421176)