## Abstract

A signed graph is a pair (G,Σ), where G=(V,E) is a graph (in which parallel edges are permitted, but loops are not) with V={1,…,n} and Σ⊆E. The edges in Σ are called odd and the other edges of E even. If there are parallel edges, then only two edges in each parallel class are permitted, one of which is even and one of which is odd. By S(G,Σ) we denote the set of all symmetric n×n matrices A=[a_{i,j}] with a_{i,j}<0 if i and j are connected by an even edge, a_{i,j}>0 if i and j are connected by an odd edge, a_{i,j}∈R if i and j are connected by both an even and an odd edge, a_{i,j}=0 if i≠j and i and j are non-adjacent, and a_{i,i}∈R for all vertices i. The maximum nullity M(G,Σ) of a signed graph (G,Σ) is the maximum nullity attained by any A∈S(G,Σ). Arav et al. gave a combinatorial characterization of 2-connected signed graphs (G,Σ) with M(G,Σ)=2. In this paper, we give a complete combinatorial characterization of the signed graphs (G,Σ) with M(G,Σ)=2.

Original language | English |
---|---|

Pages (from-to) | 29-47 |

Number of pages | 19 |

Journal | Linear Algebra and Its Applications |

Volume | 675 |

DOIs | |

Publication status | Published - 2023 |

### Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-careOtherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

## Keywords

- Nullity
- Signed graph
- Symmetric