𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A common generalization of line graphs and clique graphs

✍ Scribed by Erich Prisner

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
664 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k‐edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k‐edge graph Ξ”__~k~(G__) of a graph G is defined as the intersection graph of the set of all k‐edges of G. The following three problems are investigated for k‐edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k‐edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k‐edge graphs?

πŸ“œ SIMILAR VOLUMES

A generalization of perfect graphs?i-per
A generalization of perfect graphs?i-perfect graphs
✍ Cai, Leizhen; Corneil, Derek πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc

Diameters of iterated clique graphs of c
Diameters of iterated clique graphs of chordal graphs
✍ Bor-Liang Chen; Ko-Wei Lih πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^nβˆ’1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

A generalization of chordal graphs
A generalization of chordal graphs
✍ P. D. Seymour; R. W. Weaver πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

Metric characterizations of proper inter
Metric characterizations of proper interval graphs and tree-clique graphs
✍ Gutierrez, M.; OubiοΏ½a, L. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 393 KB πŸ‘ 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

A note on generalized line graphs
A note on generalized line graphs
✍ Peter J. Cameron πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 167 KB πŸ‘ 1 views

## Abstract Whitney's theorem on line graphs is extended to the class of generalized line graphs defined by Hoffman.