✦ LIBER ✦

Bridged graphs and geodesic convexity

✍ Scribed by Martin Farber

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 588 KB
Volume: 66
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90100-2

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is bridged if each cycle C of length at least four contains two vertices whose distance from each other in G is strictly less than that in C. The class of bridged graphs is an extension of the class of chordal (or triangulated) graphs which arises in the study of convexity in graphs.

A set K of vertices of a graph G is geodesically convex if K contains every vertex on every shortest path joining vertices in K. It is known that a graph is bridged if and only if the closed neighborhood of every geodesically convex set is again geodesically convex.

This paper contains several results concerning geodesicaUy convex sets in bridged graphs. As an interesting consequence of these results we obtain two recursive characterizations of the class of bridged graphs.

📜 SIMILAR VOLUMES

A Helly theorem for geodesic convexity i

A Helly theorem for geodesic convexity in strongly dismantlable graphs

✍ Norbert Polat 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 476 KB

A (finite or infinite) graph G is strongly dismantlable if its vertices can be linearly ordered x o ..... x~ so that, for each ordinal fl < ~, there exists a strictly increasing finite sequence (i~)0~<j~<n of ordinals such that i o = fl, i, = ct and xi~ +1 is adjacent with x~j and with all neighbors

Geodesics and almost geodesic cycles in

Geodesics and almost geodesic cycles in random regular graphs

✍ Itai Benjamini; Carlos Hoppen; Eran Ofek; Paweł Prałat; Nick Wormald 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d G (u, v) is at least d C (u, v)-e(n). Let (n) be any function tending to infin

On constructible graphs, locally Helly g

On constructible graphs, locally Helly graphs, and convexity

✍ Norbert Polat 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

## Abstract A (finite or infinite) graph __G__ is __constructible__ if there exists a well‐ordering ≤ of its vertices such that for every vertex __x__ which is not the smallest element, there is a vertex __y__ < __x__ which is adjacent to __x__ and to every neighbor __z__ of __x__ with __z__ < __x_

A Convexity Lemma and Expansion Procedur

A Convexity Lemma and Expansion Procedures for Bipartite Graphs

✍ W. Imrich; S. Klavžar 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 148 KB

A hierarchy of classes of graphs is proposed which includes hypercubes, acyclic cubical complexes, median graphs, almost-median graphs, semi-median graphs and partial cubes. Structural properties of these classes are derived and used for the characterization of these classes by expansion procedures,

Convexity of minimal total dominating fu

Convexity of minimal total dominating functions in graphs

✍ Yu, Bo 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB 👁 2 views

A total dominating function (TDF) of a graph G = (V, E) is a function f : V → [0, 1] such that for each v ∈ V , the sum of f values over the open neighbourhood of v is at least one. Zero-one valued TDFs are precisely the characteristic functions of total dominating sets of G. We study the convexity

Geodesic graphs on the 13–dimensional gr

Geodesic graphs on the 13–dimensional group of Heisenberg type

✍ Z. Dušek; O. Kowalski 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract A __g.o. space__ is a homogeneous Riemannian manifold __M__ = (__G/H, g__) on which every geodesic is an orbit of a one–parameter subgroup of the group __G__. (__G__ acts transitively on __M__ as a group of isometries.) Each g.o. space gives rise to certain rational maps called “geodesi