✦ LIBER ✦

Packings and perfect path double covers of maximal planar graphs

✍ Scribed by Karen Seyffarth

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 817 KB
Volume: 117
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90334-p

No coin nor oath required. For personal study only.

✦ Synopsis

Seyffarth, K., Packings and perfect path double covers of maximal planar graphs, Discrete Mathematics 117 (1993) 1833195.

A maximal planar graph is a simple planar graph in which every face is a triangle, and a perfect packing of such a graph by 2-cliques and facial triangles corresponds to a partition of the vertex set into classes, each of which induces either a 2-clique or a facial triangle in the graph. We prove a sufficient condition for a maximal planar graph to have a perfect packing by 2-cliques and facial triangles. This result then leads to a construction of a special type of perfect path double cover of a maximal planar graph.

📜 SIMILAR VOLUMES

Perfect path double covers of graphs

✍ J. A. Bondy 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 513 KB

## Abstract A __perfect path double cover__ (PPDC) of a graph __G__ on __n__ vertices is a family 𝒫 of __n__ paths of __G__ such that each edge of __G__ belongs to exactly two members of 𝒫 and each vertex of __G__ occurs exactly twice as an end of a path of 𝒫. We propose and study the conjecture th

Hajós' conjecture and small cycle double

Hajós' conjecture and small cycle double covers of planar graphs

✍ Karen Seyffarth 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 865 KB

## Seyffarth, K., Hajos' conjecture and small cycle double covers of planar graphs, Discrete Mathematics 101 (1992) 291-306. We prove that every simple even planar graph on n vertices has a partition of its edge set into at most [(n -1)/2] cycles. A previous proof of this result was given by Tao,