On cube-free median graphs

Brešar, Boštjan; Klavžar, Sandi; Škrekovski, Riste

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	On cube-free median graphs
Avtorji:	ID Brešar, Boštjan (Avtor) ID Klavžar, Sandi (Avtor) ID Škrekovski, Riste (Avtor)
Datoteke:	http://www.imfm.si/preprinti/PDF/00886.pdf
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Organizacija:	FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis:	Naj bo $G$ mediansk graf brez 3-kocke. Pokazano je, da velja $frac{k}{2} ge sqrt{n}-1 ge frac{m}{2sqrt{n}} ge sqrt{s} ge r-1$ , kjer so $n, m, s, k$ in $r$ števila točk, povezav, kvadratov, $Theta$ -razredov in število povezav najmanšega $Theta$ -razreda grafa $G$ . Enakosti so dosežene natanko tedaj, ko je $G$ kartezični produkt dveh dreves istega reda. Obravnavan je tudi polinom kock medianskih grafov in pokazano je, da lahko ravninske medianske grafe brez 3-kocke prepoznamo v linearnem času.
Ključne besede:	matematika, teorija grafov, medianski graf, kartezični produkt, prepoznavni algoritem, mathematics, graph theory, median graph, cube-free graph, Cartesian product, recognition algoritem
Leto izida:	2003
Št. strani:	str. 1-9
Številčenje:	Vol. 41, št. 886
PID:	20.500.12556/DKUM-49368
ISSN:	1318-4865
UDK:	519.17
COBISS.SI-ID:	12589913
NUK URN:	URN:SI:UM:DK:C5WBE0DR
Datum objave v DKUM:	10.07.2015
Število ogledov:	1371
Število prenosov:	40
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan, KLAVŽAR, Sandi in ŠKREKOVSKI, Riste, 2003, On cube-free median graphs [na spletu]. 2003. [Dostopano 9 april 2025]. Pridobljeno s: http://www.imfm.si/preprinti/PDF/00886.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:

Podobna dela iz repozitorija:

Tranzitivni, lokalno končni medianski grafi s končnimi bloki
Mulder, Henry Martin: Metric graph theory: the case of median graphs. - Graph connections (Cochin, 1998), 19-32, Allied Publ., New Delhi, 1999
Brešar, Boštjan: On the natural imprint function of a graph. - European J. Combin. 23 (2002), no. 2, 149-161
Križni grafi grafov zastraženih inverzov
Relations between median graphs, semi-median graphs and partial cubes

Podobna dela iz ostalih repozitorijev:

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:	O medianskih grafih brez 3-kocke
Opis:	Let $G$ be a cube-free median graph. It is proved that $frac{k}{2} ge sqrt{n}-1 ge frac{m}{2sqrt{n}} ge sqrt{s} ge r-1$ , where $n, m, s, k$ and $r$ are the number of vertices, edges, squares, $Theta$ -classes, and the number of edges in a smallest $Theta$ -class of $G$ , respectively. Moreover, the equalities characterize Cartesian product of two trees of the same order. The cube polynomial of cube-free median graphs is also considered and it is shown that planar cube-free median graphs can be recognized in linear time.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj