Signed graphs whose signed Colin de Verdière parameter is two

Publication date 11 December 2015

Abstract: A signed graph is a pair

(G, S i g m a)

, where

G = (V, E)

is a graph (in which parallel edges are permitted, but loops are not) with

V = 1, ..., n

and

S i g m a s u b s e t e q E

. The edges in

S i g m a

are called odd and the other edges even. By

S (G, S i g m a)

we denote the set of all symmetric

n i m e s n

matrices

A = [a_{i, j}]

with

a_{i, j} < 0

if

i

and

j

are connected by only even edges,

a_{i, j} > 0

if

i

and

j

are connected by only odd edges,

a_{i, j} i n m a t h b b R

if

i

and

j

are connected by both even and odd edges,

a_{i, j} = 0

if

i o t = j

and

i

and

j

are non-adjacent, and

a_{i, i} i n m a t h b b R

for all vertices

i

. The parameter

u (G, S i g m a)

of a signed graph

(G, S i g m a)

is the largest nullity of any positive semidefinite matrix

A i n S (G, S i g m a)

that has the Strong Arnold Property. By

K_{3}^{=}

we denote the signed graph obtained from

(K_{3}, e m p t y s e t)

by adding to each even edge an odd edge in parallel. In this paper, we prove that a signed graph

(G, S i g m a)

has

u (G, S i g m a) l e q 2

if and only if

(G, S i g m a)

has no minor isomorphic to

(K_{4}, E (K_{4}))

or

K_{3}^{=}

.

Recommendations

Cited in

(2)

This page was built for publication: Signed graphs whose signed Colin de Verdière parameter is two