A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.
@article{10_37236_6701,
author = {Monique Laurent and Matteo Seminaroti and Shin-ichi Tanigawa},
title = {A structural characterization for certifying {Robinsonian} matrices},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {2},
doi = {10.37236/6701},
zbl = {1361.05110},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6701/}
}
TY - JOUR
AU - Monique Laurent
AU - Matteo Seminaroti
AU - Shin-ichi Tanigawa
TI - A structural characterization for certifying Robinsonian matrices
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6701/
DO - 10.37236/6701
ID - 10_37236_6701
ER -
%0 Journal Article
%A Monique Laurent
%A Matteo Seminaroti
%A Shin-ichi Tanigawa
%T A structural characterization for certifying Robinsonian matrices
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6701/
%R 10.37236/6701
%F 10_37236_6701
Monique Laurent; Matteo Seminaroti; Shin-ichi Tanigawa. A structural characterization for certifying Robinsonian matrices. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/6701
