Distinguishing Cartesian powers of graphs

Imrich, Wilfried; Klavžar, Sandi

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Distinguishing Cartesian powers of graphs
Avtorji:	ID Imrich, Wilfried (Avtor) ID Klavžar, Sandi (Avtor)
Datoteke:	http://dx.doi.org/10.1002/jgt.20190
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	PEF - Pedagoška fakulteta
Opis:	Razlikovalno število $D(G)$ grafa je najmanjše celo število $d$ , za katero obstaja taka $d$ -označitev točk grafa $G$ , da je ne ohranja noben avtomorfizem grafa $G$ . Dokažemo, da je razlikovalno število kvadrata in višjih potenc povezanega grafa $G ne K_2, K_3$ , glede na kartezični produkt, vedno enako 2. Ta rezultat je močnejši od rezultatov Albertsona [Electron J Combin, 12 (2005), N17] za potence pra-grafov in tudi od rezultatov Klavžarja and Zhuja [European J. Combin, v tisku]. Bolj splošno, dokažemo tudi, da je $(G Box H) = 2$ , če sta $G$ in $H$ relativno tuja grafa in je $\|H\| le \|G\| < 2^{\|H\|} - \|H\|$ . Pod podobnimi pogoji veljajo sorodni rezultati tudi za potence grafov glede na krepki in direktni produkt grafov.
Ključne besede:	matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Leto izida:	2006
Št. strani:	str. 250-260
Številčenje:	Vol. 53, iss. 3
PID:	20.500.12556/DKUM-51560
UDK:	519.17:512.54
COBISS.SI-ID:	14075481
ISSN pri članku:	0364-9024
NUK URN:	URN:SI:UM:DK:BEVHJRZI
Datum objave v DKUM:	10.07.2015
Število ogledov:	1234
Število prenosov:	98
Metapodatki:
Področja:	Ostalo
:	IMRICH, Wilfried in KLAVŽAR, Sandi, 2006, Distinguishing Cartesian powers of graphs. Journal of graph theory [na spletu]. 2006. Vol. 53, no. 3, p. 250–260. [Dostopano 1 april 2025]. Pridobljeno s: http://dx.doi.org/10.1002/jgt.20190 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Podobna dela iz ostalih repozitorijev:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Journal of graph theory
Skrajšan naslov:	J. graph theory
Založnik:	J. Wiley & Sons
ISSN:	0364-9024
COBISS.SI-ID:	25747712

Sekundarni jezik

Jezik:	Neznan jezik
Naslov:	Razlikovanje kartezičnih potenc grafov
Opis:	The distinguishing number $D(G)$ of a graph is the least integer $d$ such that there is a $d$ -labeling of the vertices of $G$ that is not preserved by any nontrivial automorphism of $G$ . We show that the distinguishing number of the square and higher powers of a connected graph $G ne K_2, K_3$ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 (2005), N17] on powers of prime graphs, and results of Klavžar and Zhu [Eu J Combin, to appear]. More generally, we also prove thatd $(G Box H) = 2$ if $G$ and $H$ are relatively prime and $\|H\| le \|G\| < 2^{\|H\|} - \|H\|$ . Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj