Regular codes in regular graphs are difficult

DOI10.1016/0012-365X(94)90026-4zbMath0821.68096WikidataQ127015947 ScholiaQ127015947MaRDI QIDQ1336698

Jan Kratochvíl

Publication date: 3 November 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

planar cubic graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

1-perfect codes in Sierpiński graphs ⋮ A Taxonomy of Perfect Domination ⋮ An almost complete description of perfect codes in direct products of cycles ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Locally injective \(k\)-colourings of planar graphs ⋮ Dominating induced matchings in graphs without a skew star ⋮ Perfect codes in direct products of cycles-a complete characterization ⋮ On the number of 2-packings in a connected graph ⋮ Fixed-parameter complexity of \(\lambda\)-labelings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Efficient edge domination in regular graphs ⋮ Algorithms for unipolar and generalized split graphs ⋮ On the Complexity of Planar Covering of Small Graphs ⋮ Dominating Induced Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Perfect codes and regular partitions in graphs and groups
• On existence theorems
• Characterizations of strongly chordal graphs
• Relations between packing and covering numbers of a tree
• The NP-completeness of the bandwidth minimization problem
• Perfect codes in graphs
• The NP-Completeness of Edge-Coloring
• Determining the thickness of graphs is NP-hard
• A new 5‐arc‐transitive cubic graph

This page was built for publication: Regular codes in regular graphs are difficult