Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → -1,1 satisfying ${\sum }_{e\in E_G\left(v\right)}x\left(e\right)\le 1$ for every v ∈ V(G), where $E_G\left(v\right)=uv\in E\left(G\right)\left|u\in V\right(G)$. The maximum of the values of ${\sum }_{e\in E\left(G\right)}x\left(e\right)$, taken over all signed matchings x, is called the signed matching number and is denoted by β’₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β’₁(G) for general graphs....

We investigate which switching classes do not contain a bipartite graph. Our final aim is a characterization by means of a set of critically non-bipartite graphs: they do not have a bipartite switch, but every induced proper subgraph does. In addition to the odd cycles, we list a number of exceptional cases and prove that these are indeed critically non-bipartite. Finally, we give a number of structural results towards proving the fact that we have indeed found them all. The search for critically...

In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.

A signed graph $\Gamma$ is a graph whose edges are labeled by signs. If $\Gamma$ has $n$ vertices, its spectral radius is the number $\rho \left(\Gamma \right):=max\left\{\right|{\lambda }_i\left(\Gamma \right)|:1\le i\le n\}$, where ${\lambda }_1\left(\Gamma \right)\ge \cdots \ge {\lambda }_n\left(\Gamma \right)$ are the eigenvalues of the signed adjacency matrix $A\left(\Gamma \right)$. Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes ${𝔘}_n$ and ${𝔅}_n$ of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.

Given a graph G = (V,E) of order n and a finite abelian group H = (H,+) of order n, a bijection f of V onto H is called a vertex H-labeling of G. Let g(e) ≡ (f(u)+f(v)) mod H for each edge e = u,v in E induce an edge H-labeling of G. Then, the sum $Hva{l}_f\left(G\right)\equiv {\sum }_{e\in E}g\left(e\right)modH$ is called the H-value of G relative to f and the set HvalS(G) of all H-values of G over all possible vertex H-labelings is called the H-value set of G. Theorems determining HvalS(G) for given H and G are obtained.