| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Roots of cube polynomials of median graphs
Authors:Brešar, Boštjan (Author)
Klavžar, Sandi (Author)
Škrekovski, Riste (Author)
Files:URL http://dx.doi.org/10.1002/jgt.20146
 
Language:English
Work type:Not categorized (r6)
Typology:1.01 - Original Scientific Article
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:Polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ je definiran z ▫$sum_{i ge 0}alpha_i(G)x^i$▫, kjer ▫$alpha_i(G)$▫ označuje število induciranih ▫$i$▫-kock v ▫$G$▫. Naj bo ▫$G$▫ medianski graf. Dokazano je, da je vsaka racionalna ničla polinoma ▫$c(G,x)$▫ oblike ▫$-frac{t+1}{t}$▫ za neko celo število ▫$t>0$▫ in da ima ▫$c(G,x)$▫ vedno realno ničlo na intervalu ▫$[-2,-1)$▫. Nadalje ima ▫$c(G,x)$▫ ▫$p$▫-kratno ničlo natanko tedaj, ko je ▫$G$▫ kartezični produkt ▫$p$▫ dreves istega reda. Grafi acikličnih kubičnih kompleksov so karakterizirani kot grafi za katere velja ▫$c(H,-2)=0$▫ za vsak 2-povezan konveksen podgraf ▫$H$▫.
Keywords:matematika, teorija grafov, polinom kock, koren, medianski graf, kartezični produkt grafov, mathematics, graph theory, cube polynomial, root, median graph, Cartesian product
Year of publishing:2006
Number of pages:str. 37-50
Numbering:Vol. 52, no. 1
UDC:519.17
ISSN on article:0364-9024
COBISS_ID:13960537 Link is opened in a new window
NUK URN:URN:SI:UM:DK:EZV3XXZT
Views:413
Downloads:46
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:Journal of graph theory
Shortened title:J. graph theory
Publisher:J. Wiley & Sons
ISSN:0364-9024
COBISS.SI-ID:25747712 New window

Secondary language

Language:Unknown
Title:Koreni polinoma kock medianskih grafov
Abstract:The cube polynomial ▫$c(G,x)$▫ of a graph ▫$G$▫ is defined as ▫$sum_{i ge 0}alpha_i(G)x^i$▫, where ▫$alpha_i(G)$▫ denotes the number of induced ▫$i$▫-cubes of ▫$G$▫, in particular, ▫$alpha_0(G) = |V(G)|$▫ and ▫$alpha_1(G) = |E(G)|$▫. Let ▫$G$▫ be a median graph. It is proved that every rational zero of ▫$c(G,x)$▫ is of the form ▫$-frac{t+1}{t}$▫ for some integer ▫$t>0$▫ and that ▫$c(G,x)$▫ always has a real zero in the interval ▫$[-2,-1)$▫. Moreover, ▫$c(G,x)$▫ has a ▫$p$▫-multiple zero if and only if ▫$G$▫ is the cartesian product of ▫$p$▫ trees all of the same order. Graphs of acyclic cubical complexes are characterized as the graphs ▫$G$▫ for which ▫$c(H,-2)=0$▫ holds for every 2-connected convex subgraph ▫$H$▫ of ▫$G$▫. Median graphs that are Cartesian products are also characterized.


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