Quasi near ideal odd st-walk matrices

NASINI, GRACIELA; TOLOMEI, PAOLA

Buenos Aires.

Workshop; VI ALIO/EURO Workshop on Applied Combinatorial Optimization; 2008

Facultad de Cs. Exactas y Naturales, Universidad de Buenos Aires.

Near-ideal matrices are defined following a similar concept due to Shepherd for near-perfect graphs. For these matrices, every minor obtained by deletion is ideal, and every nonideal minor obtained by contraction has the same covering number as the original matrix. General 0, 1 matrices satisfying these two last properties are called quasi near-ideal matrices. A conjecture of Argiroffo et al., establishes that every quasi near-ideal matrix is near-ideal. In this work we prove that this conjecture holds for the family of odd st-walk matrices in signed graphs.