𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on path-perfect graphs

✍ Scribed by John Frederick Fink; H.Joseph Straight

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
498 KB
Volume
33
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we explore the c:oncept of factoring a graph into non-isomorphic paths. Lel Pi denote the path of length i. We SAY that a graph G having $n(n + 1) edges is path-perfect if E( G) can be partitioned as E, UE, !J l * l U & such that the subgraph of G induced by 32i is isomorphic to Pr, for 14 bn. It is noted that the< graphs I&, K(r, 2r -1) and K(r, 2r+ ?I are path-perfect. Also some resuk are given concerning the existen* of regular path-perfect graphs.

πŸ“œ SIMILAR VOLUMES

A note on path-zero graphs
A note on path-zero graphs
✍ J.J. Seidel πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 207 KB

of the matrix equation P\*(X,,) = O,, where Pk(k) is the characteristic equation of the path-graph of length k.

A note on Ki-perfect graphs
A note on Ki-perfect graphs
✍ Jason I. Brown; Derek G. Corneil; A. Ridha Mahjoub πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 348 KB

## Abstract __Ki__‐perfect graphs are a special instance of __F ‐ G__ perfect graphs, where __F__ and __G__ are fixed graphs with __F__ a partial subgraph of __G.__ Given __S__, a collection of __G__‐subgraphs of graph __K__, an __F ‐ G__ cover of __S__ is a set of __T__ of __F__‐subgraphs of __K__

Perfect path double covers of graphs
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

A note on path and cycle decompositions
A note on path and cycle decompositions of graphs
✍ Dom Decaen πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 137 KB πŸ‘ 1 views

## Abstract In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph __G__ has a smallest path (resp. path‐cycle) decomposition __P__ such that every odd vertex of __G__ is the endpoint of exactly one path of __P__? This note g

A note on the characterization of domina
A note on the characterization of domination perfect graphs
✍ Jason Fulman πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 191 KB

## Abstract A graph __G__ is domination perfect if for each induced subgraph __H__ of __G__, Ξ³(__H__) = __i__(__H__), where Ξ³ and __i__ are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of