平衡子欧拉符号图及符号线图

符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$.

Balanced Subeulerian Signed Graphs and Signed Line Graphs

A signed graph $S=\left(S^u, \sigma\right)$ has an underlying graph $S^u$ and a function $\sigma: E\left(S^u\right) \longrightarrow\{+,-\}$. Let $E^{-}(S)$ denote the set of negative edges of $S$. Then $S$ is eulerian signed graph (or subeulerian signed graph, or balanced eulerian signed graph, respectively) if $S^{u}$ is eulerian (or subeulerian, or eulerian and $|E^{-}(S)|$ is even, respectively). We say that $S$ is balanced subeulerian signed graph if there exists a balanced eulerian signed graph $S''$ such that $S''$ is spanned by $S$. The signed line graph $L(S)$ of a signed graph $S$ is a signed graph with the vertices of $L(S)$ being the edges of $S$, where an edge $e_i e_j$ is in $ L(S)$ if and only if the edges $e_i$ and $e_j$ of $S$ have a vertex in common in $S$ such that an edge $e_i e_j$ in $L(S)$ is negative if and only if both edges $e_i$ and $e_j$ are negative in $S$. In this paper, two families of signed graphs $\mathcal{S}$ and $\mathcal{S}''$ are identified, which are applied to characterize balanced subeulerian signed graphs and balanced subeulerian signed line graphs. In particular, it is proved that a signed graph $S$ is balanced subeulerian if and only if $S\not\in \mathcal{S}$, and that a signed line graph of signed graph $S$ is balanced subeulerian if and only if $S\not\in \mathcal{S}''$.