𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The coordinate representation of a graph and n-universal graph of radius 1

✍ Scribed by A.V. Ivashchenko

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
411 KB
Volume
120
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space E". Cube vertices have integer coordinates.

The coordinate matrix, A(G) = {v.~} of a graph G is defined by the set of cube coordinates.

The imbedded dimension of a graph, BP(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements v,,#v,,.

We show that Bp(G)=cub(G) for some graphs, and Bp(G)<n-2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3"-' vertices that contains as an induced subgraph a copy of any graph on n vertices.

πŸ“œ SIMILAR VOLUMES

On the spectral radius of a directed gra
On the spectral radius of a directed graph
✍ Kwapisz, Jaroslaw πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 314 KB πŸ‘ 2 views

We provide upper estimates on the spectral radius of a directed graph. In particular w e prove that the spectral radius is bounded by the maximum of the geometric mean of in-degree and out-degree taken over all vertices.

On the hamiltonian index and the radius
On the hamiltonian index and the radius of a graph
✍ Marko LovrečičSaraαΊ‘in πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 316 KB

Catlin et al. [1, Corollary 9A] characterised the graphs G with the property that ham(G) > rad(G) + 1 where ham(G) and rad(G) stand for the hamiltonian index and the radius of G, respectively. Here a slightly stronger result is presented. In effect, the graphs for which ham(G) > rad(G) holds are ch

The Laplacian spectral radius of a graph
The Laplacian spectral radius of a graph under perturbation
✍ Ji-Ming Guo πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 251 KB

In this paper, we investigate how the Laplacian spectral radius changes when one graph is transferred to another graph obtained from the original graph by adding some edges, or subdivision, or removing some edges from one vertex to another.