𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On graphs whose star complement for −2 is a path or a cycle

✍ Scribed by Francis K Bell; Slobodan K Simić

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
241 KB
Volume
377
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

It was proved recently by one of the authors that, if H is a path P t (t > 2 with t / = 7 or 8) or an odd cycle C t (t > 3), then there is a unique maximal graph having H as a star complement for -2. The methods employed were analytical in nature, making use of the Reconstruction Theorem for star complements. Here we offer an alternative approach, based on the forbidden subgraph technique. In addition, we resolve the exceptional situations arising when H = P 7 or P 8 .

📜 SIMILAR VOLUMES

Cycles in a graph whose lengths differ b
Cycles in a graph whose lengths differ by one or two
✍ Bondy, J. A.; Vince, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 2 views

Several problems concerning the distribution of cycle lengths in a graph have been proposed by P. Erdös and colleagues. In this note two variations of the following such question are answered. In a simple graph where every vertex has degree at least three, must there exist two cycles whose lengths d

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a