On induced and isometric embeddings of graphs into the strong product of paths

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:	2006
Typology:	1.01 - Original Scientific Article
Organization:	UM PEF - Faculty of Education
UDC:	519.17
COBISS:	14028121
ISSN:	0012-365X
Views:	44
Downloads:	23
Average score:	0 (0 votes)
Metadata:

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