✦ LIBER ✦

Covering the Edges of a Connected Graph by Paths

✍ Scribed by L. Pyber

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 316 KB
Volume: 66
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0012

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every connected graph on n vertices can be covered by at most nÂ2+O(n 3Â4 ) paths. This implies that a weak version of a well-known conjecture of Gallai is asymptotically true.

📜 SIMILAR VOLUMES

Covering the edges of a graph by three o

Covering the edges of a graph by three odd subgraphs

✍ Tamás Mátrai 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

Covering the Edges of a Graph by a Presc

Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 360 KB

Let H=(V H , E H ) be a graph, and let k be a positive integer. A graph G=(V G , E G ) is H-coverable with overlap k if there is a covering of the edges of G by copies of H such that no edge of G is covered more than k times. Denote by overlap(H, G) the minimum k for which G is H-coverable with over

On the edge-connectivity vector of a gra

On the edge-connectivity vector of a graph

✍ Linda M. Lesniak; Raymond E. Pippert 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

The number of connected sparsely edged g

The number of connected sparsely edged graphs

✍ E. M. Wright 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 472 KB

## Abstract An (__n, q__) graph has __n__ labeled points, __q__ edges, and no loops or multiple edges. The number of connected (__n, q__) graphs is __f(n, q)__. Cayley proved that __f(n, n__^‐1^) = __n__^n−2^ and Renyi found a formula for __f(n, n)__. Here I develop two methods to calculate the exp

Covering contractible edges in 3-connect

Covering contractible edges in 3-connected graphs. I: Covers of size three are cutsets

✍ Akira Saito 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 397 KB 👁 1 views

## Abstract An edge of a 3‐connected graph is said to be __contractible__ if its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (__Scientia__ (A) 2 (1988) 101–105) that the set of co

Approximation algorithms for covering a

Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight

✍ Shlomo Moran; Ilan Newman; Yaron Wolfstahl 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 464 KB