Geodesic
Minimum rank of edge subdivisions of graphs
The electronic journal of linear algebra, Tome 18 (2009), pp. 530-563.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Let F be a field, let G be an undirected graph on n vertices, and let $S(F, G)$ be the set of all F -valued symmetric n $\times n$ matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The minimum rank of G over F is defined to be $mr(F, G) = $minrank A | A $\in S(F, G)$. The problem of finding the minimum rank (maximum nullity) of edge subdivisions of a given graph G is investigated. Is is shown that if an edge is adjacent to a vertex of degree 1 or 2, its maximum nullity is unchanged upon subdividing the edge. This enables us to reduce the problem of finding the minimum rank of any graph obtained from G by subdividing edges to finding the minimum rank of those graphs obtained from G by subdividing each edge at most once. The graph obtained by subdividing each edge of G once is called its subdivision graph and is denoted by a G. It is shown that its maximum nullity is an upper bound for the maximum nullity of any graph obtained from G by subdividing edges. It is also shown that the minimum rank of a Goften depends only upon the number of vertices of G. In conclusion, some illustrative examples and open questions are presented.
Classification : 05C50, 15A03, 15B57
Keywords: combinatorial matrix theory, edge subdivision, graph, maximum nullity, minimum rank, symmetric 
@article{ELA_2009__18__a16,
     author = {Barrett, Wayne and Bowcutt, Ryan and Cutler, Mark and Gibelyou, Seth and Owens, Kayla},
     title = {Minimum rank of edge subdivisions of graphs},
     journal = {The electronic journal of linear algebra},
     pages = {530--563},
     publisher = {mathdoc},
     volume = {18},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2009__18__a16/}
}
TY  - JOUR
AU  - Barrett, Wayne
AU  - Bowcutt, Ryan
AU  - Cutler, Mark
AU  - Gibelyou, Seth
AU  - Owens, Kayla
TI  - Minimum rank of edge subdivisions of graphs
JO  - The electronic journal of linear algebra
PY  - 2009
SP  - 530
EP  - 563
VL  - 18
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2009__18__a16/
LA  - en
ID  - ELA_2009__18__a16
ER  - 
%0 Journal Article
%A Barrett, Wayne
%A Bowcutt, Ryan
%A Cutler, Mark
%A Gibelyou, Seth
%A Owens, Kayla
%T Minimum rank of edge subdivisions of graphs
%J The electronic journal of linear algebra
%D 2009
%P 530-563
%V 18
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2009__18__a16/
%G en
%F ELA_2009__18__a16
Barrett, Wayne; Bowcutt, Ryan; Cutler, Mark; Gibelyou, Seth; Owens, Kayla. Minimum rank of edge subdivisions of graphs. The electronic journal of linear algebra, Tome 18 (2009), pp. 530-563. http://geodesic.mathdoc.fr/item/ELA_2009__18__a16/