Characterizing almost-median graphs. II.

DOI10.1016/J.DISC.2011.09.008MaRDI QIDQ658076zbMATH OpenOpenAlexFDO

Authors Sandi Klavžar, S. Shpectorov

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.09.008

zbMATH Keywords

almost-median graphconvex cyclemedian graphpartial cube

Mathematics Subject Classification ID

Distance in graphs (05C12)

Review text

This paper is divided into four sections of which the last two discuss the kernel of the problem. While the third section deals with the convex cycles in a partial cube, Section 4 presents the main theorem, namely that if a graph \(G\) is a partial cube then \(G\) is almost-median if and only if \(G\) contains no convex cycles of length more than \(4\). This paper concludes by giving a short proof of the characterization of almost-median graphs due to \textit{I. Peterin} in his paper [``Quasi-almostmedian graphs, Ars Comb. (to appear)]. (For part I see [\textit{B. Brešar}, Eur. J. Comb. 28, No.\,3, 916--920 (2007; Zbl 1113.05029)].)

Recommendations

• Characterizing almost-median graphs
• Quasi-almostmedian graphs
• Partial cubes and their \(\tau\)-graphs
• Netlike partial cubes III. The median cycle property
• Netlike partial cubes. I. General properties

Cites work

• A convexity lemma and expansion procedures for bipartite graphs
• Characterizing almost-median graphs
• Convex excess in partial cubes
• Fast recognition algorithms for classes of partial cubes
• Fast recognition of classes of almost-median graphs
• Graphs of acyclic cubical complexes
• Isometric subgraphs of Hamming graphs and d-convexity
• Netlike partial cubes II. Retracts and netlike subgraphs
• Netlike partial cubes. I. General properties
• Quasi-almostmedian graphs
• Recognizing partial cubes in quadratic time
• Tiled partial cubes

Cited in

(16)

• Netlike partial cubes, V: completion and netlike classes
• Induced cycles in crossing graphs of median graphs
• Graphs and finite distributive partial lattices
• A new characterization of median graphs
• Median graphs and hypercubes, some new characterizations
• Graphs of acyclic cubical complexes
• Moore graphs and cycles are extremal graphs for convex cycles
• Regular pseudo-median graphs
• Tiled partial cubes
• Quasi-almostmedian graphs
• Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
• First-order logic axiomatization of metric graph theory
• A characterization of regular partial cubes whose all convex cycles have the same lengths
• On a generalization of median graphs: k-median graphs
• Fast recognition of classes of almost-median graphs
• Characterizing almost-median graphs

This page was built for publication: Characterizing almost-median graphs. II.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658076)