𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterizing subgraphs of Hamming graphs

✍ Scribed by Sandi Klavžar; Iztok Peterin

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
117 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Characterizing path graphs by forbidden
Characterizing path graphs by forbidden induced subgraphs
✍ Benjamin Lévêque; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009

An induced subgraph characterization of
An induced subgraph characterization of domination perfect graphs
✍ Igor E. Zvervich; Vadim E. Zverovich 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 800 KB

## Abstract Let γ(__G__) ι(__G__) be the domination number and independent domination number of a graph (__G__), respectively. A graph (__G__) is called domination perfect if γ(__H__) = ι(__H__), for every induced subgraph __H__ of (__G__). There are many results giving a partial characterization o

Retracts of Infinite Hamming Graphs
Retracts of Infinite Hamming Graphs
✍ Marc Chastand 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A Hamming graph is a Cartesian product of complete graphs. We show that (finite or infinite) quasi-median graphs, which are a generalization of median graphs, are exactly the retracts of Hamming graphs. This generalizes a result of Bandelt (1984,

Subgraphs of graphs, I
Subgraphs of graphs, I
✍ Paul A. Catlin 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 737 KB

&et G' and H aphs on p vertices. We give a suffictent Londition, based f the verrices of G and the maximum degree of t w vertices of ff' for Throughout this paper, all graphs considered are finite and simpl;. The C&~WP of a vertex v in the graph G is denoted deg<; (v). The vertex set of G is dencted

A semi-induced subgraph characterization
A semi-induced subgraph characterization of upper domination perfect graphs
✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl