Distinguishing Cartesian powers of graphs

Imrich, Wilfried; Klavžar, Sandi

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Distinguishing Cartesian powers of graphs
Authors:	ID Imrich, Wilfried (Author) ID Klavžar, Sandi (Author)
Files:	http://dx.doi.org/10.1002/jgt.20190
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	PEF - Faculty of Education
Abstract:	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.
Keywords:	matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Year of publishing:	2006
Number of pages:	str. 250-260
Numbering:	Vol. 53, iss. 3
PID:	20.500.12556/DKUM-51560
UDC:	519.17:512.54
ISSN on article:	0364-9024
COBISS.SI-ID:	14075481
NUK URN:	URN:SI:UM:DK:BEVHJRZI
Publication date in DKUM:	10.07.2015
Views:	1234
Downloads:	98
Metadata:
Categories:	Misc.
:	IMRICH, Wilfried and KLAVŽAR, Sandi, 2006, Distinguishing Cartesian powers of graphs. Journal of graph theory [online]. 2006. Vol. 53, no. 3, p. 250–260. [Accessed 1 April 2025]. Retrieved from: http://dx.doi.org/10.1002/jgt.20190 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:	Journal of graph theory
Shortened title:	J. graph theory
Publisher:	J. Wiley & Sons
ISSN:	0364-9024
COBISS.SI-ID:	25747712

Secondary language

Language:	Unknown
Title:	Razlikovanje kartezičnih potenc grafov
Abstract:	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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back