Induced embeddings into Hamming graphs

DOI10.4230/LIPICS.MFCS.2017.28zbMATH Open1441.68193OpenAlexW2771182029MaRDI QIDQ5111242FDOQ5111242

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/

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

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)

Cites Work

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

Cited In (3)

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

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)