𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improved upper bound for the TSP in cubic 3-edge-connected graphs

✍ Scribed by David Gamarnik; Moshe Lewenstein; Maxim Sviridenko

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
193 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An upper bound for the radius of a 3-con
An upper bound for the radius of a 3-connected graph
✍ Jochen Harant πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 286 KB

For a 3-connected graph with radius r containing n vertices, in [1] r < n/4 + O(log n) was proved and r < n/4 + const was conjectured. Here we prove r < n/4 + 8. Let G be a simple 3-connected finite graph on n vertices with vertex set V(G) and edge set E(G). For X, YE V(G) we denote by d(X, Y) the

A general upper bound for the cyclic chr
A general upper bound for the cyclic chromatic number of 3-connected plane graphs
✍ Hikoe Enomoto; Mirko HorňÑk πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 457 KB πŸ‘ 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number Ο‡~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an

Tight upper bound on the number of edges
Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application
✍ Zhi-Zhong Chen; Shiqing Zhang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms fo

A sharp upper bound for the number of st
A sharp upper bound for the number of stable sets in graphs with given number of cut edges
✍ Hongbo Hua πŸ“‚ Article πŸ“… 2009 πŸ› Elsevier Science 🌐 English βš– 648 KB

Let G be a connected and simple graph, and let i(G) denote the number of stable sets in G. In this letter, we have presented a sharp upper bound for the i(G)-value among the set of graphs with k cut edges for all possible values of k, and characterized the corresponding extremal graphs as well.