Relations between median graphs, semi-median graphs and partial cubes

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Relations between median graphs, semi-median graphs and partial cubes
Authors:	ID Imrich, Wilfried (Author) ID Klavžar, Sandi (Author) ID Mulder, Henry Martyn (Author) ID Škrekovski, Riste (Author)
Files:	http://www.imfm.si/preprinti/PDF/00612.pdf
Language:	English
Work type:	Not categorized
Organization:	PEF - Faculty of Education
Abstract:	Podan je samostojen dokaz ekspanzijskega izreka za semi-medianske grafe. Dokazano je, da te grafe lahko karakteriziramo kot tlakovane delne kocke in da za njih velja neenakost ▫$2n-m-k le 2$▫. Pri tem je ▫$k$▫ število ekvivalenčnih razredov relacije ▫$Theta$▫. Za medianske grafe dokažemo, da se dajo karakterizirati kot semi-medianski grafi brez ▫$Q_3^-$▫. Vpeljemo tudi koncept šibke 2-konveksnosti in jo uporabimo, med drugim, za dokaz, da so medianski grafi dvodelni grafi, ki zadoščajo šibki 2-konveksnosti intervalov in štirikotniški lastnosti.
Keywords:	matematika, teorija grafov, medianski grafi, delne kocke, semi-medianski grafi, mathematics, graph theory, median graphs, partial cubes, semi median graphs
Year of publishing:	1998
Number of pages:	str. 1-15
Numbering:	Let. 36, št. 612
PID:	20.500.12556/DKUM-49362
ISSN:	1318-4865
UDC:	519.17
COBISS.SI-ID:	8227417
NUK URN:	URN:SI:UM:DK:DQ6Y4LLZ
Publication date in DKUM:	10.07.2015
Views:	1457
Downloads:	82
Metadata:
Categories:	Misc.
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Language:	Unknown
Title:	Relacije med medianskimi grafi, semi-medianskimi grafi in delnimi kockami
Abstract:	A rich structure theory has been developed in the last three decades for graphs embeddable into hypercubes, in particular for isometric subgraphs of hypercubes, also known as partial cubes, and for median graphs. Median graphs, which constitute a proper subclass of partial cubes, have attracted considerable attention. In order to better understand them semi-median graphs have been introduced but have turned out of form a rather interesting class of graphs by themselves. This class lies strictly between median graphs and partial cubes and satisfies an expansion theorem for which we give a self-contained proof. Furthermore, we show that these graphs can be characterized as tiled partial cubes and we prove for a semi-median graph ▫$G$▫ with ▫$n$▫ vertices, ▫$m$▫ edges and ▫$k$▫ equivalence classes of Djoković's relation ▫$Theta$▫, we have ▫$2n-m-k < 2$▫. Moreover, aquality holds if and only if ▫$G$▫ contains no ▫$K_2 Box C_{2t}$▫ with ▫$tge 2$▫ as a subgraph. For median graphs we show that they can be characterized as semi-median graphs which contain no convex ▫$Q_3^-$▫. i.e. the 3-cube minus a vertex, as a convex subgraph. Also, we introduce the concept of weak 2-convexity and use it, among other things, to prove that median graphs are bipartite, meshed graphs with weakly 2-convex intervals.

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back