Isomorphism checking of I-graphs

Boris Horvat (Avtor), Tomaž Pisanski (Avtor), Arjana Žitnik (Avtor)

Povzetek

Obravnavamo razred ▫$I$▫-grafov - posplošitev razreda t.i. posplošenih Petersenovih grafov. Pokažemo da sta ▫$I$▫-grafa ▫$I(n, j, k)$▫ in ▫$I(n, j_1, k_1)$▫ izomorfna natanko takrat, ko obstaja celo število ▫$a$▫ tuje z ▫$n$▫, za katerega velja, da drži bodisi ▫$\{j_1, k_1\} = \{aj \mod n, \; ak \mod n \}$▫ bodisi ▫$\{j_1, k_1\} = \{aj \mod n, \; -ak \mod n\}$▫. Ta rezultat je uporaben pri preštevanju neizomorfnih ▫$I$▫-grafov in predstavitev z enotsko razdaljo posplošenih Petersenovih grafov.

Ključne besede

matematika;teorija grafov;izomorfizem;I-graf;posplošeni Petersenov graf;mathematics;graph theory;isomorphism;I-graph;generalized Petersen graph;

Podatki

Jezik:	Angleški jezik
Leto izida:	2012
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	16069977
ISSN:	0911-0119
Št. ogledov:	0
Št. prenosov:	0
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Preverjanje izomorfnosti I-grafov
Sekundarni povzetek:	We consider the class of ▫$I$▫-graphs, which is a generalization of the class of the generalized Petersen graphs. We show that two ▫$I$▫-graphs ▫$I(n, j, k)$▫ and ▫$I(n, j_1, k_1)$▫ are isomorphic if and only if there exists an integer ▫$a$▫ relatively prime to $n$ such that either ▫$\{j_1, k_1\} = \{aj \mod n, \; ak \mod n \}$▫ or ▫$\{j_1, k_1\} = \{aj \mod n, \; -ak \mod n\}$▫. This result has an application in the enumeration of non-isomorphic ▫$I$▫-graphs and unit-distance representations of generalized Petersen graphs.
Sekundarne ključne besede:	matematika;teorija grafov;izomorfizem;I-graf;posplošeni Petersenov graf;
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 823-830
Letnik:	Vol. 28
Zvezek:	no. 6
Čas izdaje:	2012
ID:	1475866