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

Boštjan Brešar (Avtor), Sandi Klavžar (Avtor), Riste Škrekovski (Avtor)

Povzetek

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)!}$▫.

Ključne besede

matematika;teorija grafov;polinom kock;odvod grafa;medianski grafi;mathematics;graph theory;cube polynomials;graph derivation;median graphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2003
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	12165977
ISSN:	1077-8926
Št. ogledov:	30
Št. prenosov:	6
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Polinom kock in njegovi odvodi: primer medianskih grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;polinom kock;odvod grafa;medianski grafi;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	R3 (11 str.)
Letnik:	ǂVol. ǂ10
Zvezek:	ǂno. ǂ1
Čas izdaje:	2003
ID:	1472232