✦ LIBER ✦

Generalized line graphs

✍ Scribed by Dragoš Cvetkovic̀; Michael Doob; Slobodan Simic̀

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 775 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050408

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz‐type covering characterization, and Whitney‐type theorems on isomorphisms and automorphisms.

📜 SIMILAR VOLUMES

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.

Equivalence of four descriptions of gene

Equivalence of four descriptions of generalized line graphs

✍ G. R. Vijayakumar 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB 👁 1 views

A new characterization of generalized line graphs, analogous to that of line graphs found by Van Rooij and Wilf [Acta Math Acad Sci Hungar 16 (1965), 263-269] is obtained. By a cycle of implications, we settle the equivalence of the definition of generalized line graph given by Hoffman [Combinatoria

A common generalization of line graphs a

A common generalization of line graphs and clique graphs

✍ Erich Prisner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 664 KB

## 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__‐

Generalized steinhaus graphs

✍ Neal Brand; Margaret Morton 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 584 KB

## Abstract A generalized Steinhaus graph of order __n__ and type __s__ is a graph with __n__ vertices whose adjacency matrix (__a__~i,j~) satisfies the relation magnified image where 2 ≦__i__≦__n__−1, __i__ + __s__(__i__ − 1 ≦ __j__ ≦ __n__, __c__~r,i,j~ ϵ {0,1} for all 0 ≦ __r__ ≦ __s__(__i__) −1

Generalized and/or graphs

✍ Giorgio Levi; Franco Sirovich 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 974 KB

A generalization of AND/OR graphs is introduced as a problem solving model, in which subproblem interdependence in problem reduction can be explicitly accounted for. An ordered-search algorithm is given to fred a solution. The algorithm is proven to be admissible and optimal Examples are given which

Which generalized petersen graphs are ca

Which generalized petersen graphs are cayley graphs?

✍ Roman Nedela; Martin Škoviera 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 572 KB

## Abstract The generalized Petersen graph __GP__ (__n, k__), __n__ ≤ 3, 1 ≥ __k__ < __n__/2 is a cubic graph with vertex‐set {u~j~; i ϵ Z~n~} ∪ {v~j~; i ϵ Z~n~}, and edge‐set {u~i~u~i~, u~i~v~i~, v~i~v~i+k, iϵ~Z~n~}. In the paper we prove that (i) __GP__(__n, k__) is a Cayley graph if and only if