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

Abstract

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$▫.

Keywords

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

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM PEF - Faculty of Education
UDC: 519.17
COBISS: 14028121 Link will open in a new window
ISSN: 0012-365X
Views: 44
Downloads: 23
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: O induciranih in izometričnih vložitvah grafov v krepke produkte poti
Secondary abstract: 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$▫.
Secondary keywords: matematika;teorija grafov;krepki produkt grafov;krepka izometrična dimenzija;sosedna izometrična dimenzija;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 1358-1363
Volume: ǂVol. ǂ306
Issue: ǂiss. ǂ13
Chronology: 2006
ID: 1472805