| | 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://www.imfm.si/preprinti/PDF/00886.pdf
Work type:Not categorized (r6)
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
COBISS_ID:12589913 Link is opened in a new window
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
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.

Secondary language

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

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

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