符号图的符号线图的无零流


扩展功能
	加入收藏夹

	复制引文信息

	加入引用管理器

	Email Alert

	RSS
本文作者相关文章
	何静

	文超

	章超

符号图的符号线图的无零流

何静, 文超, 章超

贵州大学数学与统计学院, 贵州贵阳 550025

收稿日期：2024-06-11; 接收日期：2024-10-22

基金项目：国家自然科学基金资助(12461006), 贵州省自然科学基金重点项目资助(ZD[2025]085).

作者简介：何静(1999–), 女, 土家族, 贵州铜仁, 硕士研究生, 主要研究方向: 图论. E-mail: jinghe19990627@163.com.

通讯作者：章超(1986–), 男, 土家族, 湖北宜昌, 教授, 主要研究方向: 同调代数与代数表示论. E-mail: zhangc@amss.ac.cn.

摘要：本文研究了符号图的符号线图的无零流问题. 利用数学归纳法以及分析符号图结构等方法, 获得了当符号图的底图为简单图且没有2度点时, 其符号线图允许一个无零4-流的结果. 特别地, 如果符号图的底图为简单图且没有2度点和4度点, 那么它的符号线图允许一个无零3-流. 验证了对具有上述结构的符号图的符号线图, Bouchet 6-流猜想是成立的. 同时我们研究了连通的符号圈的符号线图是否是流允许的.

关键词：符号图符号线图无零流

NOWHERE-ZERO FLOWS ON THE SIGNED LINE GRAPHS OF SIGNED GRAPHS

HE Jing, WEN Chao, ZHANG Chao

School of Mathematics and Statistics, Guizhou University, Guiyang 550025, China

Abstract: This paper studies the nowhere-zero flow of the signed line graphs of signed graphs. By using mathematical induction and analyzing the structure of signed graphs, we obtain the result that when the underlying graphs of the signed graphs are simple and have no vertices of degree 2, the signed line graphs admit a nowhere-zero 4-flow. In particular, if the underlying graphs of the signed graphs are simple without vertices of degree 2 and 4, then the signed line graphs admit a nowhere-zero 3-flow. It is verified that for signed graphs with the aforementioned structures, their signed line graphs satisfy Bouchet's 6-flow conjecture. We also studied whether the signed line graph of the connected signed circle is flow-admissible.

Keywords: signed graphs signed line graph nowhere-zero flow

1 引言

无零流问题来源于Tutte ^[1]对于四色问题的研究. Tutte ^[2]证明了无桥的平面图可面$ k $-着色当且仅当该图允许一个无零$ k $-流. Jaeger ^[3]进一步指出, 如果图$ \; G\; $在一个可定向曲面上有一个面$ k $-可染的2-细胞嵌入, 那么$ \; G\; $就允许一个无零$ k $-流. 更进一步地, Bouchet ^[4]把Jaeger的研究推广到了图在不可定向曲面上的嵌入, 并且导出了有别于Tutte提出的无零流. 由于符号图可以用来表示图在不可定向曲面上的嵌入, 所以Bouchet引入的无零流问题可以转化为符号图的无零流问题. Bouchet ^[4]提出了著名的Bouchet 6-流猜想: 任意流允许的符号图都允许一个无零6-流. 它是符号图流理论中的核心猜想. 另外, Bouchet证明了一类符号Peterson图不允许无零5-流, 因此Bouchet猜想中无零6-流这个结论是最优的. 在同一篇文章中, Bouchet ^[4]证明了任意流允许的符号图都有无零216-流. 2021年, DeVos等人^[5]证明了任意流允许的符号图允许一个无零11-流, 这是目前关于Bouchet 6-流猜想最好的结论.

下面为了区分图与符号图, 我们统一将图称作普通图. 1933年Whitney ^[6]在考虑普通图的2-同构的文章中, 引入了线图. 随后线图受到广泛关注. 人们研究了线图的染色问题, 连通性以及平面性等问题. 在无零流问题的研究方面, Chen等人^[7]考虑了普通图的线图的无零流问题. 符号图最早由Harary ^[8]在研究社交网络的模型中引入. 对于符号图的符号线图, Belardo等人^[9]在2015年研究了符号图及其符号线图的拉普拉斯系数. 随后, Cavaleri等人^[10]给出了一个符号图是另一个符号图的符号线图的充分必要条件. 受到Chen等人的关于普通图的线图上无零流结论的启发, 本文主要考虑符号图的符号线图上的无零流问题, 证明了符号图的底图为简单图且没有2度点时, Bouchet 6-流猜想在它的符号线图上是成立的. 同时我们研究了连通的符号圈的符号线图是否是流允许的, 这说明当符号图存在2度点时, 它的符号线图可能不是流允许的.

2 相关定义

为了文章的完整性, 本节将给出符号图及其符号线图的定义. 如果没有特别指出, 本文研究的图都是有限的简单图. 我们首先给出符号图以及相关定义. 未给出定义的术语参考书籍[11].

定义2.1^[5] 符号图$ \; (G, \sigma)\; $由普通图$ \; G\; $和符号函数$ \; \sigma:E(G)\rightarrow \{+1, -1\} $组成, 其中$ G\; $是$ \; (G, \sigma)\; $的底图, $ E(G) $是$ G $的边集. 对一条边$ \; e\in E(G) $, 若$ \; \sigma(e)=+1 $, 则称这条边是正边; 否则称为负边. 对$ \; (G, \sigma)\; $的一个符号子图$ (H, \sigma\mid_{E(H)}) $, 为了方便, 在不产生歧义的情况下, 我们将$ (H, \sigma\mid_{E(H)}) $简记为$ (H, \sigma) $.

定义2.2^[5] 对符号图$ \; (G, \sigma) $, 它的符号子图$ (H, \sigma) $的符号是指该图中所有边符号的乘积, 即$ \sigma(H)=\prod_{e\in E(H)}\sigma(e) $.

定义2.3 圈是一个连通的2-正则图, 记作$ C_{n} $, 其中$ n $表示圈中的顶点数. 我们将$ (C_{n}, \sigma) $称为符号圈.

根据符号图中圈的正负, 可将符号图分为以下两类.

定义2.4^[12] 如果一个符号圈的符号是正的, 则称它是平衡的; 否则就称它是不平衡的. 如果一个符号图包含不平衡圈, 那么就称它是不平衡的, 否则它就是平衡的.

定义2.5^[5] 令$ \; U $是$ \; (G, \sigma)\; $顶点集的一个子集. 对$ \; U\; $做切换是指将端点分别在$ \; U\; $与$ V(G)\setminus U $中的边的符号取反. 如果一个符号图$ (G, \sigma) $可以通过一系列的切换转化为$ (G, \sigma') $, 则称$ (G, \sigma) $和$ (G, \sigma') $是切换等价的.

注2.1 切换并不改变符号圈的符号. 一个符号图$ \; (G, \sigma)\; $是平衡的当且仅当它可以通过一系列切换, 使得它的所有边都是正边. 对于无零流问题, 边全正的符号图等价于普通图.

为了给出符号图的无零流的定义, 我们首先介绍符号图的定向.

定义2.6^[5] 令$ \; (G, \sigma)\; $是一个符号图. 将符号图的一条边$ e=uv $看做两条半边$ \; h^e_{u}\; $和$ \; h^e_{v} $, 其中每条半边都和一个端点关联. 令$ \; H(G)\; $和$ \; H_{G}(u)\; $分别为$ \; (G, \sigma)\; $中所有半边构成的集合以及所有与顶点$ \; u\; $关联的半边构成的集合. 对$ \; h^e_v\in H(G) $, 用$ \; e_{h^e_v}\; $表示包含半边$ \; h^e_v\; $的边. $ \; (G, \sigma)\; $的一个定向是一个映射$ \; \tau:H(G)\rightarrow \{+1, -1 \} $, 使得对每一条半边$ \; h^e_{v}\in H(G) $, 有$ \; \tau(h^e_{v})\tau(h^e_{u})=-\sigma(e_{h^e_{v}}) $. 其中对$ \; h^e_{v}\in H(G) $, 如果$ \; h^e_{v}\; $的方向远离它的顶点, 那么$ \; \tau(h^e_{v})=1 $; 如果$ \; h^e_{v}\; $的方向指向它的顶点, 那么$ \; \tau(h^e_{v})=-1 $.

根据边的定向, 可以定义符号图的无零流.

定义2.7^[5] 设$ (G, \sigma) $是一个带有定向$ \; \tau\; $的符号图, 并令$ \; f:E(G)\rightarrow \mathbb{Z} $是一个映射. 如果对于每个顶点$ \; v \in V(G) $, 都有$ \; \sum_{h^e_{v}\in H_{G}(v)}\tau(h^{e}_{v})f(e_{h^e_{v}})=0\; $, 并且对任意一条边$ \; e\in E(G)\; $, 都满足$ \; 0< |f(e)|< k\; $, 则称$ \; (\tau, f) $为$ \; (G, \sigma)\; $的一个无零$ \; k $-流. 符号图$ \; (G, \sigma)\; $的流值$ \; \Phi((G, \sigma))\; $是使得$ \; (G, \sigma)\; $具有无零$ k $-流的最小整数$ \; k $. 如果存在一个整数$ \; k $, 使得$ \; (G, \sigma)\; $有无零$ \; k $-流, 则称$ \; (G, \sigma)\; $是流允许的.

注2.2 一方面, 对于边集为空集的符号图, 我们认为它是平衡的且允许有无零2-流. 另一方面, 如果两个符号图$ (G, \sigma) $和$ (G, \sigma') $切换等价, 那么$ (G, \sigma) $允许一个无零$ k $-流当且仅当$ (G, \sigma') $允许一个无零$ k $-流. 令$ (\tau, f) $是$ (G, \sigma) $上的一个无零$ k $-流. 对$ (G, \sigma) $中顶点子集$ V_{0}=\{v_{1}, v_{2}, \ldots, v_{t} \} $做切换后得到$ (G, \sigma') $, 以及$ (G, \sigma') $的一个定向$ \tau' $: 令$ H_{G}(V_{0})=\bigcup_{i=1}^t H_{G}(v_{i}) $. 对任意$ h^e_{v}\in H_{G}(V_{0}) $, 都有$ \tau'(h^e_{v})=-\tau(h^e_{v}) $; 对任意$ h^e_{v}\in H(G)\backslash H_{G}(v_{i}) $, 都有$ \tau'(h^e_{v})=\tau(h^e_{v}) $. 容易验证$ (\tau', f) $为$ (G, \sigma') $的一个无零$ k $-流.

对符号图$ (G, \sigma) $的一个无零$ \; k $-流$ (\tau, f) $, 令$ E_{0} $是$ (G, \sigma) $边集的一个子集. 对任意的$ e=uv\in E(G) $, 考虑如下一个定向$ \tau' $: 若$ e\in E_{0} $, 则$ \tau'(h^e_v)=-\tau(h^e_v) $; 若$ e\in E(G)\backslash E_{0} $, 则$ \tau'(h^e_v)=\tau(h^e_v) $. 以及一个映射$ f' $: 若$ e\in E_{0} $, 则$ f'(e)=-f(e) $; 若$ e\in E(G)\backslash E_{0} $, 则$ f'(e)=f(e) $. 这时得到的$ (\tau', f') $仍为$ (G, \sigma) $的一个无零$ k $-流. 所以$ (G, \sigma) $在定向$ \tau $下允许一个无零$ k $-流当且仅当它在定向$ \tau' $下允许一个无零$ k $-流. 因此边的定向不会对寻找无零流产生影响, 故我们将$ (\tau, f) $简记为$ f $.

在下面的引理中, Máčajová 和Škoviera ^[12]完全刻画了不平衡的2-边连通符号图.

引理2.1^[12] 一个不平衡的2-边连通符号图$ \; (G, \sigma)\; $是流允许的当且仅当它不存在一条边, 使得删掉这条边后得到的符号图是平衡的.

注2.3 一个符号圈$ (C_{n}, \sigma) $是流允许的当且仅当它是平衡的.

为了给出符号图对应的符号线图, 我们首先介绍普通图的线图.

定义2.8^[11] 一个普通图$ \; G\; $的线图$ \; L(G)\; $仍然是一个普通图, 其中$ \; V(L(G))=E(G) $, $ \; L(G)\; $中的两个顶点相邻当且仅当这两个点对应的边在$ \; G\; $中相邻.

下面给出符号图的符号线图的定义.

定义2.9^[13] 带有定向$ \; \tau\; $的符号图$ \; (G, \sigma)\; $的符号线图记作$ \; (L(G), \sigma_{L, \tau}) $, 其中$ \; L(G)\; $是$ \; G\; $的线图, 并且对$ \; (G, \sigma)\; $中的每个顶点$ \; v\; $和任意两条不同的半边$ \; h^{e_{1}}_{v}, h^{e_{2}}_{v}\in H_{G}(v) $, 有$ \; \sigma_{L, \tau}(e_{h^{e_{1}}_{v}}e_{h^{e_{2}}_{v}})=\tau(h^{e_{1}}_{v})\tau(h^{e_{2}}_{v}) $.

注2.4 对符号图$ (G, \sigma) $, 它的不同的定向得到的符号线图$ (L(G), \sigma_{L, \tau}) $与$ (L(G), \sigma_{L, \tau'}) $是切换等价的. 结合注$ 2.2 $可知, $ (L(G), \sigma_{L, \tau}) $允许一个无零$ k $-流当且仅当$ (L(G), \sigma_{L, \tau'}) $允许一个无零$ k $-流.

我们给出一个符号图及其符号线图的例子, 其中实线表示正边, 虚线表示负边.

例2.1 图 1给出了$ \; (K_{4}, \sigma) $以及它上面的一个定向. 其对应的符号线图如图 2所示, 其中$ \; V(L(K_{4}))=E(K_{4}) $.

图 1

$ (K_{4}, \sigma) $

图 2

$ (L(K_{4}), \sigma_{L, \tau}) $

3 主要定理及证明

对普通图的线图, 有下列结论.

引理3.1^[7] 令$ G $是无环的有限图, 其中$ \; G\; $允许有重边. 对$ \; G\; $中的任意一个顶点$ \; v $, 设$ \; G_{v}\; $是线图$ \; L(G)\; $中由$ \; E(v)\; $诱导的子图. 那么以下三个结论成立:

$ (1) $ 任意的$ \; G_{v}\; $都以一个完全图$ \; K_{d}\; $作为支撑子图, 其中$ \; d\; $是点$ \; v\; $在$ \; G\; $中的度;

$ (2) $ $ L(G)=\bigcup_{v\in V(G)}G_{v}\; $是$ \; G_{v}\; $的一个边不交的并;

$ (3) $ $ L(G)\; $中任意一个顶点$ \; e\; $只属于两个$ \; G_{v}\; $的点集.

对符号图$ \; (G, \sigma)\; $的符号线图$ \; (L(G), \sigma_{L, \tau}) $, 我们证明了类似于引理$ 3.1 $的结论.

定理3.1 令$ \; (G, \sigma) $是一个符号图, 其中$ \; G\; $是一个简单图. 对任意的顶点$ \; v\in V(G) $, 设$ (G_{v}, \sigma_{L, \tau})\; $是$ \; (L(G), \sigma_{L, \tau})\; $中由$ \; E(v)\; $诱导的符号子图. 那么以下三个结论成立:

$ (1) $ 任意的$ \; (G_{v}, \sigma_{L, \tau})\; $都是一个平衡的符号完全图$ \; (K_{d}, \sigma) $, 其中$ \; d\; $是点$ \; v\; $在$ \; (G, \sigma)\; $中的度;

$ (2) $ $ (L(G), \sigma_{L, \tau})=\bigcup_{v\in V(G)}(G_{v}, \sigma_{L, \tau})\; $是$ \; (G_{v}, \sigma_{L, \tau})\; $的一个边不交的并;

$ (3) $ $ (L(G), \sigma_{L, \tau})\; $中任意一个顶点$ \; e\; $只属于两个$ \; (G_{v}, \sigma_{L, \tau})\; $的点集.

证因为$ (L(G), \sigma_{L, \tau}) $的底图为线图$ L(G) $, 所以$ (2) $和$ (3) $是引理$ 3.1 $的直接推论. 由于$ G $是简单图, 根据引理$ 3.1 $的$ (1) $可知, $ (G_{v}, \sigma_{L, \tau}) $是一个符号完全图. 因此下面我们将证明, 任意的一个符号完全图$ (G_{v}, \sigma_{L, \tau}) $都是平衡的. 如果$ (G, \sigma) $中有1度点$ v_{1} $, 那么$ v_{1} $在其符号线图中对应的$ (G_{v_{1}}, \sigma_{L, \tau}) $是阶为1且平衡的完全图, 即只有一个孤立点的完全图. 下面考虑$ (G, \sigma) $中度大于等于3的点. 令$ \mathcal {C}_{k}=\{(C_{v}, \sigma_{L, \tau})\subseteq (G_{v}, \sigma_{L, \tau}): $符号圈$ (C_{v}, \sigma_{L, \tau}) $的长度为$ k\} $, 其中$ 3\leq k\leq d(v) $. 对$ k $用数学归纳法.

对任意的$ (C_{v}, \sigma_{L, \tau}) \in \mathcal {C}_{3} $, 它在$ (G, \sigma) $中与顶点$ v $相邻的半边对应的定向为图 3, 图 4, 图 5以及图 6这四种情形之一. 这时在点$ v $对应的符号完全图中, 任意的符号圈$ (C_{v}, \sigma_{L, \tau}) $中的负边数目均为偶数.

图 3 情形1

图 4 情形2

图 5 情形3

图 6 情形4

当$ k>3 $时, 假设命题对$ \mathcal {C}_{3}, \; \mathcal {C}_{4}, \; \cdots, \; \mathcal {C}_{k-1} $均成立, 现考虑$ \mathcal {C}_{k} $. 由于$ (G_{v}, \sigma_{L, \tau}) $是一个符号完全图, 故对任意的$ (C'_{v}, \sigma_{L, \tau}) \in \mathcal {C}_{k} $, $ (C'_{v}, \sigma_{L, \tau}) $中任意两点$ x, y $都相邻. 任取$ (C'_{v}, \sigma_{L, \tau}) $中的一条弦$ v_{1}v_{2} $, 其中$ v_{1}, v_{2}\in V(C'_{v}) $. 它将$ (C'_{v}, \sigma_{L, \tau}) $划分成两个长度都小于$ k $的符号圈$ (C'_{1}, \sigma_{L, \tau}) $和$ (C'_{2}, \sigma_{L, \tau}) $, 注意到$ E(C'_{v})=(E(C'_{1})\setminus v_{1}v_{2})\cup (E(C'_{2})\setminus v_{1}v_{2}) $且$ E(C'_{1})\cap E(C'_{2})=\{v_{1}v_{2} \} $. 由归纳假设可知, $ (C'_{1}, \sigma_{L, \tau}) $和$ (C'_{2}, \sigma_{L, \tau}) $都有偶数条负边. 因为

$ \begin{equation} \begin{split} \sigma_{L, \tau}(C'_{1})\sigma_{L, \tau}(C'_{2}) &=\bigg(\prod\limits_{e\in E(C'_{1})}\sigma_{L, \tau}(e)\bigg)\bigg(\prod\limits_{e\in E(C'_{2})}\sigma_{L, \tau}(e)\bigg)\\ &=\bigg(\prod\limits_{e\in E(C'_{1})\setminus v_{1}v_{2}}\sigma_{L, \tau}(e)\bigg)\bigg(\prod\limits_{e\in E(C'_{2})\setminus v_{1}v_{2}}\sigma_{L, \tau}(e)\bigg)(\sigma_{L, \tau}(v_{1}v_{2}))^{2}\\ &=\bigg(\prod\limits_{e\in E(C'_{1})\setminus v_{1}v_{2}}\sigma_{L, \tau}(e)\bigg)\bigg(\prod\limits_{e\in E(C'_{2})\setminus v_{1}v_{2}}\sigma_{L, \tau}(e)\bigg) \\ &\qquad \quad =\prod\limits_{e\in E(C'_{v})}\sigma_{L, \tau}(e)=\sigma_{L, \tau}(C'_{v}). \end{split} \end{equation} $

且$ \sigma_{L, \tau}(C'_{1})\sigma_{L, \tau}(C'_{2})=1 $, 所以$ \sigma_{L, \tau}(C'_{v})=1 $. 从而$ (C'_{v}, \sigma_{L, \tau}) $是平衡的. 因此, 任意的$ (G_{v}, \sigma_{L, \tau})\; $是平衡的. 证明完毕.

例3.1 在例$ \; 2.1\; $中, 顶点$ \; v_{1}\; $在$ (L(K_{4}), \sigma_{L, \tau}) $中对应的完全图$ \; (G_{v_{1}}, \sigma_{L, \tau})\; $, 如图 7中用蓝线表示的部分, 其中$ \; V(G_{v_1})=\{ e_{1}, e_{4}, e_{6} \} $; $ v_{2} $对应的完全图, 如图 7中红线表示的部分, 其中$ V(G_{v_2})=\{e_{1}, e_{2}, e_{5} \} $, 它们都是平衡的.

图 7

$ (G_{v_{1}}, \sigma_{L, \tau}) $

Máčajová 和Rollová ^[14]刻画了平衡的符号完全图的流值.

引理3.2^[14] 令$ G=(K_{n}, \Sigma) $是具有个$ n $顶点的平衡的符号完全图, 其中$ n\geq 5 $. 如果$ n $是奇数, 那么$ \Phi(G)=2 $; 否则$ \Phi(G)=3 $.

注3.1 本文考虑的图均为简单图, 不存在重边和环. 当$ n=1 $时, $ (K_{1}, \sigma) $是平衡的且允许一个无零2-流. 当$ n=3 $时, 一个平衡的$ (K_{3}, \sigma) $允许一个无零2-流. 当$ n=4 $时, 由于平衡的符号图与边全正的符号图切换等价, 所以我们只考虑边全正的符号完全图$ (K_{4}, \sigma) $. 因为三正则图允许一个无零3-流当且仅当它是二部图, 所以边全正的$ (K_{4}, \sigma) $没有无零3-流. 但我们可以在$ (K_{4}, \sigma) $上面找到一个无零4-流, 如图 8, 也即所有平衡的$ (K_{4}, \sigma) $都允许一个无零4-流.

图 8 $ (K_{4}, \sigma) $上的一个4-NZF

由定理3.1和引理3.2, 可以得到关于符号图的符号线图的无零流的结论.

定理3.2 令$ (G, \sigma) $是一个符号图, 其中$ G $是一个简单图. 如果$ (G, \sigma) $中没有2度点, 那么$ (L(G), \sigma_{L, \tau}) $允许一个无零4-流. 进一步地, 如果$ (G, \sigma) $中没有2度点和4度点, 那么$ (L(G), \sigma_{L, \tau}) $允许一个无零3-流.

证因为$ (G, \sigma) $中没有2度点, 由定理$ 3.1 $中的$ (1) $可知, 对任意的$ v\in V(G) $, $ v $在$ (L(G), \sigma_{L, \tau}) $中对应的符号完全图$ (G_{v}, \sigma_{L, \tau}) $是平衡的, 且$ (G_{v}, \sigma_{L, \tau}) $中不存在阶为2的符号完全图. 结合引理$ 3.2 $以及$ (K_{4}, \sigma_{L, \tau}) $不允许无零3-流, 但允许一个无零4-流可知, $ (G_{v}, \sigma_{L, \tau}) $允许一个无零4-流$ f_{v} $. 由于$ \bigcup_{v\in V(G)}(G_{v}, \sigma_{L, \tau}) $是一个边不交的并, 且$ (L(G), \sigma_{L, \tau})=\bigcup_{v\in V(G)}(G_{v}, \sigma_{L, \tau}) $, 所以$ (L(G), \sigma_{L, \tau}) $允许一个无零4-流$ \sum_{v\in V(G)}f_{v} $.

进一步地, 因为$ (G, \sigma) $中没有2度点和4度点, 由定理$ 3.1 $可知, $ (G_{v}, \sigma_{L, \tau}) $中不存在阶为2和4的符号完全图. 此时, 任意的$ (G_{v}, \sigma_{L, \tau}) $都允许一个无零3-流, 所以$ (L(G), \sigma_{L, \tau}) $允许一个无零3-流. 证明完毕.

上述定理说明, 只要符号图不含2度点, 那么它的符号线图就一定是流允许的. 下面我们讨论符号图具有2度点的情况. 比如路径$ (P_{n}, \sigma) $, 它的符号线图不是流允许的, 因为其符号线图具有1度点. 进一步地, 我们研究了符号圈的符号线图. 下面的结论说明, 对于符号圈的符号线图, 其符号线图可能是流允许的, 也可能不是流允许的.

定理3.3 对符号圈$ (C_{n}, \sigma) $, 其中$ n\in \mathbb{Z} $, 有以下两个结论成立:

(1) 当$ n $为奇数时, 如果$ (C_{n}, \sigma) $是流允许的, 那么它的符号线图不是流允许的; 如果$ (C_{n}, \sigma) $不是流允许的, 那么它的符号线图是流允许的.

(2) 当$ n $为偶数时, 如果$ (C_{n}, \sigma) $是流允许的, 那么它的符号线图是流允许的; 如果$ (C_{n}, \sigma) $不是流允许的, 那么它的符号线图不是流允许的.

证令$ V(C_{n})=\{v_{1}, v_{2}, \cdots, v_{n} \} $. 由定义可知, $ (C_{n}, \sigma) $的符号线图仍为一个符号圈.

(1) 如果$ (C_{n}, \sigma) $是流允许的, 那么$ (C_{n}, \sigma) $中有偶数条负边, 这是因为$ (C_{n}, \sigma) $是流允许的当且仅当它是平衡的. 我们对$ (C_{n}, \sigma) $做切换使得它中所有边符号都是正的, 记作$ (C_{n}, \sigma') $. 由于对同一个符号图, 不同的定向得到的符号线图是切换等价的, 因此我们假设$ (C_{n}, \sigma') $的定向$ \tau $如下: 对边$ e_{i}=v_{i}v_{i+1} $, 其中$ i\in [1, n-1] $, 我们令$ h^{e_{i}}_{v_{i}} $的定向为远离端点$ v_{i} $, $ h^{e_{i}}_{v_{i+1}} $的定向为指向端点$ v_{i+1} $. 且对于边$ e_{n}=v_{n}v_{1} $, $ h^{e_{n}}_{v_{n}} $的定向为远离端点$ v_{n} $, $ h^{e_{n}}_{v_{1}} $的定向为指向端点$ v_{1} $. 由符号线图的定义可知, $ (L(C_{n}), \sigma'_{L, \tau}) $中每条边都是负边. 结合$ n $是奇数, 可知$ (L(C_{n}), \sigma'_{L, \tau}) $是不平衡的. 从而$ (L(C_{n}), \sigma'_{L, \tau}) $不是流允许的. 由注$ 2.4 $可知, $ (L(C_{n}), \sigma_{L, \tau}) $不是流允许的.

如果$ (C_{n}, \sigma) $不是流允许的, 那么$ (C_{n}, \sigma) $中有奇数条负边. 我们将$ (C_{n}, \sigma) $做切换使得它只有一条负边$ e_{1}=v_{n}v_{1} $, 记作$ (C_{n}, \sigma') $. 假设$ (C_{n}, \sigma') $的定向$ \tau $如下: $ \tau(h^{e_{i}}_{v_{i}})=1, \tau(h^{e_{i}}_{v_{i+1}})=-1 $.其中$ i\in [1, n-1] $, 且$ \tau(h^{e_{n}}_{v_{n}})=\tau(h^{e_{n}}_{v_{1}})=1 $. 由符号线图的定义可知, $ (L(C_{n}), \sigma'_{L, \tau}) $中只有$ e_{n}e_{1} $为正边, 其余边均为负边. 从而$ (L(C_{n}), \sigma'_{L, \tau}) $有偶数条负边. 所以$ (L(C_{n}), \sigma'_{L, \tau}) $是平衡的. 因此$ (L(C_{n}), \sigma'_{L, \tau}) $是流允许的. 结合注$ 2.4 $可知, $ (L(C_{n}), \sigma_{L, \tau}) $是流允许的.

(2) 如果$ (C_{n}, \sigma) $是流允许的, 那么$ (C_{n}, \sigma) $中有偶数条负边. 我们对$ (C_{n}, \sigma) $做切换使得它中所有边符号都是正的, 记作$ (C_{n}, \sigma') $. 假设$ (C_{n}, \sigma') $的定向$ \tau $如下: $ \tau(h^{e_{i}}_{v_{i}})=1, \tau(h^{e_{i}}_{v_{i+1}})=-1 $.其中$ i\in [1, n-1] $, 且$ \tau(h^{e_{n}}_{v_{n}})=1, \tau(h^{e_{n}}_{v_{1}})=-1 $. 由符号线图的定义可知, $ (L(C_{n}), \sigma'_{L, \tau}) $中每条边都是负边, 结合$ n $是偶数, 可知$ (L(C_{n}), \sigma'_{L, \tau}) $是平衡的. 因此$ (L(C_{n}), \sigma'_{L, \tau}) $是流允许的. 结合注$ 2.4 $可知, $ (L(C_{n}), \sigma_{L, \tau}) $是流允许的.

如果$ (C_{n}, \sigma) $不是流允许的, 那么$ (C_{n}, \sigma) $中有奇数条负边. 我们对$ (C_{n}, \sigma) $做切换使得它只有一条负边$ e_{n}=v_{n}v_{1} $, 记作$ (C_{n}, \sigma') $. 假设$ (C_{n}, \sigma') $的定向$ \tau $如下: $ \tau(h^{e_{i}}_{v_{i}})=1, \tau(h^{e_{i}}_{v_{i+1}})=-1 $.其中$ i\in [1, n-1] $, 且$ \tau(h^{e_{n}}_{v_{n}})=\tau(h^{e_{n}}_{v_{1}})=1 $. 由符号线图的定义可知, $ (L(C_{n}), \sigma'_{L, \tau}) $中只有$ e_{n}e_{1} $为正边, 其余边均为负边. 所以$ (L(C_{n}), \sigma'_{L, \tau}) $有奇数条负边, 即$ (L(C_{n}), \sigma'_{L, \tau}) $是不平衡的. 因此$ (L(C_{n}), \sigma'_{L, \tau}) $不是流允许的. 结合注$ 2.4 $可知, $ (L(C_{n}), \sigma_{L, \tau}) $不是流允许的. 证明完毕.

问题3.1 能否找到其它包含2度点的符号图, 其符号线图不是流允许的? 进一步地, 能否给出符号图的符号线图是流允许的充分必要条件?

参考文献

[1]	Tutte W T. On the imbedding of linear graphs in surfaces[J]. Proc. London Math. Soc., 1949, 2(51): 474–483.

[2]	Tutte W T. A contribution to the theory of chromatic polynomials[J]. Canad. J. Math., 1954, 6: 80–91. DOI:10.4153/CJM-1954-010-9

[3]	Jaeger F. Nowhere-zero flow problems[A]. Beineke L W, Wilson R J. Selected Topics in Graph Theory (Vol. 3)[C]. London: Academic Press, 1988: 71–95.

[4]	Bouchet A. Nowhere-zero integral flows on bidirected graph[J]. J. Combin. Theory Ser. B, 1983, 34(3): 279–292. DOI:10.1016/0095-8956(83)90041-2

[5]	DeVos M, Li Jiaao, Lu You, et al. Flows on flow-admissible signed graphs[J]. J. Combin. Theory Ser. B, 2021, 149: 198–221. DOI:10.1016/j.jctb.2020.04.008

[6]	Whitney H. 2-isomorphic graphs[J]. Amer. J. Math., 1933, 55(1): 245–254.

[7]	Chen Zhihong, Lai Hongjian, Lai Hongyuan. Nowhere zero flows in line graphs[J]. Discrete Math., 2001, 230(1-3): 133–141. DOI:10.1016/S0012-365X(00)00076-5

[8]	Harary F. On the notion of balance of a signed graph[J]. Mich. Math. J., 1953-1954, 2(2): 143–146.

[9]	Belardo F, Simić S K. On the Laplacian coefficients of signed graphs[J]. Linear Algebra Appl., 2015, 475: 94–113. DOI:10.1016/j.laa.2015.02.007

[10]	Cavaleri M, D'Angeli D, Donno A. Characterizations of line graphs in signed and gain graphs[J]. Eur. J. Comb., 2022, 102: 103479. DOI:10.1016/j.ejc.2021.103479

[11]	Bondy J A, Murty U S R. Graph theory (Second edition)[M]. New York: Springer, 2008.

[12]	Máčajová E, Škoviera M. Nowhere-zero flows on signed Eulerian graphs[J]. SIAM J. Discrete Math., 2017, 31(3): 1937–1952. DOI:10.1137/16M1080586

[13]	Zhang Li, Lu You, Luo Rong, et al. Edge coloring of signed graphs[J]. Discrete Appl. Math., 2020, 282: 234–242. DOI:10.1016/j.dam.2019.12.004

[14]	Máčajová E, Rollová E. Nowhere-zero flows on signed complete and complete bipartite graphs[J]. J. Graph Theory, 2015, 78(2): 108–130. DOI:10.1002/jgt.21793