The cube polynomial and its derivatives: the case of median graphs

Brešar, Boštjan; Klavžar, Sandi; Škrekovski, Riste

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	The cube polynomial and its derivatives: the case of median graphs
Authors:	ID Brešar, Boštjan (Author) ID Klavžar, Sandi (Author) ID Škrekovski, Riste (Author)
Files:	http://www.combinatorics.org/
Language:	English
Work type:	Not categorized
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
PID:	20.500.12556/DKUM-51455
UDC:	519.17
ISSN on article:	1077-8926
COBISS.SI-ID:	12165977
NUK URN:	URN:SI:UM:DK:5YNSNFQS
Publication date in DKUM:	10.07.2015
Views:	1106
Downloads:	54
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan, KLAVŽAR, Sandi and ŠKREKOVSKI, Riste, 2003, The cube polynomial and its derivatives: the case of median graphs. The Electronic journal of combinatorics [online]. 2003. Vol. 10, no. 1. [Accessed 26 April 2025]. Retrieved from: http://www.combinatorics.org/ 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.

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
ISSN:	1077-8926
COBISS.SI-ID:	6973785

Secondary language

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

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back