A local structure result for line graphs of strong quasi-graphical matrices
Massimiliano Caramia, Nicola Apollonio · Cineca Institutional Research Information System (Tor Vergata University) · 2010
Let A be a binary matrix which generates a regular matroid with no M*(K3;3) minor and let L(A) be the line graph of A, namely, the graph whose vertices correspond to the columns of A and where there is an edge between two vertices if the supports of the corresponding columns intersect. In this paper we prove that every vertex of L(A) has at most four neighbors on every hole of L(A). This result generalizes a local structure result proved by Golumbic and Jamison [Golumbic and Jamison, J. Comb. Theory Ser. B 38, 1985] for Edge-Path-Tree graphs, that is line graphs of network matrices reduced modulo 2.