𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Thep-maxian problem on block graphs

✍ Scribed by Liying Kang; Yukun Cheng

Publisher
Springer US
Year
2008
Tongue
English
Weight
338 KB
Volume
20
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The -maxian problem on a tree
The -maxian problem on a tree
✍ Rainer E. Burkard; Jafar Fathali; Hossein Taghizadeh Kakhki πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 141 KB
Optimal path cover problem on block grap
Optimal path cover problem on block graphs
✍ Wong Pak-Ken πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 427 KB

Let G = (V,E) be a block graph. First we show that an algorithm for finding the path partition number p(G) by J.H. Yan and G.J. Chang gives wrong answers to some block graphs. Then we present an efficient algorithm for finding a minimum path partition of G (not just the path partition number p(G)).

On thep-ranks of net graphs
On thep-ranks of net graphs
✍ RenΓ© Peeters πŸ“‚ Article πŸ“… 1995 πŸ› Springer 🌐 English βš– 669 KB
On theP4-Structure of Perfect Graphs V.
On theP4-Structure of Perfect Graphs V. Overlap Graphs
✍ ChΔ±́nh T. HoΓ ng; Stefan Hougardy; FrΓ©dΓ©ric Maffray πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 480 KB

Given a graph G we define its k-overlap graph as the graph whose vertices are the induced P 4 's of G and two vertices in the overlap graph are adjacent if the corresponding P 4 's in G have exactly k vertices in common. For k=1, 2, 3 we prove that if the k-overlap graph of G is bipartite then G is