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.
24-mar-2010
en
line graphs
regular matrices
wheels
Caramia, M., Apollonio, N. (2010). A local structure result for line graphs of strong quasi-graphical matrices.
Caramia, M; Apollonio, N
Altro
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/1229
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact