On cube-free median graphs

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

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On cube-free median graphs
Authors:	ID Brešar, Boštjan (Author) ID Klavžar, Sandi (Author) ID Škrekovski, Riste (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2004.09.018
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
Abstract:	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.
Keywords:	matematika, teorija grafov, medianski graf, kartezični produkt, prepoznavni algoritem, mathematics, graph theory, median graph, cube-free graph, Cartesian product, recognition algoritem
Year of publishing:	2007
Number of pages:	str. 345-351
Numbering:	Vol. 307, iss. 3-5
PID:	20.500.12556/DKUM-51565
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	14179417
NUK URN:	URN:SI:UM:DK:TRCATFX5
Publication date in DKUM:	10.07.2015
Views:	1372
Downloads:	28
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan, KLAVŽAR, Sandi and ŠKREKOVSKI, Riste, 2007, On cube-free median graphs. Discrete mathematics [online]. 2007. Vol. 307, no. 3–5, p. 345–351. [Accessed 9 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2004.09.018 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Searching for similar works... Please wait....

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

Record is a part of a journal

Title:	Discrete mathematics
Shortened title:	Discrete math.
Publisher:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Secondary language

Language:	Unknown
Title:	O medianskih grafih brez 3-kocke
Abstract:	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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back