Janja Jerebic (Avtor), Sandi Klavžar (Avtor)

Povzetek

Primerjani sta krepka izometrična dimenzija in sosedna izometrična dimenzija grafov. Koncepta sta ekvivalentna za grafe premera 2 in v tem primeru se problem določitve dimenzije reducira na problem pokritja s polnimi dvodelnimi grafi. S pomočjo tega pristopa je določena krepka izometrična dimenzija in sosedna izometrična dimenzija za različne grafe (na primer za Petersenov graf). Podan je pozitiven odgovor na Problem 4.1 iz [Fitzpatrick, Nowakowski, The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38], ali obstaja tak graf ▫$G$▫, ki ima krepko izometrično dimenzijo večjo od ▫$\lceil |V(G)|/2 \rceil$▫.

Ključne besede

matematika;teorija grafov;krepki produkt grafov;krepka izometrična dimenzija;sosedna izometrična dimenzija;ne zaključna dela;mathematics;graph theory;strong product of graphs;adjacent isometric dimension;strong isometric dimension;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM PEF - Pedagoška fakulteta
Založnik: Elsevier
UDK: 519.17
COBISS: 14028121 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 1208
Št. prenosov: 122
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: O induciranih in izometričnih vložitvah grafov v krepke produkte poti
Sekundarni povzetek: The strong isometric dimension and the adjacent isometric dimension of graphs are compared. The concepts are equivalent for graphs of diameter 2 in which case the problem of determining these dimensions can be reduced to a covering problem with complete bipartite graphs. Using this approach several exact strong and adjacent dimensions are computed (for instance of the Petersen graph) and a positive answer is given to the Problem 4.1 of Fitzpatrick and Nowakowski [The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38] whether there is a graph ▫$G$▫ with the strong isometric dimension bigger that ▫$\lceil |V(G)|/2 \rceil$▫.
Sekundarne ključne besede: Teorija grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Znanstveno delo
Strani: str. 1358-1363
Letnik: ǂVol. ǂ306
Zvezek: ǂissue ǂ13
Čas izdaje: 2006
ID: 1472805