The maximum independent sets of de Bruijn graphs of diameter 3

zbMATH Open1229.05217arXiv0905.3820MaRDI QIDQ640456FDOQ640456

María Angélica Cueto, Enrique A. Tobis, Dustin Cartwright

Publication date: 18 October 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The nodes of the de Bruijn graph B(d,3) consist of all strings of length 3, taken from an alphabet of size d, with edges between words which are distinct substrings of a word of length 4. We give an inductive characterization of the maximum independent sets of the de Bruijn graphs B(d,3) and for the de Bruijn graph of diameter three with loops removed, for arbitrary alphabet size. We derive a recurrence relation and an exponential generating function for their number. This recurrence allows us to construct exponentially many comma-free codes of length 3 with maximal cardinality.

Full work available at URL: https://arxiv.org/abs/0905.3820

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 3878839
• Independence number of de Bruijn graphs
• scientific article; zbMATH DE number 1874376
• scientific article; zbMATH DE number 2050882
• Covering the de Bruijn graph

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Cited In (8)

• On the diameter of the generalized undirected de Bruijn graphsUG_B(n,m),n²<m≤n³
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Covering the de Bruijn graph
• Title not available (Why is that?)
• Independence number of de Bruijn graphs
• Independently prescribable sets of n-letter words

Uses Software

• CoCoA

This page was built for publication: The maximum independent sets of de Bruijn graphs of diameter 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640456)