Characterizing almost-median graphs II

S Klavzar; Sergey Shpectorov

doi:10.1016/j.disc.2011.09.008

Characterizing almost-median graphs II

S Klavzar, Sergey Shpectorov

Mathematics

Research output: Contribution to journal › Article

2 Citations (Scopus)

Abstract

Let M, A, S, and, P be the sets of median graphs, almost-median graphs, semi-median graphs and partial cubes, respectively. Then M subset of A subset of S subset of P. It is proved that a partial cube is almost-median if and only if it contains no convex cycle of length greater than 4. This extends the result of Bresar (2007) [2] who proved that the same property characterizes almost-median graphs within the class of semi-median graphs. (C) 2011 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	462-464
Number of pages	3
Journal	Discrete Mathematics
Volume	312
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2011.09.008
Publication status	Published - 1 Jan 2012

Keywords

Median graph
Almost-median graph
Convex cycle
Partial cube

Access to Document

10.1016/j.disc.2011.09.008

Cite this

@article{c7a5d86488114c6da9ee147ec65f1eeb,

title = "Characterizing almost-median graphs II",

abstract = "Let M, A, S, and, P be the sets of median graphs, almost-median graphs, semi-median graphs and partial cubes, respectively. Then M subset of A subset of S subset of P. It is proved that a partial cube is almost-median if and only if it contains no convex cycle of length greater than 4. This extends the result of Bresar (2007) [2] who proved that the same property characterizes almost-median graphs within the class of semi-median graphs. (C) 2011 Elsevier B.V. All rights reserved.",

keywords = "Median graph, Almost-median graph, Convex cycle, Partial cube",

author = "S Klavzar and Sergey Shpectorov",

year = "2012",

month = jan,

day = "1",

doi = "10.1016/j.disc.2011.09.008",

language = "English",

volume = "312",

pages = "462--464",

journal = "Discrete Mathematics",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Characterizing almost-median graphs II

AU - Klavzar, S

AU - Shpectorov, Sergey

PY - 2012/1/1

Y1 - 2012/1/1

N2 - Let M, A, S, and, P be the sets of median graphs, almost-median graphs, semi-median graphs and partial cubes, respectively. Then M subset of A subset of S subset of P. It is proved that a partial cube is almost-median if and only if it contains no convex cycle of length greater than 4. This extends the result of Bresar (2007) [2] who proved that the same property characterizes almost-median graphs within the class of semi-median graphs. (C) 2011 Elsevier B.V. All rights reserved.

AB - Let M, A, S, and, P be the sets of median graphs, almost-median graphs, semi-median graphs and partial cubes, respectively. Then M subset of A subset of S subset of P. It is proved that a partial cube is almost-median if and only if it contains no convex cycle of length greater than 4. This extends the result of Bresar (2007) [2] who proved that the same property characterizes almost-median graphs within the class of semi-median graphs. (C) 2011 Elsevier B.V. All rights reserved.

KW - Median graph

KW - Almost-median graph

KW - Convex cycle

KW - Partial cube

U2 - 10.1016/j.disc.2011.09.008

DO - 10.1016/j.disc.2011.09.008

M3 - Article

VL - 312

SP - 462

EP - 464

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Characterizing almost-median graphs II

Abstract

Keywords

Access to Document

Fingerprint

Cite this