Induced embeddings into Hamming graphs

DOI10.4230/LIPICS.MFCS.2017.28MaRDI QIDQ5111242zbMATHOpenAlexFDO

Authors Martin Milanič, Peter Mursic, Marcelo Mydlarz

Publication date 26 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8128/pdf/LIPIcs-MFCS-2017-28.pdf/

zbMATH Keywords

NP-completenessHamming graphchordal graphgridline graphinduced embedding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Isometric embeddings in Hamming graphs
• On the complexity of recognizing Hamming graphs and related classes of graphs
• Embeddings of graphs in Euclidean spaces
• Characterizing subgraphs of Hamming graphs
• scientific article; zbMATH DE number 653263

Cites work

• scientific article; zbMATH DE number 1186102 (Why is no real title available?)
• scientific article; zbMATH DE number 3663187 (Why is no real title available?)
• scientific article; zbMATH DE number 3717345 (Why is no real title available?)
• scientific article; zbMATH DE number 3747193 (Why is no real title available?)
• scientific article; zbMATH DE number 3477201 (Why is no real title available?)
• scientific article; zbMATH DE number 3477221 (Why is no real title available?)
• scientific article; zbMATH DE number 3563183 (Why is no real title available?)
• scientific article; zbMATH DE number 1107726 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 969975 (Why is no real title available?)
• A characterization of cubic lattice graphs
• A note on the exceptional graph of the cubic lattice graph characterization
• A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph
• An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
• Characterizing subgraphs of Hamming graphs
• Complexity of dimension three and some related edge-covering characteristics of graphs
• Cubical graphs and cubical dimensions
• Duchet-type theorems for powers of HHD-free graphs
• Finding large independent sets in line of sight networks
• Further characterizations of cubic lattice graphs
• Graph Classes: A Survey
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• Hamming dimension of a graph-the case of Sierpiński graphs
• LexBFS-orderings and powers of chordal graphs
• Lexbfs-orderings and powers of hhd-free graphs^∗
• Line graphs of hypergraphs. I
• Line-of-Sight Networks
• Note on “A characterization of cubic lattice graphs”
• On Isometric Embeddings of Graphs
• On a product dimension of bipartite graphs
• On a product dimension of graphs
• On induced and isometric embeddings of graphs into the strong product of paths
• On the semi-perfect elimination
• Powers of hhd-free graphs^∗
• Product dimension of forests and bounded treewidth graphs
• Queens graphs
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs
• Representations of graphs modulo \(n\)
• Snarks without small cycles
• The NP-Completeness of Edge-Coloring
• The lattice dimension of a graph
• The square of a block graph
• The strong isometric dimension of finite reflexive graphs
• The strong perfect graph theorem
• The uniqueness of the cubic lattice graph
• Wings and perfect graphs

Cited in

(3)

• Dynamic programming optimization in line of sight networks
• Independent sets in Line of Sight networks
• Classification of nonorientable regular embeddings of Hamming graphs

This page was built for publication: Induced embeddings into Hamming graphs

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