✦ LIBER ✦

A characterization of radius-critical graphs

✍ Scribed by Siemion Fajtlowicz

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 201 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120409

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is radius-critical if every proper induced connected subgraph of G has radius strictly smaller than the original graph. Our main purpose is to characterize all such graphs.

By a graph we shall mean here a finite, simple, undirected graph. For a connected graph the distance between two vertices u and u is the length of a shortest path joining these two vertices and it is denoted by d(u, u ) . If u is a vertex of maximum distance from u then d(u, u) is called the eccentricity of u. Every vertex of minimum eccentricity is a center of a graph and the eccentricity of the center is called the radius of the graph. A graph is r-critical if it has radius r and every proper induced connected subgraph has radius strictly smaller than r.

📜 SIMILAR VOLUMES

Characterization of maximum critically 2

Characterization of maximum critically 2-connected graphs

✍ R. C. Entringer 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

## Abstract A graph __G__ is critically 2‐connected if __G__ is 2‐connected but, for any point __p__ of __G, G — p__ is not 2‐connected. Critically 2‐connected graphs on __n__ points that have the maximum number of lines are characterized and shown to be unique for __n__ ⩾ 3, __n__ ≠ 11.

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.

The Spectral Radius of Graphs on Surface

The Spectral Radius of Graphs on Surfaces

✍ M.N. Ellingham; Xiaoya Zha 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 152 KB

This paper provides new upper bounds on the spectral radius \ (largest eigenvalue of the adjacency matrix) of graphs embeddable on a given compact surface. Our method is to bound the maximum rowsum in a polynomial of the adjacency matrix, using simple consequences of Euler's formula. Let # denote th

A Sharp Upper Bound of the Spectral Radi

A Sharp Upper Bound of the Spectral Radius of Graphs

✍ Yuan Hong; Jin-Long Shu; Kunfu Fang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 88 KB

A construction of chromatic index critic

A construction of chromatic index critical graphs

✍ Hian Poh Yap 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

## Abstract We prove that if __K__ is an undirected, simple, connected graph of even order which is of class one, regular of degree __p__ ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph __G__ obtained from __K__ by splitting any vertex is __p

Generalized eccentricity, radius, and di

Generalized eccentricity, radius, and diameter in graphs

✍ Dankelmann, Peter; Goddard, Wayne; Henning, Michael A.; Swart, Henda C. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 1 views

For a vertex v and a (k Ϫ 1)-element subset P of vertices of a graph, one can define the distance from v to P in various ways, including the minimum, average, and maximum distance from v to P. Associated with each of these distances, one can define the k-eccentricity of the vertex v as the maximum d