| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:On cube-free median graphs
Authors:Brešar, Boštjan (Author)
Klavžar, Sandi (Author)
Škrekovski, Riste (Author)
Files:URL http://dx.doi.org/10.1016/j.disc.2004.09.018
 
Language:English
Work type:Not categorized (r6)
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
UDC:519.17
ISSN on article:0012-365X
COBISS_ID:14179417 Link is opened in a new window
NUK URN:URN:SI:UM:DK:TRCATFX5
Views:371
Downloads:11
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:Misc.
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

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 New window

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 have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica