Covering numbers of regular multigraphs (Q753843)
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 4181397
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Covering numbers of regular multigraphs |
scientific article; zbMATH DE number 4181397 |
Statements
Covering numbers of regular multigraphs (English)
0 references
1989
0 references
Let n be odd. For every n-regular multigraph G on N vertices \(\alpha_ 1(G)\leq \lfloor (2n-3)N/(3n-4)\rfloor\), where \(\alpha_ 1(G)\) is the minimum size of an edge cover (i.e. a family of edges such that every vertex is incident with some of them). On the other hand, if N is a multiple of \(3n+1\) then there exists a multigraph G with \(\alpha_ 1(G)=2nN/(3n+1)\).
0 references
regular multigraph
0 references
edge cover
0 references
0.7851694822311401
0 references
0.7748510241508484
0 references
0.772746205329895
0 references
0.7725552320480347
0 references
