𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Regular pseudo-median graphs

✍ Scribed by Hans-Jürgen Bandelt; Henry Martyn Mulder

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
890 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is pseudo-median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo-median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyperoctahedron. Every self-map of a pseudo-median graph that preserves or collapses edges has an invariant regular pseudo-median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo-median graph induces a regular pseudo-median subgraph.

📜 SIMILAR VOLUMES

Medians in median graphs
Medians in median graphs
✍ H.J. Bandelt; J.P. Barthélemy 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 668 KB
The pseudo-cosine sequences of a distanc
The pseudo-cosine sequences of a distance-regular graph
✍ Arlene A. Pascasio; Paul Terwilliger 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 335 KB

Let denote a distance-regular graph with diameter D 3, valency k, and intersection numbers a i , b i , c i . By a pseudo-cosine sequence of we mean a sequence of real numbers σ 0 , σ 1 , . . . , σ D such that σ 0 = 1 and c i σ i-1 + a i σ i + b i σ i+1 = kσ 1 σ i for 0 i D -1. Let σ 0 , σ 1 , . . .

From Local Adjacency Polynomials to Loca
From Local Adjacency Polynomials to Locally Pseudo-Distance-Regular Graphs
✍ M.A Fiol; E Carriga 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 488 KB

The local adjacency polynomials can be thought of as a generalization, for all graphs, of (the sums of ) the distance polynomials of distance-regular graphs. The term ``local'' here means that we ``see'' the graph from a given vertex, and it is the price we must pay for speaking of a kind of distanc

On compact median graphs
On compact median graphs
✍ Tardif, Claude 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 715 KB

A median graph is called compact if it does not contain an isometric ray. This property is shown to be equivalent to the finite intersection property for convex sets. We show that a compact median graph contains a finite cube that is fixed by all of its automorphisms, and that each family of commuti

Regular factors of regular graphs
Regular factors of regular graphs
✍ B. Bollobás; Akira Saito; N. C. Wormald 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

Given r 3 3 and 1 s A s r, we determine all values of k for which every r-regular graph with edge-connectivity A has a k-factor. Some of the earliest results in graph theory are due to Petersen [8] and concern factors in graphs. Among others, Petersen proved that a regular graph of even degree has a