𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Perfect k-line graphs and k-total graphs

✍ Scribed by Van Bang Lê

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
443 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The concept of the line graph can be generalized as follows. The k‐line graph L~k~(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L~k~(G) if and only if they have in G k − 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3‐line graphs and 3‐total graphs. Moreover, perfect 3‐line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

k-Bounded classes of dominant-independen
k-Bounded classes of dominant-independent perfect graphs
✍ Zverovich, Igor E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 2 views

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a f

The symmetric (2k, k)-graphs
The symmetric (2k, k)-graphs
✍ Matthias Kriesell 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views
k-shredders in k-connected graphs
k-shredders in k-connected graphs
✍ Yoshimi Egawa 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract For a graph __G__, a subset __S__ of __V__(__G__) is called a shredder if __G__ − __S__ consists of three or more components. We show that if __k__ ≥ 4 and __G__ is a __k__‐connected graph, then the number of shredders of cardinality __k__ of __G__ is less than 2|__V__(__G__)|/3 (we sho

Minimally (k, k)-edge-connected graphs
Minimally (k, k)-edge-connected graphs
✍ Kamal Hennayake; Hong-Jian Lai; Deying Li; Jingzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract For an integer __l__ > 1, the __l__‐edge‐connectivity of a connected graph with at least __l__ vertices is the smallest number of edges whose removal results in a graph with __l__ components. A connected graph __G__ is (__k__, __l__)‐edge‐connected if the __l__‐edge‐connectivity of __G_

k-ordered Hamiltonian graphs
k-ordered Hamiltonian graphs
✍ Ng, Lenhard; Schultz, Michelle 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v 1 , v 2 , . . . , v k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v 1 , v 2 , . . . , v k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be h