| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:The cube polynomial and its derivatives: the case of median graphs
Authors:Brešar, Boštjan (Author)
Klavžar, Sandi (Author)
Škrekovski, Riste (Author)
Files:URL http://www.combinatorics.org/
Work type:Not categorized (r6)
Typology:1.01 - Original Scientific Article
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:Naj bo ▫$alpha_i(G)$▫ število induciranih ▫$i$▫-kock grafa ▫$G$▫. Tedaj je polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ definiran z ▫$sum_{i ge 0} alpha_i (G) x_i$▫. Pokazano je, da je vsaka funkcija ▫$f$▫ z dvemi predpisanimi naravnimi lastnostmi do faktorja ▫$f(Q_0,x)$▫ enaka polinomu kock. Vpeljan je tudi odvod ▫$partial G$▫ medianskega grafa ▫$G$▫. Dokazano je, da je polinom kock edina funkcija ▫$f$▫ z lastnostjo ▫$f'(G,z) = f(partial G,x)$▫, če je le ▫$f(G,0) = |V(G)|$▫. Dokazanih je tudi več relacij za medianske grafe, ki posplošujejo prej znane rezultate. Na primer, za vsak ▫$s ge 0$▫ velja ▫$c^{(s)}(G, x+1) = sum_{i ge s} frac{c^{(s)}(G,x)}{(i-s)!}$▫.
Keywords:matematika, teorija grafov, polinom kock, odvod grafa, medianski grafi, mathematics, graph theory, cube polynomials, graph derivation, median graphs
Year of publishing:2003
Number of pages:R3 (11 str.)
Numbering:Vol. 10, no. 1
ISSN on article:1077-8926
COBISS_ID:12165977 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.

Record is a part of a journal

Title:The Electronic Journal of Combinatorics
Shortened title:Electron. J. Comb.
Publisher:N.J. Calkin and H.S. Wilf
COBISS.SI-ID:6973785 New window

Secondary language

Title:Polinom kock in njegovi odvodi: primer medianskih grafov
Abstract:For ▫$i ge 0$▫, the ▫$i$▫-cube of ▫$Q_i$▫ is the graph on ▫$2^i$▫ vertices representing ▫$0/1$▫ tuples of lenght ▫$i$▫, where two vertices are adjacent whenever the tuples differ in exactly one position. (In particular, ▫$Q_0=K_1$▫.) Let ▫$alpha_i(G)$▫ be the number of induced ▫$i$▫-cubes of a graph ▫$G$▫. Then the cube polynomial ▫$c(G,x)$▫ of ▫$G$▫ is introduced as ▫$sum_{i ge 0} alpha_i (G) x_i$▫. It is shown that any function ▫$f$▫ with two related, natural properties, is up to the factor ▫$f(Q_0,x)$▫ the cubes polynomial. The derivation ▫$partial G$▫ of a median graph ▫$G$▫ is also introduced and it is proved that the cubes polynomial is the only function ▫$f$▫ with the property ▫$f'(G,z) = f(partial G,x)$▫ provided that ▫$f(G,0) = |V(G)|$▫. As the main application of the new concept,several relations that widely generalize previous such results for median graphs are proved. For istance, it is shown that for any ▫$s ge 0$▫ we have ▫$c^{(s)}(G, x+1) = sum_{i ge s} frac{c^{(i)}(G,x)}{(i-s)!}$▫, where certain derivatives of the cube polynomial coincide with well-known invariants of median graphs.


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