| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava
Prva stran > Izpis gradiva

Izpis gradiva Pomoč

Naslov:Relations between median graphs, semi-median graphs and partial cubes
Avtorji:ID Imrich, Wilfried (Avtor)
ID Klavžar, Sandi (Avtor)
ID Mulder, Henry Martyn (Avtor)
ID Škrekovski, Riste (Avtor)
Datoteke:URL http://www.imfm.si/preprinti/PDF/00612.pdf
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano
Organizacija:PEF - Pedagoška fakulteta
Opis: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−kle2. 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.
Ključne besede:matematika, teorija grafov, medianski grafi, delne kocke, semi-medianski grafi, mathematics, graph theory, median graphs, partial cubes, semi median graphs
Leto izida:1998
Št. strani:str. 1-15
Številčenje:Let. 36, št. 612
PID:20.500.12556/DKUM-49362 Novo okno
ISSN:1318-4865
UDK:519.17
COBISS.SI-ID:8227417 Novo okno
NUK URN:URN:SI:UM:DK:DQ6Y4LLZ
Datum objave v DKUM:10.07.2015
Število ogledov:1266
Število prenosov:46
Metapodatki:XML DC-XML DC-RDF
Področja:Ostalo
:
IMRICH, Wilfried, KLAVŽAR, Sandi, MULDER, Henry Martyn in ŠKREKOVSKI, Riste, 1998, Relations between median graphs, semi-median graphs and partial cubes [na spletu]. 1998. [Dostopano 28 marec 2025]. Pridobljeno s: http://www.imfm.si/preprinti/PDF/00612.pdf
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:Neznan jezik
Naslov:Relacije med medianskimi grafi, semi-medianskimi grafi in delnimi kockami
Opis: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 K2BoxC2t with tge2 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.


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici