Shortest coverings of graphs with cycles (Q802571)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Shortest coverings of graphs with cycles |
scientific article; zbMATH DE number 3891407
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Shortest coverings of graphs with cycles |
scientific article; zbMATH DE number 3891407 |
Statements
Shortest coverings of graphs with cycles (English)
0 references
1983
0 references
Es wird bewiesen, daß jeder 2-fach kantenzusammenhängende, endliche Graph G ein System von Kreisen \(K_ 1,...,K_ m\) enthält, so daß jede Kante von G zu mindestens einem der Kreise \(K_ i\) gehört und \(\sum^{m}_{i=1}| K_ i| \leq \| G\| +\min \{2/3\| G\|,7/3(| G| -1)\}\) gilt, wobei \(| G|\) bzw. \(\| G\|\) die Ecken- bzw. Kantenzahl von G bedeute. Dies verschärft eine Abschätzung aus [\textit{A. Itai, R. J. Lipton, C. H. Papadimitriou} und \textit{M. Rodeh}: Covering graphs by simple circuits. SIAM J. Comput. 10, 746-750 (1981; Zbl 0468.68071)].
0 references
edge covering
0 references
bridgeless graph
0 references
cycles
0 references
0 references
0.8183518648147583
0 references
0.8163692951202393
0 references
0.8112685084342957
0 references
0.8109948635101318
0 references
0.8070568442344666
0 references
