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.
Caramia, M., Apollonio, N. (2010). A local structure result for line graphs of strong quasi-graphical matrices.
A local structure result for line graphs of strong quasi-graphical matrices
CARAMIA, MASSIMILIANO;
2010-03-24
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
RR_08_09Apollonio_caramia.pdf
accesso aperto
Dimensione
285.95 kB
Formato
Adobe PDF
|
285.95 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.