Quasi-median graphs, their generalizations, and tree-like equalities
type: Item
instance of: scholarly article
title: Quasi-median graphs, their generalizations, and tree-like equalities
zbMATH Open document ID: 1022.05070
DOI: 10.1016/S0195-6698(03)00045-3
author: Boštjan Brešar
author: Riste Škrekovski
author: Sandi Klavžar
published in: European Journal of Combinatorics
publication date: 2003-07-30T00:00:00Z
review text: Let \(G\) be a graph with \(V(G)\) and \(E(G)\) denoting the sets of vertices and edges of \(G\), respectively. For an edge \(ab\) of \(G\), set \( W_{ab}=\{x\in V(G):d(x,a)<d(x,b)\}\) and \(U_{ab}=\{x\in W_{ab}:x\) has a neighboor \(y\) in \(W_{ba}\}.\) \(G\) is called quasi-median if every clique in \(G\) is gated and for any edge \(ab\), \(U_{ab}\) is convex. The paper presents three characterizations of quasi-median graphs and also proves two equalities for these graphs. Finally, an Euler formula is derived for graphs that can be obtained by a sequence of connected expansions from \( K_{1}\).
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1957117
zbMATH Keywords: quasi-median graph
zbMATH Keywords: partial Hamming graph
zbMATH Keywords: quasi-semimedian graph
zbMATH Keywords: tree-like equality
zbMATH Keywords: Euler-type formula
reviewed by: Vasile Berinde
MaRDI profile type: Publication
cites work: Quasi‐median graphs and algebras
cites work: Decomposition and \(l_1\)-embedding of weakly median graphs
cites work: Partial Hamming graphs and expansion procedures
cites work: Tiled partial cubes
cites work: The cube polynomial and its derivatives: The case of median graphs
cites work: Retracts of infinite Hamming graphs
cites work: Invariant Hamming graphs in infinite quasi-median graphs
cites work: Isometric subgraphs of Hamming graphs and d-convexity
cites work: Q3983321
cites work: Separation of two convex sets in convexity structures
cites work: Q3785965
cites work: A dynamic location problem for graphs
cites work: Distance-preserving subgraphs of hypercubes
cites work: Product graph representations
cites work: On the Addressing Problem for Loop Switching
cites work: On Isometric Embeddings of Graphs
cites work: Skeletons, recognition algorithm and distance matrix of quasi-median graphs
cites work: A convexity lemma and expansion procedures for bipartite graphs
cites work: Q4523707
cites work: Median Graphs and Triangle-Free Graphs
cites work: Q4264556
cites work: An Euler-type formula for median graphs
cites work: On median graphs and median grid graphs
cites work: The structure of median graphs
cites work: Q3890733
cites work: Q3972522
cites work: Two relations for median graphs
cites work: Prefibers and the cartesian product of metric spaces
cites work: Recognizing pseudo-median graphs
cites work: Isometric embeddings in Hamming graphs
cites work: The retracts of Hamming graphs
cites work: Isometric embedding in products of complete graphs
full work available at URL: s0195-6698(03)00045-3
OpenAlex ID: W2035212325
description: scientific article; zbMATH DE number 1957117