No label defined (Q4374729)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1109417
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1109417 |
Statements
25 January 1998
0 references
regular hexagon
0 references
hexagonal system
0 references
coronoid system
0 references
polyhex graph
0 references
perfect matching
0 references
benzenoid system
0 references
Kekulé structures
0 references
plane graph
0 references
0.8442085385322571
0 references
0.8147441744804382
0 references
0.7911602854728699
0 references
A hexagonal system is a finite connected plane graph with no cut-vertices in which every interior region is bounded by a regular hexagon of side length 1. A coronoid system \(G\) is a subgraph of a hexagonal system \(H\) which can be obtained from \(H\) by deleting some interior vertices and/or some interior edges such that each edge of \(G\) belongs to at least one hexagon of \(G\). A polyhex graph is either a hexagonal system or a coronoid system. A polyhex graph \(G\) is said to be \(k\)-coverable if for any \(k\) mutually disjoint hexagons the subgraph obtained from \(G\) by deleting all these \(k\) hexagons together with their incident edges has at least one perfect matching. In this paper a constructive criterion is given to determine whether or not a given polyhex graph is \(k\)-coverable (for \(k\geq 3\)). From this criterion follows that for any \(k,l\geq 3\) a polyhex graph \(G\) is \(k\)-coverable if and only if \(G\) is \(l\)-coverable. Furthermore, a simple but not very effective method is developed which allows us to determine whether or not there exists a \(k\)-coverable polyhex graph (and how it looks) with exactly \(h\) hexagons.
0 references