Let Bn be the binary de Bruijn digraph of order n andW the quotient set of the set of vertices of Bn with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that .v; u/ is an arc of Bn. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.

Perfect matchings of a graph associated with a binary de Bruijn digraph

KRAMER, ALPAR VAJK;LASTARIA, FEDERICO GIAMPIERO;ZAGAGLIA, NORMA
2010-01-01

Abstract

Let Bn be the binary de Bruijn digraph of order n andW the quotient set of the set of vertices of Bn with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that .v; u/ is an arc of Bn. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.
File in questo prodotto:
File Dimensione Formato  
Kramer_Lastaria_Zagaglia.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 246.88 kB
Formato Adobe PDF
246.88 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/11311/572154
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact