𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Natural Imprint Function of a Graph

✍ Scribed by Boštjan Brešar

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
130 KB
Volume
23
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, some characterizations of median and quasi-median graphs are extended to general isometric subgraphs of Cartesian products using the concept of an imprint function as introduced by Tardif. This extends the well known concepts of medians in median graphs as well as imprints in quasi-median graphs. We introduce absolute C-median graphs in analogy to absolute retracts, and derive a connection with the canonical isometric embedding of graphs into Cartesian products. Absolute C-median graphs strictly include classes of irreducible graphs and absolute (weak) retracts as well as many median-like classes, such as weakly median graphs, pre-median graphs, and weakly modular graphs. New characterizations of quasi-median graphs and of median graphs are obtained along the way. Finally, we propose a conjecture on the amalgamation procedure for absolute C-median graphs, and prove the fixed box theorem for this class modulo the conjecture.

📜 SIMILAR VOLUMES

A Note on the Zeta Function of a Graph
A Note on the Zeta Function of a Graph
✍ Sam Northshield 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 113 KB

The number of spanning trees in a finite graph is first expressed as the derivative (at 1) of a determinant and then in terms of a zeta function. This generalizes a result of Hashimoto to non-regular graphs. ## 1998 Academic Press Let G be a finite graph. The complexity of G, denoted }, is the num

On the Number of Slopes of the Graph of
On the Number of Slopes of the Graph of a Function Defined on a Finite Field
✍ A. Blokhuis; S. Ball; A.E. Brouwer; L. Storme; T. Szőnyi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 116 KB

Given a set U of size q in an affine plane of order q, we determine the possibilities for the number of directions of secants of U, and in many cases characterize the sets U with given number of secant directions.

On the hamiltonian path graph of a graph
On the hamiltonian path graph of a graph
✍ George R. T. Hendry 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

On the eulericity of a graph
On the eulericity of a graph
✍ K. R. Matthews 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB

## Abstract The eulericity ϵ(__G__) of a bridgeless graph __G__ is defined as the least number of eulerian subgraphs of __G__ which together cover the lines of __G__. A 1–1 correspondence is shown to exist between the __k__‐tuples of eulerian subgraphs of __G__ and the proper flows (mod2^__k__^) on

On the independence ratio of a graph
On the independence ratio of a graph
✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB

## Abstract This paper presents some recent results on lower bounds for independence ratios of graphs of positive genus and shows that in a limiting sense these graphs have the same independence ratios as do planar graphs. This last result is obtained by an application of Menger's Theorem to show t