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://dx.doi.org/10.1016/j.disc.2004.09.018
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
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:	2007
Št. strani:	str. 345-351
Številčenje:	Vol. 307, iss. 3-5
PID:	20.500.12556/DKUM-51565
UDK:	519.17
COBISS.SI-ID:	14179417
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:TRCATFX5
Datum objave v DKUM:	10.07.2015
Število ogledov:	1372
Število prenosov:	28
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan, KLAVŽAR, Sandi in ŠKREKOVSKI, Riste, 2007, On cube-free median graphs. Discrete mathematics [na spletu]. 2007. Vol. 307, no. 3–5, p. 345–351. [Dostopano 9 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2004.09.018 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:

Iščem podobna dela... Prosim, počakajte...

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

Gradivo je del revije

Naslov:	Discrete mathematics
Skrajšan naslov:	Discrete math.
Založnik:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

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