Premium
Characterizing subgraphs of Hamming graphs
Author(s) -
Klavžar Sandi,
Peterin Iztok
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20084
Subject(s) - hamming graph , combinatorics , mathematics , cograph , discrete mathematics , induced subgraph , graph , hamming code , chordal graph , 1 planar graph , vertex (graph theory) , algorithm , block code , decoding methods
Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E ( G ) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u , υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005