Balanced Subeulerian Signed Graphs and Signed Line Graphs

Abstract:

      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}'$.