๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the Complexity of Recognizing Hamming Graphs and Related Classes of Graphs

โœ Scribed by Wilfried Imrich; Sandi Klavzar

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
287 KB
Volume
17
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On recognizing graphs by numbers of homo
On recognizing graphs by numbers of homomorphisms
โœ Zdenฤ›k Dvoล™รกk ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 129 KB

## Abstract Let hom (__G, H__) be the number of homomorphisms from a graph __G__ to a graph __H__. A wellโ€known result of Lovรกsz states that the function hom (ยท, __H__) from all graphs uniquely determines the graph __H__ up to isomorphism. We study this function restricted to smaller classes of gra

On the structure of hereditary classes o
On the structure of hereditary classes of graphs
โœ Edward R. Scheinerman ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 333 KB ๐Ÿ‘ 1 views

A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have "composition sequences" and we show that this concept is equivalent to a notion of "amalgamation" which generalizes disjoint union of graphs. We also discuss how general

The complexity of the matching-cut probl
The complexity of the matching-cut problem for planar graphs and other graph classes
โœ Paul Bonsma ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 247 KB

## Abstract The Matchingโ€Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$โ€complete when restricted to graphs with maximum deg

Mixing properties of the Swendsenโ€“Wang p
Mixing properties of the Swendsenโ€“Wang process on classes of graphs
โœ Colin Cooper; Alan M. Frieze ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 194 KB ๐Ÿ‘ 2 views

We consider the mixing properties of the widely used Swendsen-Wang process for the Markov chain Monte Carlo estimation of the partition function of the ferromagnetic Q-state Potts model, for certain classes of graphs. In the paper "The Swendsen-Wang Process Does Not Always Mix Rapidly," V. Gore and

Bi-arc graphs and the complexity of list
Bi-arc graphs and the complexity of list homomorphisms
โœ Tomas Feder; Pavol Hell; Jing Huang ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 185 KB

## Abstract Given graphs __G__, __H__, and lists __L__(__v__) โŠ† __V__(__H__), __v__ ฮต __V__(__G__), a list homomorphism of __G__ to __H__ with respect to the lists __L__ is a mapping __f__ : __V__(__G__) โ†’ __V__(__H__) such that __u__v ฮต __E__(__G__) implies __f__(__u__)__f__(__v__) ฮต __E__(__H__),