On cube-free median graphs

| | 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://www.imfm.si/preprinti/PDF/00886.pdf
Language:	English
Work type:	Not categorized
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:	2003
Number of pages:	str. 1-9
Numbering:	Vol. 41, št. 886
PID:	20.500.12556/DKUM-49368
ISSN:	1318-4865
UDC:	519.17
COBISS.SI-ID:	12589913
NUK URN:	URN:SI:UM:DK:C5WBE0DR
Publication date in DKUM:	10.07.2015
Views:	1371
Downloads:	40
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan, KLAVŽAR, Sandi and ŠKREKOVSKI, Riste, 2003, On cube-free median graphs [online]. 2003. [Accessed 9 April 2025]. Retrieved from: http://www.imfm.si/preprinti/PDF/00886.pdf 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:

Similar works from our repository:

Similar works from other repositories:

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:	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.

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back